线段树
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define N 300005 5 int n,tp,c[N],mn[N],mx[N],s[N<<2],tg[N<<2];ll res; 6 void down(int x,int l,int r){if(tg[x]){int mid=l+r>>1;s[x<<1]=mid-l+1;s[x<<1|1]=r-mid;tg[x<<1]=tg[x<<1|1]=1;tg[x]=0;}} 7 void build(int x,int l,int r) 8 { 9 s[x]=tg[x]=0; 10 if(l==r)return; 11 int mid=l+r>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r); 12 } 13 void upd(int x,int l,int r,int tl,int tr) 14 { 15 if(tl>tr)return; 16 if(tl<=l&&r<=tr){s[x]=r-l+1;tg[x]=1;return;} 17 int mid=l+r>>1;down(x,l,r); 18 if(tl<=mid)upd(x<<1,l,mid,tl,tr); 19 if(tr>mid)upd(x<<1|1,mid+1,r,tl,tr); 20 s[x]=s[x<<1]+s[x<<1|1]; 21 } 22 int qry(int x,int l,int r,int tl,int tr) 23 { 24 if(tl>tr)return 0; 25 if(tl<=l&&r<=tr)return s[x]; 26 int mid=l+r>>1,rr=0;down(x,l,r); 27 if(tl<=mid)rr+=qry(x<<1,l,mid,tl,tr); 28 if(tr>mid)rr+=qry(x<<1|1,mid+1,r,tl,tr); 29 return rr; 30 } 31 struct st{int c,p;}stk[N]; 32 void sol() 33 { 34 scanf("%d",&n);res=0;tp=0; 35 for(int i=1;i<=n;i++)scanf("%d",&c[i]); 36 build(1,1,n); 37 for(int i=1;i<=n;i++)mn[i]=n+1,mx[i]=0; 38 for(int i=1;i<=n;i++)mn[c[i]]=min(mn[c[i]],i),mx[c[i]]=max(mx[c[i]],i); 39 for(int i=1;i<=n;i++) 40 { 41 if(i==mx[c[i]])upd(1,1,n,mn[c[i]]+1,mx[c[i]]);//mx[c[i]]>mn[c[i]] 42 else stk[++tp]=(st){c[i],i}; 43 while(tp&&mx[stk[tp].c]<=i)tp--; 44 int l=!tp?0:stk[tp].p; 45 if(i>l)res+=i-l-qry(1,1,n,l+1,i); 46 } 47 printf("%lld ",res); 48 } 49 int main() 50 { 51 int T;scanf("%d",&T); 52 while(T--)sol(); 53 return 0; 54 }
线段树合并
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 int n,m,cc,fa[N][22],dep[N],ans[N],ls[40*N],rs[40*N],rt[N]; 5 struct st{int x,y;}T[40*N]; 6 st operator+(st a,st b){return a.x==b.x?(st){a.x,min(a.y,b.y)}:(a.x<b.x?b:a);} 7 vector<st>gg[N]; 8 vector<int>g[N]; 9 void upd(int &x,int l,int r,int p,int v) 10 { 11 if(!x)x=++cc; 12 if(l==r){T[x].x+=v;T[x].y=l;return;} 13 int mid=l+r>>1; 14 if(p<=mid)upd(ls[x],l,mid,p,v);else upd(rs[x],mid+1,r,p,v); 15 T[x]=T[ls[x]]+T[rs[x]]; 16 } 17 int merge(int x,int y,int l,int r) 18 { 19 if(!x||!y)return x|y; 20 if(l==r){T[x].x+=T[y].x;return x;} 21 int mid=l+r>>1; 22 ls[x]=merge(ls[x],ls[y],l,mid); 23 rs[x]=merge(rs[x],rs[y],mid+1,r); 24 T[x]=T[ls[x]]+T[rs[x]]; 25 return x; 26 } 27 void dfs1(int x,int p) 28 { 29 fa[x][0]=p;dep[x]=dep[p]+1; 30 for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)dfs1(g[x][i],x); 31 } 32 int lca(int u,int v) 33 { 34 if(dep[u]<dep[v])swap(u,v); 35 int sub=dep[u]-dep[v]; 36 for(int i=17;i>=0;i--)if(sub>>i&1)u=fa[u][i]; 37 if(u==v)return u; 38 for(int i=17;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i]; 39 return fa[u][0]; 40 } 41 void dfs2(int x,int p) 42 { 43 for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)dfs2(g[x][i],x); 44 for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)rt[x]=merge(rt[x],rt[g[x][i]],0,1e5); 45 for(int i=0;i<gg[x].size();i++)upd(rt[x],0,1e5,gg[x][i].x,gg[x][i].y); 46 ans[x]=T[rt[x]].y; 47 } 48 int main() 49 { 50 scanf("%d%d",&n,&m);cc=n; 51 for(int i=1;i<=n;i++)rt[i]=i; 52 for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u); 53 dfs1(1,0); 54 for(int i=1;i<=17;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; 55 for(int i=1,u,v,w;i<=m;i++) 56 { 57 scanf("%d%d%d",&u,&v,&w);int t=lca(u,v); 58 gg[u].push_back((st){w,1});gg[v].push_back((st){w,1}); 59 gg[t].push_back((st){w,-1});gg[fa[t][0]].push_back((st){w,-1}); 60 } 61 dfs2(1,0); 62 for(int i=1;i<=n;i++)printf("%d ",ans[i]); 63 return 0; 64 }
线段树分治
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define N 100005 5 struct trie 6 { 7 int nn,sz[N*20],ch[N*20][2]; 8 void ins(int &x,int y,int p,int d) 9 { 10 sz[x=++nn]=sz[y]+1; 11 if(d==-1)return; 12 int t=p>>d&1;ch[x][t^1]=ch[y][t^1]; 13 ins(ch[x][t],ch[y][t],p,d-1); 14 } 15 int qry(int x,int y,int p,int d) 16 { 17 if(d==-1)return 0; 18 int t=p>>d&1; 19 if(sz[ch[y][t^1]]-sz[ch[x][t^1]])return qry(ch[x][t^1],ch[y][t^1],p,d-1)|(1<<d); 20 else return qry(ch[x][t],ch[y][t],p,d-1); 21 } 22 }T; 23 struct k1{int l,r,x,tl,tr;}qq[N]; 24 struct k2{int s,v,t;}q[N<<2],q1[N<<2],q2[N<<2]; 25 bool cmp(k2 a,k2 b){return a.s<b.s;} 26 vector<int>g[N<<2]; 27 void upd(int x,int l,int r,int tl,int tr,int v) 28 { 29 if(tl>tr)return; 30 if(tl<=l&&r<=tr){g[x].push_back(v);return;} 31 int mid=l+r>>1; 32 if(tl<=mid)upd(x<<1,l,mid,tl,tr,v); 33 if(tr>mid)upd(x<<1|1,mid+1,r,tl,tr,v); 34 } 35 int cc,tt,tp,rt[N],ans[N],st[N]; 36 void calc(int x,int tl,int tr) 37 { 38 tp=T.nn=0; 39 for(int i=tl;i<=tr;i++) 40 { 41 st[++tp]=q[i].s; 42 T.ins(rt[tp],rt[tp-1],q[i].v,17); 43 } 44 for(int i=0;i<g[x].size();i++) 45 { 46 int p=g[x][i],l=upper_bound(st+1,st+tp+1,qq[p].l-1)-st-1,r=upper_bound(st+1,st+tp+1,qq[p].r)-st-1; 47 ans[p]=max(ans[p],T.qry(rt[r],rt[l],qq[p].x,17)); 48 } 49 } 50 void sol(int x,int l,int r,int tl,int tr) 51 { 52 if(tl>tr)return; 53 calc(x,tl,tr); 54 if(l==r)return; 55 int mid=l+r>>1,t1=0,t2=0; 56 for(int i=tl;i<=tr;i++)if(q[i].t<=mid)q1[++t1]=q[i];else q2[++t2]=q[i]; 57 for(int i=1;i<=t1;i++)q[tl+i-1]=q1[i]; 58 for(int i=1;i<=t2;i++)q[tl+t1+i-1]=q2[i]; 59 sol(x<<1,l,mid,tl,tl+t1-1);sol(x<<1|1,mid+1,r,tl+t1,tr); 60 } 61 int main() 62 { 63 int n,m; 64 scanf("%d%d",&n,&m); 65 for(int i=1,x;i<=n;i++)scanf("%d",&x),T.ins(rt[i],rt[i-1],x,17); 66 for(int i=1,a,b,c,d,o;i<=m;i++) 67 { 68 scanf("%d%d%d",&o,&a,&b); 69 if(!o)cc++,q[cc]=(k2){a,b,cc}; 70 else{scanf("%d%d",&c,&d);qq[++tt]=(k1){a,b,c,max(1,cc-d+1),cc};ans[tt]=T.qry(rt[a-1],rt[b],c,17);} 71 } 72 for(int i=1;i<=tt;i++)upd(1,1,cc,qq[i].tl,qq[i].tr,i); 73 sort(q+1,q+cc+1,cmp);sol(1,1,cc,1,cc); 74 for(int i=1;i<=tt;i++)printf("%d ",ans[i]); 75 return 0; 76 }
树链剖分
动态dp
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define inf 1000000000 5 int n,m,id=0,w[N],dep[N],tp[N],fa[N],sz[N],sn[N],dfn[N],idfn[N],rr[N]; 6 vector<int>g[N]; 7 struct mat 8 { 9 int r,c,a[2][2]; 10 inline mat(){memset(a,0,sizeof(a));} 11 mat operator*(const mat&b)const 12 { 13 mat c;c.r=r;c.c=b.c; 14 for(int i=0;i<r;i++)for(int j=0;j<c.c;j++)for(int k=0;k<b.r;k++)c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]); 15 return c; 16 } 17 }d[N<<2],s[N]; 18 mat qry(int x,int l,int r,int tl,int tr) 19 { 20 if(tl<=l&&r<=tr)return d[x]; 21 int mid=l+r>>1; 22 if(tl<=mid&&mid<tr)return qry(x<<1|1,mid+1,r,tl,tr)*qry(x<<1,l,mid,tl,tr); 23 if(tl<=mid)return qry(x<<1,l,mid,tl,tr); 24 if(mid<tr)return qry(x<<1|1,mid+1,r,tl,tr); 25 } 26 void upd(int x,int l,int r,int p,mat v) 27 { 28 if(l==r){d[x]=v;return;} 29 int mid=l+r>>1; 30 if(p<=mid)upd(x<<1,l,mid,p,v);else upd(x<<1|1,mid+1,r,p,v); 31 d[x]=d[x<<1|1]*d[x<<1]; 32 } 33 void dfs1(int x) 34 { 35 sz[x]=1;sn[x]=0; 36 for(int i=0;i<g[x].size();i++)if(g[x][i]!=fa[x]) 37 { 38 dep[g[x][i]]=dep[x]+1;fa[g[x][i]]=x; 39 dfs1(g[x][i]);sz[x]+=sz[g[x][i]]; 40 if(!sn[x]||sz[g[x][i]]>sz[sn[x]])sn[x]=g[x][i]; 41 } 42 } 43 void dfs2(int x) 44 { 45 idfn[dfn[x]=++id]=x; 46 if(sn[x])tp[sn[x]]=tp[x],dfs2(sn[x]); 47 for(int i=0;i<g[x].size();i++)if(g[x][i]!=sn[x]&&g[x][i]!=fa[x]){tp[g[x][i]]=g[x][i];dfs2(g[x][i]);} 48 rr[x]=(sn[x]?rr[sn[x]]:x); 49 } 50 void calc(int x) 51 { 52 stack<int>st; 53 for(int i=x;i;i=sn[i])st.push(i); 54 while(!st.empty()) 55 { 56 int t=st.top();st.pop(); 57 int x=0,y=w[t]; 58 for(int i=0;i<g[t].size();i++)if(g[t][i]!=fa[t]&&g[t][i]!=sn[t]) 59 { 60 calc(g[t][i]);mat q=s[g[t][i]]; 61 x+=max(q.a[0][0],q.a[0][1]); 62 y+=q.a[0][0]; 63 } 64 mat m;m.r=m.c=2; 65 m.a[0][0]=m.a[1][0]=x; 66 m.a[0][1]=y;m.a[1][1]=-inf; 67 upd(1,1,n,dfn[t],m); 68 } 69 s[x]=qry(1,1,n,dfn[x],dfn[rr[x]]); 70 } 71 void chg(int x,int v) 72 { 73 mat p=qry(1,1,n,dfn[x],dfn[x]); 74 p.a[0][1]+=v-w[x];upd(1,1,n,dfn[x],p);w[x]=v; 75 for(int t=tp[x],f;t!=1;t=tp[f]) 76 { 77 f=fa[t]; 78 p=qry(1,1,n,dfn[f],dfn[f]); 79 mat q=qry(1,1,n,dfn[t],dfn[rr[t]]); 80 p.a[0][0]+=max(q.a[0][0],q.a[0][1])-max(s[t].a[0][0],s[t].a[0][1]); 81 p.a[0][1]+=q.a[0][0]-s[t].a[0][0]; 82 p.a[1][0]=p.a[0][0]; 83 upd(1,1,n,dfn[f],p); 84 s[t]=q; 85 } 86 } 87 int main() 88 { 89 scanf("%d%d",&n,&m); 90 for(int i=1;i<=n;i++)scanf("%d",&w[i]); 91 for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);} 92 dfs1(dep[1]=1);dfs2(tp[1]=1);calc(1); 93 while(m--) 94 { 95 int x,y;scanf("%d%d",&x,&y);chg(x,y); 96 mat p=qry(1,1,n,1,dfn[rr[1]]); 97 printf("%d ",max(p.a[0][0],p.a[0][1])); 98 } 99 return 0; 100 }
长链剖分
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=30005; 4 struct T{int f,c;T(){f=0;c=1;}}dp[N],*f[N],*e=dp+1; 5 int K,cc,ans1,ans2,hd[N],nxt[N],to[N],vis[N],dist[N],dep[N],mx[N],fa[N],sn[N],w[N]; 6 vector<pair<int,int> >g[N]; 7 priority_queue<pair<int,int> >q; 8 inline void add(int u,int v){nxt[++cc]=hd[u];hd[u]=cc;to[cc]=v;vis[v]=0;fa[v]=u;} 9 void dfs1(int x) 10 { 11 for(int i=0;i<g[x].size();i++) 12 { 13 int y=g[x][i].first,z=g[x][i].second; 14 if(vis[y]&&dist[x]+z==dist[y])add(x,y),w[y]=z,dfs1(y); 15 } 16 } 17 void dfs2(int x) 18 { 19 mx[x]=dep[x]=dep[fa[x]]+1; 20 for(int i=hd[x];i;i=nxt[i]) 21 { 22 int y=to[i];dfs2(y); 23 if(mx[y]>mx[x])mx[x]=mx[y],sn[x]=y; 24 } 25 } 26 void dfs(int x) 27 { 28 f[x][0].c=1;int v; 29 if(!sn[x])return; 30 f[sn[x]]=f[x]+1;dfs(sn[x]); 31 w[x]+=(v=w[sn[x]]);f[x][0].f-=v; 32 if(mx[x]-dep[x]>=K+1) 33 { 34 int len=f[x][K+1].f+v; 35 if(len>ans1)ans1=len,ans2=f[x][K+1].c;else if(len==ans1)ans2+=f[x][K+1].c; 36 } 37 for(int i=hd[x];i;i=nxt[i]) 38 { 39 int y=to[i];if(y==sn[x])continue; 40 f[y]=e;int lim=mx[y]-dep[y]+1;e+=lim; 41 dfs(y);int u=w[y]; 42 for(int j=max(K-mx[x]+dep[x],0);j<lim&&j<=K;j++) 43 { 44 int len=f[y][j].f+f[x][K-j].f+u+v; 45 if(len>ans1)ans1=len,ans2=f[y][j].c*f[x][K-j].c;else if(len==ans1)ans2+=f[y][j].c*f[x][K-j].c; 46 } 47 for(int j=0;j<lim;j++) 48 { 49 int len=f[y][j].f+u-v; 50 if(len>f[x][j+1].f)f[x][j+1].f=len,f[x][j+1].c=f[y][j].c;else if(len==f[x][j+1].f)f[x][j+1].c+=f[y][j].c; 51 } 52 } 53 } 54 int main() 55 { 56 int n,m;scanf("%d%d%d",&n,&m,&K);K-=2; 57 for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),g[u].push_back(make_pair(v,w)),g[v].push_back(make_pair(u,w)); 58 for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end()); 59 memset(dist,0x3f,sizeof(dist));dist[1]=0;q.push(make_pair(0,1)); 60 while(!q.empty()) 61 { 62 int x=q.top().second;q.pop(); 63 if(vis[x])continue;vis[x]=1; 64 for(int i=0;i<g[x].size();i++) 65 { 66 int y=g[x][i].first,z=g[x][i].second; 67 if(dist[y]>dist[x]+z){dist[y]=dist[x]+z;q.push(make_pair(-dist[y],y));} 68 } 69 } 70 dfs1(1);dfs2(1);f[1]=e;e+=mx[1];dfs(1); 71 printf("%d %d ",ans1,ans2); 72 return 0; 73 }
树上dsu
cdq分治
树状数组
树套树
(1).线段树套权值线段树
luoguP3759 [TJOI2017]不勤劳的图书管理员
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define inf 0x3f3f3f3f 5 #define N 50010 6 #define mod 1000000007 7 int n,m,rt[N<<2],cc=0,cnt,sum,ans=0; 8 struct st{int id,v;}a[N]; 9 //**struct book{int id,v;}a[N]; 10 struct nd{int lc,rc,cnt,sum;}T[N<<8]; 11 //**struct node{int cnt,lc,rc,sum;}tr[N*256]; 12 queue<int>q; 13 void del(int &x){T[x].lc=T[x].rc=T[x].cnt=T[x].sum=0;q.push(x);x=0;} 14 int nwnd(){int x;if(!q.empty()){x=q.front();q.pop();return x;}else return ++cc;} 15 void add(int &x,int l,int r,int p,int f,int v) 16 { 17 if(!x)x=nwnd(); 18 T[x].cnt+=f;T[x].sum=((T[x].sum+f*v)%+mod)%mod; 19 if(l==r)return; 20 int mid=l+r>>1; 21 if(p<=mid)add(T[x].lc,l,mid,p,f,v);else add(T[x].rc,mid+1,r,p,f,v); 22 if(!T[x].cnt)del(x); 23 } 24 void ask(int x,int l,int r,int tl,int tr) 25 { 26 if(!x)return; 27 if(tl<=l&&r<=tr){cnt+=T[x].cnt;(sum+=T[x].sum)%=mod;return;} 28 int mid=l+r>>1; 29 if(tl<=mid)ask(T[x].lc,l,mid,tl,tr); 30 if(tr>mid)ask(T[x].rc,mid+1,r,tl,tr); 31 } 32 void upd(int x,int l,int r,int p,int v) 33 { 34 if(p!=v)add(rt[x],1,n,a[p].id,-1,a[p].v); 35 add(rt[x],1,n,a[v].id,1,a[v].v); 36 if(l==r)return; 37 int mid=l+r>>1; 38 if(p<=mid)upd(x<<1,l,mid,p,v);else upd(x<<1|1,mid+1,r,p,v); 39 } 40 void qry(int x,int l,int r,int tl,int tr,int pl,int pr) 41 { 42 if(tl>tr)return; 43 if(tl<=l&&r<=tr){ask(rt[x],1,n,pl,pr);return;} 44 int mid=l+r>>1; 45 if(tl<=mid)qry(x<<1,l,mid,tl,tr,pl,pr); 46 if(tr>mid)qry(x<<1|1,mid+1,r,tl,tr,pl,pr); 47 } 48 int main() 49 { 50 scanf("%d%d",&n,&m); 51 for(int i=1;i<=n;i++) 52 { 53 scanf("%d%d",&a[i].id,&a[i].v); 54 upd(1,1,n,i,i);cnt=0;sum=0;ask(rt[1],1,n,a[i].id+1,n); 55 (ans+=(1ll*cnt*a[i].v%mod+sum)%mod)%=mod; 56 } 57 while(m--) 58 { 59 int x,y;scanf("%d%d",&x,&y); 60 if(x>y)swap(x,y); 61 if(x==y){printf("%d ",ans);continue;} 62 int tl=a[x].id,tr=a[y].id,mn=min(tl,tr),mx=max(tl,tr); 63 cnt=sum=0;qry(1,1,n,x,y,mn+1,mx-1); 64 (ans+=(mn==tl?1:-1)*(2*sum%mod+1ll*(cnt+1)*(a[x].v+a[y].v)%mod)%mod)%=mod; 65 cnt=0;qry(1,1,n,x,y,1,mn-1);(ans+=1ll*cnt*(a[y].v-a[x].v)%mod)%=mod; 66 cnt=0;qry(1,1,n,x,y,mx+1,n);(ans+=1ll*cnt*(a[x].v-a[y].v)%mod)%=mod; 67 upd(1,1,n,x,y);upd(1,1,n,y,x);ans=(ans+mod)%mod; 68 swap(a[x],a[y]);printf("%d ",ans); 69 } 70 return 0; 71 }
主席树
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define N 100010 5 int n,q,t,a[N],dfn[N],l[N],r[N],dep[N],fa[N][25]; 6 vector<int>g[N]; 7 struct Trie 8 { 9 int nn,rt[N],s[N*40],ch[N*40][2]; 10 Trie(){rt[0]=nn=0;} 11 void ins(int &x,int y,int p) 12 { 13 int z=x=++nn; 14 for(int i=30;i>=0;i--) 15 { 16 int t=p>>i&1; 17 ch[z][t^1]=ch[y][t^1]; 18 ch[z][t]=++nn;z=ch[z][t];y=ch[y][t];s[z]=s[y]+1; 19 } 20 } 21 int qry(int x,int y,int p) 22 { 23 int r=0; 24 for(int i=30;i>=0;i--) 25 { 26 int t=p>>i&1; 27 if(s[ch[y][t^1]]-s[ch[x][t^1]]){r|=(1<<i);x=ch[x][t^1];y=ch[y][t^1];} 28 else{x=ch[x][t];y=ch[y][t];} 29 } 30 return r; 31 } 32 }T1,T2; 33 void dfs(int x,int p) 34 { 35 l[x]=++t;dep[x]=dep[p]+1;dfn[t]=x;fa[x][0]=p;T2.ins(T2.rt[x],T2.rt[p],a[x]); 36 for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)dfs(g[x][i],x); 37 r[x]=t; 38 } 39 int lca(int u,int v) 40 { 41 if(dep[u]<dep[v])swap(u,v); 42 int sub=dep[u]-dep[v]; 43 for(int i=20;i>=0;i--)if(sub>>i&1)u=fa[u][i]; 44 if(u==v)return u; 45 for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i]; 46 return fa[u][0]; 47 } 48 int main() 49 { 50 scanf("%d%d",&n,&q); 51 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 52 for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u); 53 dfs(1,0); 54 for(int i=1;i<=20;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; 55 for(int i=1;i<=n;i++)T1.ins(T1.rt[i],T1.rt[i-1],a[dfn[i]]); 56 for(int i=1;i<=q;i++) 57 { 58 int o,x,y,z;scanf("%d%d%d",&o,&x,&y); 59 if(o==1)printf("%d ",T1.qry(T1.rt[l[x]-1],T1.rt[r[x]],y)); 60 else{scanf("%d",&z);int t=lca(x,y);printf("%d ",max(T2.qry(T2.rt[fa[t][0]],T2.rt[x],z),T2.qry(T2.rt[fa[t][0]],T2.rt[y],z)));} 61 } 62 return 0; 63 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100010 4 int n,m,mx,tot,ls[N*40],rs[N*40],s[N*40],a[N],rt[N]; 5 void upd(int y,int &x,int l,int r,int p) 6 { 7 if(!x)x=++tot;s[x]=s[y]+p; 8 if(l==r)return; 9 int mid=l+r>>1; 10 if(p<=mid)rs[x]=rs[y],upd(ls[y],ls[x],l,mid,p);else ls[x]=ls[y],upd(rs[y],rs[x],mid+1,r,p); 11 } 12 int qry(int x,int y,int l,int r,int p) 13 { 14 if(p>=r)return s[y]-s[x]; 15 int mid=l+r>>1; 16 if(p>mid)return s[ls[y]]-s[ls[x]]+qry(rs[x],rs[y],mid+1,r,p);else return qry(ls[x],ls[y],l,mid,p); 17 } 18 int main() 19 { 20 scanf("%d",&n); 21 for(int i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(mx,a[i]); 22 for(int i=1;i<=n;i++)upd(rt[i-1],rt[i],1,mx,a[i]); 23 scanf("%d",&m); 24 for(int i=1;i<=m;i++) 25 { 26 int l,r,ans=1;scanf("%d%d",&l,&r); 27 while(true) 28 { 29 int s=qry(rt[l-1],rt[r],1,mx,ans); 30 if(s<ans)break; 31 ans=s+1; 32 } 33 printf("%d ",ans); 34 } 35 return 0; 36 }
平衡树:
fhq treap
splay
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 1000000007 4 #define N 100005 5 int n,rt,tp,stk[N],ch[N][2],fa[N],sz[N],rev[N]; 6 struct T{int x,i;}v[N]; 7 bool cmp(T a,T b){return (a.x^b.x)?a.x<b.x:a.i<b.i;} 8 int wh(int x){return ch[fa[x]][1]==x;} 9 void up(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;} 10 void down(int x) 11 { 12 if(rev[x]) 13 { 14 if(ch[x][0])rev[ch[x][0]]^=1; 15 if(ch[x][1])rev[ch[x][1]]^=1; 16 swap(ch[x][0],ch[x][1]);rev[x]=0; 17 } 18 } 19 void rot(int x) 20 { 21 int y=fa[x],z=fa[y],c=wh(x); 22 ch[y][c]=ch[x][c^1];if(ch[y][c])fa[ch[y][c]]=y; 23 fa[x]=z;if(z)ch[z][wh(y)]=x; 24 ch[x][c^1]=y;fa[y]=x;up(y); 25 } 26 void splay(int x,int t) 27 { 28 for(int i=x;i!=t;i=fa[i])stk[++tp]=i; 29 stk[++tp]=t; 30 while(tp)down(stk[tp--]); 31 for(int y=fa[x];y!=t;rot(x),y=fa[x])if(fa[y]!=t)rot(wh(x)^wh(y)?x:y); 32 if(!t)rt=x; 33 up(x); 34 } 35 int fnd(int k) 36 { 37 int x=rt; 38 while(true) 39 { 40 down(x); 41 if(k==sz[ch[x][0]]+1)return x; 42 else if(k<=sz[ch[x][0]])x=ch[x][0]; 43 else{k-=sz[ch[x][0]]+1;x=ch[x][1];} 44 } 45 } 46 void build(int l,int r,int p) 47 { 48 int mid=l+r>>1;fa[mid]=p; 49 if(!p)rt=mid;else if(mid<p)ch[p][0]=mid;else ch[p][1]=mid; 50 if(l==r){sz[mid]=1;return;} 51 if(l<mid)build(l,mid-1,mid); 52 if(mid<r)build(mid+1,r,mid); 53 up(mid); 54 } 55 int main() 56 { 57 scanf("%d",&n); 58 for(int i=2;i<=n+1;i++)scanf("%d",&v[i].x),v[i].i=i; 59 v[1]=(T){-inf,1};v[n+2]=(T){inf,n+2}; 60 sort(v+1,v+n+3,cmp); 61 build(1,n+2,0); 62 for(int i=2;i<=n;i++) 63 { 64 splay(v[i].i,0); 65 int ans=sz[ch[rt][0]]; 66 printf("%d ",ans); 67 int xx=fnd(i-1),yy=fnd(ans+2); 68 splay(xx,0);splay(yy,xx); 69 rev[ch[ch[rt][1]][0]]^=1; 70 } 71 printf("%d ",n); 72 return 0; 73 }
LCT
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1500005; 4 int read() 5 { 6 int x=0;char c=getchar(); 7 while(!isdigit(c))c=getchar(); 8 while(isdigit(c))x=x*10+c-48,c=getchar(); 9 return x; 10 } 11 int n,Q,ans,fa[N],ch[N][2],d[N],v[N],t1[N],t2[N],tg[N],st[N]; 12 queue<int>q; 13 inline bool wh(const int&x){return ch[fa[x]][1]==x;} 14 inline bool isrt(const int&x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} 15 inline void up(const int&x){t1[x]=t1[ch[x][1]]?t1[ch[x][1]]:(v[x]!=1?x:t1[ch[x][0]]);t2[x]=t2[ch[x][1]]?t2[ch[x][1]]:(v[x]!=2?x:t2[ch[x][0]]);} 16 inline void cov(const int&x){if(x){v[x]^=3;swap(t1[x],t2[x]);tg[x]^=1;}} 17 inline void down(const int&x){if(tg[x]){cov(ch[x][0]);cov(ch[x][1]);tg[x]=0;}} 18 inline void rot(const int&x) 19 { 20 int y=fa[x],z=fa[y],c=wh(x); 21 ch[y][c]=ch[x][c^1];if(ch[y][c])fa[ch[y][c]]=y; 22 fa[x]=z;if(!isrt(y))ch[z][wh(y)]=x; 23 ch[x][c^1]=y;fa[y]=x;up(y); 24 } 25 inline void splay(int x) 26 { 27 st[st[0]=1]=x; 28 for(int i=x;!isrt(i);i=fa[i])st[++st[0]]=fa[i]; 29 while(st[0])down(st[st[0]--]); 30 for(int y=fa[x];!isrt(x);rot(x),y=fa[x])if(!isrt(y))wh(x)^wh(y)?rot(x):rot(y); 31 up(x); 32 } 33 inline void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,up(x);} 34 int main() 35 { 36 n=read(); 37 for(int i=1,t1,t2,t3;i<=n;++i)t1=read(),t2=read(),t3=read(),d[fa[t1]=fa[t2]=fa[t3]=i]=3; 38 for(int i=n+1;i<=3*n+1;++i)v[i]=read(),v[i]<<=1,q.push(i); 39 while(!q.empty()) 40 { 41 int x=q.front();q.pop();v[fa[x]]+=v[x]>>1; 42 if(!--d[fa[x]])q.push(fa[x]); 43 } 44 ans=v[1]>>1;Q=read(); 45 while(Q--) 46 { 47 int x=read();v[x]^=2;int t=v[x]-1; 48 access(x=fa[x]);splay(x); 49 if(~t?t1[x]:t2[x]) 50 { 51 x=~t?t1[x]:t2[x];splay(x); 52 cov(ch[x][1]);v[x]+=t;up(ch[x][1]);up(x); 53 } 54 else cov(x),ans^=1; 55 putchar('0'+ans);putchar(' '); 56 } 57 return 0; 58 }
圆方树
虚树
点分树