COJ 1008 WZJ的数据结构（八）树上操作

传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=986

WZJ的数据结构（八）

难度级别：E；运行时间限制：3000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

给你一个N个节点的森林，从1到N编号，每个点有权值。请你设计一个数据结构，进行以下两种操作：

1.修改：给你a、b、c，将a到b路径上所有点的权值改成c。

2.增加：给你a、b、c，将a到b路径上所有点的权值增加c。

3.询问：给你a、b，输出从a到b路径上经过所有点权值的最大值、最小值与权值和。

输入

第一行为一个正整数N。
接下来N-1行为每一条边，每行2个正整数a，b，表示有一条从a到b的边（从1开始编号）。
第N+1行为n个正整数Ai,表示每个点的开始权值。
第N+2行为一个正整数Q,表示Q次操作。
接下来Q行为每一次询问，每行3或4个正整数(t)、a、b、c。
若t=0表示修改，t=1表示增加，t=2表示查询。

输出

对于每一次询问，输出结果。

输入示例

5
1 2
1 3
2 5
5 4
1 3 2 3 5
5
2 1 5
2 3 4
0 3 5 2
1 1 4 1
2 3 4

输出示例

5 1 9
5 1 14
4 2 15

其他说明

1<=N<=100000
1<=Q<=100000
1<=Ai<=1000
1<=a,b<=N 1<=c<=1000

题解：树链剖分直接套上1010好了。。。

