bzoj3730震波

这是一道动态点分治好题。
在点分树上，对于每个点，维护两个树状数组，一个维护离点分中心距离不超过某个值的点权和，另一个维护离点分中心的父亲距离不超过某个值的点权和。注意树状数组的大小不必开到联通子树的大小，而是离某个定点的距离最大值就行了。
最后bzoj上好像是rk11？看来跑得还挺快的。

#include
#include 
#include
#include
#include
using namespace std;
const int N=200005;
inline char read() {static const int IN_LEN = 1000000;static char buf[IN_LEN], *s, *t;if (s == t) {t = (s = buf) + fread(buf, 1, IN_LEN, stdin);if (s == t) return -1;}return *s++;
}
template<class T>
inline void read(T &x) {static bool iosig;static char c;for (iosig = false, c = read(); !isdigit(c); c = read()) {if (c == '-') iosig = true;if (c == -1) return;}/* 这里这么写的原因见下 */for (x = 0; isdigit(c); c = read())x = (x + (x << 2) << 1) + (c ^ '0');if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}
template<class T>
inline void print(T x) {static int buf[30], cnt;if (x == 0) {print('0');} else {if (x < 0) print('-'), x = -x;for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;while (cnt) print((char)buf[cnt--]);}
}
inline void flush() {fwrite(obuf, 1, oh - obuf, stdout);
}
struct BIT{int*a,n;inline void init(){a=new int[n];memset(a,0,n<<2);--a;}inline void add(int x,int v){++x;for(register int i=x;i<=n;i+=i&-i)a[i]+=v;}inline int query(int x){++x;register int s=0,i=x;for(;i;i^=i&-i)s+=a[i];return s;}
};
inline void up(int&a,int b){if(ainline int min(int a,int b){return a>b?b:a;}
int n,m,i,v[N],x,y,o,la;
template<class T> struct vec{T *a;int n;void clear(){if(n>0)delete[]a,a=0,n=0;}void push_back(const T&x){if((n&-n)==n){T*_a=new T[n*2+1];memcpy(_a,a,n*sizeof(T));delete[]a;a=_a;}a[n++]=x;}T&operator[](const int&x){return a[x];}inline int size(){return n;}
};
struct tree{struct edge{int to,next;}e[N<<1];int h[N],xb,f[N],sz[N],sum,rt;bool b[N];vecint,int> > d[N];BIT a[N],c[N];inline void addedge(int u,int v){e[++xb]=(edge){v,h[u]},h[u]=xb;e[++xb]=(edge){u,h[v]},h[v]=xb;}void dfs(int x,int fa){sz[x]=f[x]=1;for(int i=h[x];i;i=e[i].next)if(e[i].to!=fa && !b[e[i].to])dfs(e[i].to,x),sz[x]+=sz[e[i].to],up(f[x],sz[e[i].to]);up(f[x],sum-sz[x]);if(f[x]void getdis(int x,int f,int dd){d[x].push_back(make_pair(dd,rt));for(int i=h[x];i;i=e[i].next)if(e[i].to!=f && !b[e[i].to])getdis(e[i].to,x,dd+1);}inline void work(int x){b[x]=1;getdis(x,0,0);int ts=sum;for(int i=h[x];i;i=e[i].next)if(!b[e[i].to])sum=sz[e[i].to]>sz[x]?ts-sz[x]:sz[e[i].to],dfs(e[i].to,rt=0),work(rt);}inline void add(int x,int y){register int i;for(i=d[x].size()-1;i>=0;--i)a[d[x][i].second].add(d[x][i].first,y);for(i=d[x].size()-1;i;--i)c[d[x][i].second].add(d[x][i-1].first,y);}inline void fix(int x){register int i;for(i=d[x].size()-1;i>=0;--i)up(a[d[x][i].second].n,1+d[x][i].first);for(i=d[x].size()-1;i;--i)up(c[d[x][i].second].n,1+d[x][i-1].first);}inline int query(int x,int y){register int i=d[x].size()-1,ans=a[x].query(min(y,a[x].n-1)),p,q;for(;i;--i){p=d[x][i].second,q=d[x][i-1].second;if(y>=d[x][i-1].first){ans+=a[q].query(min(y-d[x][i-1].first,a[q].n-1));ans-=c[p].query(min(y-d[x][i-1].first,c[p].n-1));}}return ans;}inline void prepare(){sum=n,*f=1<<30,dfs(1,0);work(rt);register int i=1;for(;i<=n;++i)fix(i);for(i=1;i<=n;++i)a[i].init(),c[i].init();for(i=1;i<=n;++i)add(i,v[i]);}
}t;
int main(){read(n),read(m);for(i=1;i<=n;++i)read(v[i]);for(i=1;iwhile(m--){read(o),read(x),read(y);x^=la,y^=la;if(o)t.add(x,y-v[x]),v[x]=y;else print(la=t.query(x,y)),print('\n');}return flush(),0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！