T1：森林

树上主席树+启发式合并。

然而好像知道标签就没啥了。在启发式合并时可以顺手求lca

然而这题好像可以时间换空间（回收空间）

T2：影魔

难点在于考虑贡献的来源

考虑一个区间两端点和区间最值（不含端点）的关系

小，中，大：贡献p1

大，小，大：贡献p2

大，中，小：贡献p1

则预处理出每个点左右第一个比它大的数的位置，设为l和r

则l会对r有p2的贡献，l会对i+1～r-1产生p1的贡献，同理r会对l+1~i-1产生p1的贡献。

用线段树维护扫描线，正向，逆向分别扫一遍，先把贡献都加进线段树，扫到某个点时先统计贡献再在线段树中减掉贡献。

具体实现见代码

View Code

T3：世博会

其实难点在于将切比雪夫距离转化为曼哈顿距离，然后主席树维护即可，将两维分开考虑，分别取中位数即可。

T4：Obserbing the tree树上询问

可持久化线段树+标记永久化。在线段树的每个节点维护等差数列的首项和公比，利用标记永久化减少节点数量

新建一个状态类似于主席树的建树，用树剖维护即可（线段树也是按dfs序建的）

  1 #include<bits/stdc++.h>
  2 #define N 200050
  3 #define LL long long
  4 #define int long long
  5 using namespace std;
  6 
  7 int he[N],ne[N<<1],to[N<<1],cnt;
  8 inline void addedge(int x,int y){
  9     to[++cnt]=y;ne[cnt]=he[x];he[x]=cnt;
 10 }
 11 
 12 int n,m;
 13 int rt[N];
 14 int lc[N*200],rc[N*200],tot;
 15 LL sum[N*200],d[N*200],s[N*200];
 16 inline LL cal(int a,int d,LL n){
 17     return a*n+d*(n-1)*n/2;
 18 }
 19 inline void upd(int g,int n){
 20     sum[g]=sum[lc[g]]+sum[rc[g]]+cal(s[g],d[g],n);
 21 }
 22 int merge(int x,int y,int l,int r){
 23     if(!x||!y)return x|y;
 24     s[x]+=s[y];d[x]+=d[y];
 25     if(l^r){
 26         const int m=l+r>>1;
 27         lc[x]=merge(lc[x],lc[y],l,m);
 28         rc[x]=merge(rc[x],rc[y],m+1,r);
 29     }
 30     sum[x]=sum[x]+sum[y];//////
 31     return x;
 32 }
 33 void bl(int g,int l,int r)
 34 {
 35     if(!g)return;
 36     //printf("g:%d l:%d r:%d s:%d d:%d sum:%d
",g,l,r,s[g],d[g],sum[g]);
 37     const int m=l+r>>1;
 38     bl(lc[g],l,m);bl(rc[g],m+1,r);
 39 }
 40 void add(int &g,int l,int r,int x,int y,LL a,LL b)
 41 {
 42     if(l>y||r<x)return;
 43     if(!g)g=++tot;
 44     if(l>=x&&r<=y){
 45         s[g]+=a+b*(l-x);
 46         d[g]+=b;
 47         upd(g,r-l+1);
 48         return;
 49     }
 50     const int m=l+r>>1;
 51     add(lc[g],l,m,x,y,a,b);
 52     add(rc[g],m+1,r,x,y,a,b);
 53     upd(g,r-l+1);
 54 }
 55 LL ask(int g,int l,int r,int x,int y)
 56 {
 57     if(!g||l>y||r<x)return 0;
 58     if(l>=x&&r<=y)return sum[g];
 59     const int m=l+r>>1;
 60     int tl=max(l,x),tr=min(r,y);
 61     LL ret=cal(s[g]+d[g]*(tl-l),d[g],tr-tl+1);
 62     return ret+ask(lc[g],l,m,x,y)+ask(rc[g],m+1,r,x,y);
 63 }
 64 
 65 
 66 int dl[N],dr[N],dep[N],tp[N],hs[N],pos[N],f[N],sz[N];
 67 inline void dfs1(int g,int fa){
 68     dep[g]=dep[fa]+1;sz[g]=1;f[g]=fa;
 69     for(int i=he[g];i;i=ne[i]){
 70         if(to[i]^fa){
 71             dfs1(to[i],g);
 72             if(sz[to[i]]>sz[hs[g]])hs[g]=to[i];
 73             sz[g]+=sz[to[i]];
 74         }
 75     }
 76 }
 77 inline void dfs2(int g,int fa){
 78     dl[g]=dr[g]=++cnt;pos[cnt]=g;
 79     tp[g]=g==hs[fa]?tp[fa]:g;
 80     if(hs[g])dfs2(hs[g],g);
 81     for(int i=he[g];i;i=ne[i])
 82         if(!dl[to[i]])dfs2(to[i],g);
 83 }
 84 inline int LCA(int x,int y){
 85     while(tp[x]!=tp[y]){
 86         if(dep[tp[x]]>dep[tp[y]])swap(x,y);
 87         y=f[tp[y]];
 88     }
 89     if(dep[x]<dep[y])return x;return y;
 90 }
 91 
 92 
 93 inline void work(int &g,int fr,int to,LL a,LL b)
 94 {
 95     if(dep[fr]<dep[to])return;
 96     while(tp[fr]!=tp[to]){
 97         add(g,1,n,dl[tp[fr]],dl[fr],a+b*(dl[fr]-dl[tp[fr]]),-b);
 98         a+=b*(dl[fr]-dl[tp[fr]]+1);
 99         fr=f[tp[fr]];
100     }
101     add(g,1,n,dl[to],dl[fr],a+b*(dl[fr]-dl[to]),-b);
102 }
103 inline LL getans(int g,int fr,int to)
104 {
105     LL ret=0;
106     while(tp[fr]!=tp[to]){
107         ret+=ask(g,1,n,dl[tp[fr]],dl[fr]);
108         fr=f[tp[fr]];
109     }
110     ret+=ask(g,1,n,dl[to],dl[fr]);
111     return ret;
112 }
113 main()
114 {
115 
116     scanf("%lld%lld",&n,&m);
117     for(int i=1,x,y;i<n;++i){
118         scanf("%lld%lld",&x,&y);
119         addedge(x,y);addedge(y,x);
120     }
121     cnt=0;dfs1(1,0);dfs2(1,0);
122     char s[3];int x,y,a,b;LL lasans=0,ts=0,now=0;
123     while(m--)
124     {
125         scanf("%s",s);
126         if(s[0]=='c'){
127             scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
128             x^=lasans;y^=lasans;
129             ++ts;
130             int lca=LCA(x,y),dis=dep[x]+dep[y]-dep[lca]-dep[lca];
131 //            printf("%d %d %d
",x,y,lca);
132             work(rt[ts],x,lca,a,b);
133             work(rt[ts],y,lca,a+b*dis,-b);
134             add(rt[ts],1,n,dl[lca],dl[lca],-(a+(dep[x]-dep[lca])*b),0);
135             rt[ts]=merge(rt[ts],rt[now],1,n);
136 //            bl(rt[ts],1,n);
137             now=ts;
138         }
139         else if(s[0]=='q'){
140             scanf("%lld%lld",&x,&y);
141             x^=lasans;y^=lasans;
142             int lca=LCA(x,y);
143             lasans=getans(rt[now],x,lca)+getans(rt[now],y,lca)-getans(rt[now],lca,lca);
144             printf("%lld
",lasans);
145         }
146         else{
147             scanf("%lld",&now);
148             now^=lasans;
149         }
150     }
151     return 0;
152 }

View Code

T5：Alo

此题考察可持久化trie+RMQ

因为要取区间次大值，所以要找出以每个数作次大值的区间即可，

对于每个数，先找到右面第一个比它大的，然后再向右找到第二个比它大的，这个过程可以用二分+rmq实现，这样就得到了它作为次大值的右端点，reverse一下就得到了左端点，用trie在区间找到最值即可

T5：最大异或和

可持久化trie的板子题