[bzoj3730][动态点分治][线段树]震波

De ion

在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。 接下来你需要在线处理M次操作： 0 x k
表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。 1
x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。

Input

第一行包含两个正整数N和M。 第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。 接下来M行，每行包含三个数，表示M次操作。

Output

包含若干行，对于每个询问输出一行一个正整数表示答案。

Sample Input

8 1

1 10 100 1000 10000 100000 1000000 10000000

1 2

1 3

2 4

2 5

3 6

3 7

3 8

0 3 1

Sample Output

11100101

HINT

1<=N,M<=100000

1<=u,v,x<=N

1<=value[i],y<=10000

0<=k<=N-1

题解

学一手动态点分治
需要一棵点分树
容易发现，点分树的树高只有log
动态点分治就是考虑在这上面搞事
先单考虑在原树上的过程，我们可以每次向上跳一个祖先，然后记录距离他是K-1的点
这样会记重 于是你要减去当前距离上一个祖先也是K-1的点
拓展到点分树上也是一样的
每个点开两颗线段树 记录距离自己的值的点和距离点分树上上一个祖先的点
每个跳就行了
然后
这题卡常数啊
我的9K代码硬是没卡过去
有没有大爷伸出援手的鸭…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline char nc() {
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(void) {
    char ch=nc();
    int sum=0;
    while(!(ch>=\'0\'&&ch<=\'9\'))
        ch=nc();
    while(ch>=\'0\'&&ch<=\'9\')
        sum=(sum<<3)+(sum<<1)+(ch^48),ch=nc();
    return sum;
}
static int stack[20];
inline void write(int x)
{
	if(x<0){putchar(\'-\');x=-x;}
    if(!x){putchar(\'0\');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+\'0\');
}
inline void pr1(int x){write(x);putchar(\' \');}
inline void pr2(int x){write(x);putchar(\'\\n\');}
const int MAXN=100005;
struct node{int y,next;}a[MAXN*2];int len,last[MAXN];
void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}

int dfn[2*MAXN],dep[MAXN],fir[MAXN],id,mn[25][2*MAXN],bin[25],n,Log[2*MAXN];
void pre_tree_node(int x,int fa)
{
	dfn[++id]=x;fir[x]=id;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			dep[y]=dep[x]+1;
			pre_tree_node(y,x);
			dfn[++id]=x;
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa)
		{
			dep[y]=dep[x]+1;
			pre_tree_node(y,x);
			dfn[++id]=x;
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa)
		{
			dep[y]=dep[x]+1;
			pre_tree_node(y,x);
			dfn[++id]=x;
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa)
		{
			dep[y]=dep[x]+1;
			pre_tree_node(y,x);
			dfn[++id]=x;
		}
	}
}
inline void init()
{
	for(int i=1;i<=id;i++)mn[0][i]=i;
	for(int i=1;bin[i]<=id;i++)
		for(int x=1;x+bin[i]-1<=id;x++)
			mn[i][x]=dep[dfn[mn[i-1][x]]]<dep[dfn[mn[i-1][x+bin[i-1]]]]?mn[i-1][x]:mn[i-1][x+bin[i-1]];
}
inline int lca(int x,int y)
{
	if(fir[x]>fir[y])swap(x,y);
	x=fir[x];y=fir[y];int K=Log[y-x+1];
	return dep[dfn[mn[K][x]]]<dep[dfn[mn[K][y-bin[K]+1]]]?dfn[mn[K][x]]:dfn[mn[K][y-bin[K]+1]];
}
inline int dis(int x,int y)
{
	int LA=lca(x,y);
	return dep[x]+dep[y]-2*dep[LA];
}
//LCA

int cal[MAXN],lin[MAXN],now,nxt;
int rt1[MAXN],rt2[MAXN];


int maxdep,mindep,tim,cnt[MAXN],vi[MAXN]; 
struct segtree
{
	int lc[MAXN*30],rc[MAXN*30],sum[MAXN*30],tot;
	
	void buildtree(int &now,int l,int r)
	{
		if(l>maxdep)return ;
		if(!now)now=++tot;
		if(l==r){sum[now]=cnt[l];return ;}
		int mid=(l+r)/2;
		buildtree(lc[now],l,mid);buildtree(rc[now],mid+1,r);
		sum[now]=sum[lc[now]]+sum[rc[now]];
	}
	void modify(int &now,int l,int r,int p,int c)
	{
		if(!now)now=++tot;sum[now]+=c;
		if(l==r)return ;
		int mid=(l+r)/2;
		if(p<=mid)modify(lc[now],l,mid,p,c);
		else modify(rc[now],mid+1,r,p,c);
	}
	int query(int now,int l,int r,int ql,int qr)
	{
		if(!now)return 0;
		if(l==ql&&r==qr)return sum[now];
		int mid=(l+r)/2;
		if(qr<=mid)return query(lc[now],l,mid,ql,qr);
		else if(mid+1<=ql)return query(rc[now],mid+1,r,ql,qr);
		else return query(lc[now],l,mid,ql,mid)+query(rc[now],mid+1,r,mid+1,qr);
	}
}seg1,seg2;
//seg


bool vis[MAXN];
int refa[MAXN],to[MAXN],mx[MAXN],G,sum;
inline int getsiz(int x,int fa)
{
	int re=1;
	for(register int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa&&vis[y])re+=getsiz(y,x);
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])re+=getsiz(y,x);
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])re+=getsiz(y,x);
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])re+=getsiz(y,x);
		
	}
	return re;
}
inline void go(int x,int fa)
{
	to[x]=mx[x]=1;
	for(register int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa&&vis[y])
		{
			go(y,x);to[x]+=to[y];
			mx[x]=max(mx[x],to[y]);
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])
		{
			go(y,x);to[x]+=to[y];
			mx[x]=max(mx[x],to[y]);
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])
		{
			go(y,x);to[x]+=to[y];
			mx[x]=max(mx[x],to[y]);
		}
		k=a[k].next;if(!k)break;
		y=a[k].y;
		if(y!=fa&&vis[y])
		{
			go(y,x);to[x]+=to[y];
			mx[x]=max(mx[x],to[y]);
		}
	}
	mx[x]=max(mx[x],sum-to[x]);
	if(mx[x]<mx[G]||!G)G=x;
}

inline void newnode(int x,int fa,int d)
{
	maxdep=max(maxdep,d);mindep=min(mindep,d);
	if

					

						
继续阅读与本文标签相同的文章
						

														无标签