• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[BZOJ 3221][Codechef FEB13] Obserbing the tree树上询问

admin

11月 28, 2021

[BZOJ 3221]Obserbing the tree树上询问

题目

   小N最近在做关于树的题。今天她想了这样一道题,给定一棵N个节点的树,节点按1~N编号,一开始每个节点上的权值都是0,接下来有M个操作。第一种操作是修改,给出4个整数X,Y,A,B,对于X到Y路径上加上一个首项是A,公差是B的等差数列,因为小N十分谨慎,所以她每做完一个修改操作就会保存一次,初始状态是第0次保存的局面。第二种操作是求和,给出2个整数X,Y,输出X到Y路径上所有节点的权值和。第三种操作是读取之前第X次保存的局面,所有节点的状态回到之前第X次保存的状态。现在请你对每一个求和操作输出答案。

INPUT

第一行2个整数N,M表示节点个数和操作次数。
接下来N-1行每行2个整数Ui,Vi表示了这棵树中Ui和Vi这2个节点间有边相连。
接下来M行每行先有一个字符表示了操作的类型:
如果是’c’,那么代表了一个修改操作,接下来有4个整数X1,Y1,A,B,为了使得询问在线,正确的X=X1 xor上次输出的数,Y=Y1 xor上次输出的数,如果之前没有输出过那么当成0。
如果是’q’,那么代表了一个求和操作,接下来有2个整数X1,Y1,和修改操作一样需要xor上次输出。
如果是’l’,那么代表了一次读取操作,接下来1个整数X1,正确的X=X1 xor上次输出的数。

OUTPUT

对于每一个求和操作,输出求和后的值。

SAMPLE

INPUT

5 7
1 2
2 3
3 4
4 5
c 2 5 2 3
c 3 4 5 10
q 1 3
l 13
q 13 15
l 6
q 6 4

OUTPUT

12

7

7

解题报告

树剖+可持久化线段树区间修改