更新：指针的线段树+邻接表：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 #define CH for(int d=0;d<=1;d++) if(ch[d])

 #define lson x->ch[0],L,M

 #define rson x->ch[1],M+1,R

 using namespace std;

 const int maxn=+,inf=-1u>>;

 struct node{

     node*ch[];int mx,mi,sm,set,add,siz;

     node(){set=inf;add=;}

     void init(int t){mi=mx=sm=t;return;}

     void addt(int tag){

         mi+=tag;mx+=tag;sm+=tag*siz;add+=tag;return;

     }

     void sett(int tag){

         add=;mi=mx=set=tag;sm=siz*tag;return;

     }

     void update(){

         mi=inf;mx=-inf;sm=;

         CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}

         return;

     }

     void down(){

         if(set!=inf){CH{ch[d]->sett(set);}set=inf;}

         if(add){CH{ch[d]->addt(add);}add=;}

         return;

     }

 }seg[maxn<<],*nodecnt=seg,*root;

 int A[maxn],n,Q,ql,qr,cv,tp,_mi,_mx,_sm;

 void build(node*&x,int L,int R){

     x=nodecnt++;

     if(L==R) x->init(A[L]);

     else{

         int M=L+R>>;

         build(lson);build(rson);

         x->update();

     } x->siz=R-L+;return;

 }

 void update(node*&x,int L,int R){

     if(ql<=L&&R<=qr){

         if(tp) x->addt(cv);

         else x->sett(cv);

     }else{

         int M=L+R>>;

         x->down();

         if(ql<=M) update(lson);

         if(qr>M) update(rson);

         x->update();

     } return;

 }

 void query(node*x,int L,int R){

     if(ql<=L&&R<=qr){

         _mi=min(_mi,x->mi);

         _mx=max(_mx,x->mx);

         _sm+=x->sm;

     }else{

         int M=L+R>>;

         x->down();

         if(ql<=M) query(lson);

         if(qr>M) query(rson);

     } return;

 }

 struct ted{int x,y;ted*nxt;}adj[maxn<<],*fch[maxn],*ms=adj;

 void ade(int x,int y){

     *ms=(ted){x,y,fch[x]};fch[x]=ms++;

     *ms=(ted){y,x,fch[y]};fch[y]=ms++;

     return;

 }

 int dep[maxn],p[maxn],son[maxn],top[maxn],siz[maxn],fa[maxn],cz=;

 void dfs(int x){

     siz[x]=;dep[x]=dep[fa[x]]+;

     for(ted*e=fch[x];e;e=e->nxt){

         int v=e->y;if(v!=fa[x]){

             fa[v]=x;dfs(v);siz[x]+=siz[v];

             if(siz[son[x]]<siz[v]) son[x]=v;

         }

     } return;

 }

 void build(int x,int tp){

     p[x]=++cz;top[x]=tp;

     if(son[x]) build(son[x],tp);

     for(ted*e=fch[x];e;e=e->nxt){

         int v=e->y;

         if(v!=fa[x]&&v!=son[x]) build(v,v);

     } return;

 }

 void update(int x,int y){

     int f1=top[x],f2=top[y];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);

         ql=p[f1];qr=p[x];update(root,,n);

         x=fa[f1];f1=top[x];

     } if(dep[x]>dep[y]) swap(x,y);

     ql=p[x];qr=p[y];update(root,,n);return;

 }

 void query(int x,int y){

     int f1=top[x],f2=top[y];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);

         ql=p[f1];qr=p[x];query(root,,n);

         x=fa[f1];f1=top[x];

     } if(dep[x]>dep[y]) swap(x,y);

     ql=p[x];qr=p[y];query(root,,n);return;

 }

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}

     while(isdigit(ch))x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     n=read();

     for(int i=;i<n;i++) ade(read(),read());

     dfs();build(,);

     for(int i=;i<=n;i++) A[p[i]]=read();

     build(root,,n);

     return;

 }

 void work(){

     Q=read();int x,y;

     while(Q--){

         tp=read();x=read();y=read();

         if(tp!=) cv=read(),update(x,y);

         else{

             _mi=inf;_mx=-inf;_sm=;query(x,y);

             write(_mx);PAU;write(_mi);PAU;write(_sm);ENT;

         }

     }

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

数组线段树：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,maxn3=+,inf=-1u>>;

 struct Tedge{int x,y,next;}adj[maxn*];int ms=,fch[maxn];

 int n,Q;

 void AddEdge(int v,int u){

     adj[++ms]=(Tedge){u,v,fch[u]};fch[u]=ms;

     adj[++ms]=(Tedge){v,u,fch[v]};fch[v]=ms;

     return;

 }

 int maxv[maxn3],minv[maxn3],sumv[maxn3],setv[maxn3],addv[maxn3],A[maxn];

 void pushup(int o,int lc,int rc){

     minv[o]=min(minv[lc],minv[rc]);

     maxv[o]=max(maxv[lc],maxv[rc]);

     sumv[o]=sumv[lc]+sumv[rc];

     return;

 }

 void pushdown(int o,int lc,int rc){

     if(setv[o]>=){

         setv[lc]=setv[rc]=setv[o];

         addv[lc]=addv[rc]=;

         setv[o]=-;

     } if(addv[o]){

         addv[lc]+=addv[o];

         addv[rc]+=addv[o];

         addv[o]=;

     } return;

 }

 void maintain(int o,int L,int R){

     int lc=o<<,rc=lc|;

     if(L<R&&setv[o]<) pushup(o,lc,rc);

     if(setv[o]>=){

         minv[o]=maxv[o]=setv[o];

         sumv[o]=(R-L+)*setv[o];

     } if(addv[o]){

         minv[o]+=addv[o];

         maxv[o]+=addv[o];

         sumv[o]+=(R-L+)*addv[o];

     } return;

 }

 int _min,_max,_sum,ql,qr,tp,cv;

 void update(int o,int L,int R){

     if(ql<=L&&R<=qr){

         if(tp) addv[o]+=cv;

         else setv[o]=cv,addv[o]=;

     } else{

         int M=L+R>>,lc=o<<,rc=lc|;

         pushdown(o,lc,rc);

         if(ql<=M) update(lc,L,M); else maintain(lc,L,M);

         if(qr>M) update(rc,M+,R); else maintain(rc,M+,R);

     } maintain(o,L,R);return;

 }

 void build(int o,int L,int R){

     if(L==R) setv[o]=A[L];

     else{

         int M=L+R>>,lc=o<<,rc=lc|;

         build(lc,L,M);build(rc,M+,R);

     } maintain(o,L,R);return;

 }

 void query(int o,int L,int R,int add){

     if(setv[o]>=){

         int change=setv[o]+addv[o]+add;

         _sum+=(min(R,qr)-max(L,ql)+)*change;

         _min=min(_min,change);

         _max=max(_max,change);

     } else if(ql<=L&&R<=qr){

         _sum+=sumv[o]+(R-L+)*add;

         _min=min(_min,minv[o]+add);

         _max=max(_max,maxv[o]+add);

     } else{

         int M=L+R>>,lc=o<<,rc=lc|;

         if(ql<=M) query(lc,L,M,add+addv[o]);

         if(M<qr) query(rc,M+,R,add+addv[o]);

     } return;

 }

 int dep[maxn],siz[maxn],top[maxn],p[maxn],fa[maxn],son[maxn];

 void dfs(int u){

     siz[u]=;dep[u]=dep[fa[u]]+;

     for(int i=fch[u];i;i=adj[i].next){

         int v=adj[i].y;

         if(v!=fa[u]){

             fa[v]=u;dfs(v);

             if(siz[son[u]]<siz[v]) son[u]=v;

             siz[u]+=siz[v];

         }

     } return;

 }

 int cz=;

 void build(int u,int tp){

     p[u]=++cz;top[u]=tp;

     if(son[u]) build(son[u],tp);

     for(int i=fch[u];i;i=adj[i].next){

         int v=adj[i].y;

         if(v!=fa[u]&&v!=son[u]) build(v,v);

     } return;

 }

 void query(int a,int b){

     int f1=top[a],f2=top[b];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(a,b),swap(f1,f2);

         ql=p[f1];qr=p[a];query(,,n,);

         a=fa[f1];f1=top[a];

     }

     if(dep[a]>dep[b]) swap(a,b);

     ql=p[a];qr=p[b];query(,,n,);return;

 }

 void update(int a,int b){

     int f1=top[a],f2=top[b];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(a,b),swap(f1,f2);

         ql=p[f1];qr=p[a];update(,,n);

         a=fa[f1];f1=top[a];

     }

     if(dep[a]>dep[b]) swap(a,b);

     ql=p[a];qr=p[b];update(,,n);return;

 }

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}

     while(isdigit(ch))x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     memset(setv,-,sizeof(setv));

     n=read();

     for(int i=;i<n;i++) AddEdge(read(),read());

     dfs();build(,);

     for(int i=;i<=n;i++) A[p[i]]=read();//这么写跑的更快

     build(,,n);

     /*for(int i=1;i<=n;i++){//这样慢

         ql=qr=p[i];cv=read();

         update(1,1,n);

     }*/

     Q=read();

     return;

 }

 void work(){

     int a,b;

     while(Q--){

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

         if(tp==){//query

             _sum=;_min=inf;_max=-inf;

             query(a,b);

             write(_max);PAU;write(_min);PAU;write(_sum);ENT;

         } else cv=read(),update(a,b);

     }

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

大数据跑LCT还是快：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,inf=-1u>>;

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}

     while(isdigit(ch))x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 struct node {

     node *ch[],*fa;

     bool rev;

     int x,sm,siz,add,mi,mx,set;

     inline void add_rev_tag(){

         swap(ch[],ch[]);rev^=;return;

     }

     inline void add_plus_tag(int a){

         sm+=siz*a;x+=a;add+=a;

         if(mi!=inf) mi+=a;

         if(mx!=-inf) mx+=a;

         return;

     }

     inline void add_set_tag(int a){

         x=set=a;add=;sm=a*siz;

         if(mi!=inf) mi=set;

         if(mx!=-inf) mx=set;

     }

     inline void down(){

         if(rev){

             if(ch[]) ch[]->add_rev_tag();

             if(ch[]) ch[]->add_rev_tag();

             rev=;

         }

         if(set){

             if(ch[]) ch[]->add_set_tag(set);

             if(ch[]) ch[]->add_set_tag(set);

             set=;

         }

         if(add){

             if(ch[]) ch[]->add_plus_tag(add);

             if(ch[]) ch[]->add_plus_tag(add);

             add=;

         }

         return;

     }

     inline void update(){

         sm=;siz=;mi=inf;mx=-inf;

         if(ch[]) sm+=ch[]->sm,siz+=ch[]->siz,mi=min(mi,ch[]->mi),mx=max(mx,ch[]->mx);

         if(ch[]) sm+=ch[]->sm,siz+=ch[]->siz,mi=min(mi,ch[]->mi),mx=max(mx,ch[]->mx);

         if(!x) return;

         mi=min(x,mi);

         mx=max(x,mx);

         sm+=x;

         return;

     }

 }lct[maxn];

 inline int get_parent(node *x,node *&fa){return (fa=x->fa)?fa->ch[]==x?:fa->ch[]==x?:-:-;}

 inline void rotate(node *x){

     int t1,t2;

     node *fa,*gfa;

     t1=get_parent(x,fa);

     t2=get_parent(fa,gfa);

     if ((fa->ch[t1]=x->ch[t1^])) fa->ch[t1]->fa=fa;

     x->ch[t1^]=fa;fa->fa=x;x->fa=gfa;

     if (t2!=-) gfa->ch[t2]=x;

     fa->update();return;

 }

 inline void pushdown(node *x){

     static node *stack[maxn];

     int cnt=;

     while(){

         stack[cnt++]=x;

         node *fa=x->fa;

         if (!fa || (fa->ch[]!=x && fa->ch[]!=x)) break;

         x=fa;

     }

     while(cnt--) stack[cnt]->down();

     return;

 }

 inline node * splay(node *x){

     pushdown(x);

     while(){

         int t1,t2;

         node *fa,*gfa;

         t1=get_parent(x,fa);

         if(t1==-) break;

         t2=get_parent(fa,gfa);

         if(t2==-){

             rotate(x);break;

         } else if (t1==t2){

             rotate(fa);rotate(x);

         } else{

             rotate(x);rotate(x);

         }

     }

     x->update();

     return x;

 }

 inline node * access(node *x){

     node *ret=NULL;

     while (x) splay(x)->ch[]=ret,(ret=x)->update(),x=x->fa;

     return ret;

 }

 inline void makeroot(int x){access(lct+x)->add_rev_tag();}

 inline void link(int u,int v){

     makeroot(u);splay(lct+u)->fa=lct+v;return;

 }

 inline void cut(int u,int v){

     makeroot(u);

     node *p=(access(lct+v),splay(lct+v));

     p->ch[]->fa=NULL;

     p->ch[]=NULL;

     p->update();

 }

 int n,q;

 int main(){

     n=read();

     int i;

     for(i=;i<=n;i++){

         lct[i].x=lct[i].sm=;

         lct[i].siz=;

         lct[i].add=;

         lct[i].mi=inf;

         lct[i].mx=-inf;

         lct[i].set=;

     }

     for(i=;i<n;i++){

         int u,v;

         u=read();v=read();

         link(u,v);

     }

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

         lct[i].x=read();lct[i].update();

     }

     q=read();

     int x,y,c;

     while(q--){

         c=read();x=read();y=read();

         if(c==) makeroot(x),access(y+lct)->add_set_tag(read());

         else if(c==) makeroot(x),access(y+lct)->add_plus_tag(read());

         else{

             makeroot(x);node*t=access(y+lct);splay(t);

             write(t->mx);PAU;write(t->mi);PAU;write(t->sm);ENT;

         }

     }

     return ;

 }

搜索

复制

巴特西

COJ 1008 WZJ的数据结构（八）树上操作

最新文章

热门文章

巴特西

COJ 1008 WZJ的数据结构（八） 树上操作

最新文章

热门文章

COJ 1008 WZJ的数据结构（八）树上操作