普通计算姬

wjh15101051's space

卧薪尝胆，厚积薄发。

普通计算姬

Date: Sun Jul 15 19:11:13 CST 2018

In Category: NoCategory

Description：

给定一棵 $n$ 个节点的带权树，节点编号为 $1$ 到 $n$ ，以 $root$ 为根，设 $sum[p]$ 表示以点 $p$ 为根的这棵子树中所有节点的权值和。两种操作:

$1$ 给定两个整数 $u,v$ ，修改点 $u$ 的权值为 $v$ 。

$2$ 给定两个整数 $l,r$ ，计算 $sum[l]+sum[l+1]+\dots+sum[r-1]+sum[r]$

$N\le10^5$

Solution：

树状数组维护 $dfs$ 序即可求子树和，每次修改是单点修改， $\sum sum[p]$ 没有什么特殊性质，考虑分块，大的整块加，散的树状数组。

维护 $f[i][j]$ 表示 $i$ 这个块内，有多少点是 $j$ 的祖先（包含j自身）。这个可以 $dfs$ 开一个桶记录每个块的值。修改时加 $f[k][x]\times (y-lastval[x])$

查询的复杂度： $O(Q\sqrt N logN)$

修改的复杂度： $O(Q\sqrt N)$

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef unsigned long long ll;

ll val[MAXN];

int root;

//edge

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

//block

#define MAXB 333

int cnt;

ll sum[MAXB],tag[MAXB];

int L[MAXB],R[MAXB],belong[MAXN];

void build(int l,int r,int k)

{

	L[k] = l;R[k] = r;

	for(int i = l;i <= r;++i)belong[i] = k;

	return;

}

//prework

int f[MAXB][MAXN];

int basket[MAXB];

bool vis[MAXN];

ll s[MAXN];

int rank[MAXN],cur = 0,siz[MAXN];

void dfs(int k)

{

	rank[k] = ++cur;

	s[k] = val[k];siz[k] = 1;

	vis[k] = true;

	basket[belong[k]]++;

	for(int i = 1;i <= cnt;++i)f[i][k] = basket[i];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!vis[e[i].to])

		{

			dfs(e[i].to);

			s[k] += s[e[i].to];

			siz[k] += siz[e[i].to];

		}

	}

	basket[belong[k]]--;

	return;

}

//BIT

ll c[MAXN];

int lowbit(int x){return x&(-x);}

void inc(int p,ll k){for(int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

ll query(int p){ll res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)val[i] = (ll)read();

	int a,b;

	for(int i = 1;i <= n;++i)

	{

		a = read();b = read();

		if(a == 0)root = b;

		else add(a,b);

	}

	cnt = sqrt(n);

	for(int i = 1;i <= cnt;++i)build((i - 1) * cnt + 1,i * cnt,i);

	if(cnt * cnt < n){build(R[cnt] + 1,n,cnt + 1);++cnt;}

	memset(vis,false,sizeof(vis));

	dfs(root);

	for(int i = 1;i <= n;++i)

	{

		sum[belong[i]] += s[i];

		inc(rank[i],val[i]);

	}

	int type,x,y;

	for(int i = 1;i <= m;++i)

	{

		type = read();x = read();y = read();

		if(type == 1)

		{

			inc(rank[x],(ll)y - val[x]);

			for(int k = 1;k <= cnt;++k)

			{

				tag[k] += (ll)f[k][x] * ((ll)y - val[x]);

			}

			val[x] = (ll)y;

		}

		else 

		{

			if(belong[x] == belong[y])

			{

				ll ans = 0;

				for(int k = x;k <= y;++k)ans += query(rank[k] + siz[k] - 1) - query(rank[k] - 1);

				cout << ans << endl;

			}

			else

			{

				ll ans = 0;

				for(int k = belong[x] + 1;k <= belong[y] - 1;++k)

				{

					ans += sum[k] + tag[k];

				}

				for(int k = x;k <= R[belong[x]];++k)ans += query(rank[k] + siz[k] - 1) - query(rank[k] - 1);

				for(int k = L[belong[y]];k <= y;++k)ans += query(rank[k] + siz[k] - 1) - query(rank[k] - 1);

				cout << ans << endl;

			}

		}

	}

	return 0;

}

In tag: 数据结构-分块

wjh15101051