唯一的重点在于如何处理等差数列,显然这东西是有顺序的,直接树剖抡链子肯定不行,所以我们找到两点间的$LCA$作为中转站,从$x$更新到$LCA$与从$y$更新到$LCA$分开进行,再记录一下深度差,就可以轻松解决这个鬼畜的问题了

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 using namespace std;
  5 typedef long long L;
  6 inline L read(){
  7     L sum(0),f(1);
  8     char ch(getchar());
  9     for(;ch<'0'||ch>'9';ch=getchar())
 10         if(ch=='-')
 11             f=-1;
 12     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
 13     return sum*f;
 14 }
 15 struct edge{
 16     int e;
 17     edge *n;
 18 }a[200005],*pre[100005];
 19 int to;
 20 inline void insert(int s,int e){
 21     a[++to].e=e;
 22     a[to].n=pre[s];
 23     pre[s]=&a[to];
 24 }
 25 int n,m,now,tot;
 26 char op[2];
 27 int dep[100005],size[100005],fa[100005],son[100005];
 28 inline void dfs1(int u){
 29     size[u]=1;
 30     son[u]=0;
 31     dep[u]=dep[fa[u]]+1;
 32     for(edge *i=pre[u];i;i=i->n){
 33         int e(i->e);
 34         if(e!=fa[u]){
 35             fa[e]=u;
 36             dfs1(e);
 37             size[u]+=size[e];
 38             if(size[e]>size[son[u]])
 39                 son[u]=e;
 40         }
 41     }
 42 }
 43 int timee;
 44 int id[100005],top[100005];
 45 inline void dfs2(int u,int rt){
 46     top[u]=rt;
 47     id[u]=++timee;
 48     if(son[u])
 49         dfs2(son[u],rt);
 50     for(edge *i=pre[u];i;i=i->n){
 51         int e(i->e);
 52         if(e!=son[u]&&e!=fa[u])
 53             dfs2(e,e);
 54     }
 55 }
 56 inline int lca(int x,int y){
 57     while(top[x]^top[y]){
 58         if(dep[top[x]]<dep[top[y]])
 59             swap(x,y);
 60         x=fa[top[x]];
 61     }
 62     return dep[x]<dep[y]?x:y;
 63 }
 64 int rt[100005],lch[20000005],rch[20000005];
 65 int cnt;
 66 L sum[20000005],add_sx[20000005],add_gc[20000005];
 67 L ans;
 68 inline void update(int &x,int las,int ll,int rr,L sx,L gc,int l,int r){
 69     x=++cnt;
 70     lch[x]=lch[las];
 71     rch[x]=rch[las];
 72     sum[x]=sum[las];
 73     add_sx[x]=add_sx[las];
 74     add_gc[x]=add_gc[las];
 75     if(ll==l&&r==rr){
 76         add_sx[x]+=sx;
 77         add_gc[x]+=gc;
 78         return;
 79     }
 80     sum[x]+=(sx+sx+gc*(L)(rr-ll))*(rr-ll+1)/2;
 81     int mid((l+r)>>1);
 82     if(rr<=mid)
 83         update(lch[x],lch[las],ll,rr,sx,gc,l,mid);
 84     else
 85         if(mid<ll)
 86             update(rch[x],rch[las],ll,rr,sx,gc,mid+1,r);
 87         else{
 88             update(lch[x],lch[las],ll,mid,sx,gc,l,mid);
 89             update(rch[x],rch[las],mid+1,rr,sx+(mid-ll+1)*gc,gc,mid+1,r);
 90         }
 91 }
 92 inline L query(int x,int ll,int rr,int l,int r){
 93     L ret((add_sx[x]+(ll-l)*add_gc[x]+add_sx[x]+(rr-l)*add_gc[x])*(rr-ll+1)/2);
 94     if(ll==l&&r==rr)
 95         return ret+sum[x];
 96     int mid((l+r)>>1);
 97     if(rr<=mid)
 98         return ret+query(lch[x],ll,rr,l,mid);
 99     if(mid<ll)
100         return ret+=query(rch[x],ll,rr,mid+1,r);
101     return ret+query(lch[x],ll,mid,l,mid)+query(rch[x],mid+1,rr,mid+1,r);
102 }
103 inline void change(int x,int y,L sx,L gc){
104     int f(lca(x,y));
105     L tp1(0),tp2(dep[x]+dep[y]-dep[f]*2+2);
106     while(top[x]^top[f]){
107         tp1+=dep[x]-dep[top[x]]+1;
108         update(rt[now],rt[now],id[top[x]],id[x],sx+(tp1-1)*gc,-gc,1,n);
109         x=fa[top[x]];
110     }
111     while(top[y]^top[f]){
112         tp2-=dep[y]-dep[top[y]]+1;
113         update(rt[now],rt[now],id[top[y]],id[y],sx+(tp2-1)*gc,gc,1,n);
114         y=fa[top[y]];
115     }
116     ++tp1;
117     --tp2;
118     if(dep[x]<dep[y])
119         update(rt[now],rt[now],id[x],id[y],sx+(tp1-1)*gc,gc,1,n);
120     else
121         update(rt[now],rt[now],id[y],id[x],sx+(tp2-1)*gc,-gc,1,n);
122 }
123 inline L ask(int x,int y){
124     L ret(0);
125     while(top[x]^top[y]){
126         if(dep[top[x]]<dep[top[y]])
127             swap(x,y);
128         ret+=query(rt[now],id[top[x]],id[x],1,n);
129         x=fa[top[x]];
130     }
131     if(dep[x]>dep[y])
132         swap(x,y);
133     ret+=query(rt[now],id[x],id[y],1,n);
134     return ret;
135 }
136 int main(){
137     memset(pre,NULL,sizeof(pre));
138     n=read(),m=read();
139     for(int i=1;i<n;++i){
140         int x(read()),y(read());
141         insert(x,y),insert(y,x);
142     }
143     dfs1(1);
144     dfs2(1,1);
145     while(m--){
146         scanf("%s",op);
147         if(op[0]=='c'){
148             L x(read()),y(read()),sx(read()),gc(read());
149             x^=ans,y^=ans;
150             rt[++tot]=rt[now];
151             now=tot;
152             change(x,y,sx,gc);
153         }
154         if(op[0]=='q'){
155             L x(read()),y(read());
156             x^=ans,y^=ans;
157             ans=ask(x,y);
158             printf("%lld
",ans);
159         }
160         if(op[0]=='l'){
161             L x(read());
162             x^=ans;
163             now=x;
164         }
165     }
166 }

View Code

算是真正搞会了可持久化线段树区间修改了,毕竟改了一上午= =

不要问我俩$CE$咋来的,尝试把数组大小多按几个零,或者强行$Replace$ $All$所有的$int$成$L$,把$printf$顺便$Replace$一下,获得$prLf imes 1$,就可以获得$CE imes 2$了QAQ

发表评论

您的电子邮箱地址不会被公开。