高级数据结构学习笔记

~~这里是搞基数据结构学习笔记~~ 本博文是关于（比较神仙的数据结构）的题目或者数据结构的（比较神仙的题目）的刷题笔记。（实际上现在已经逐渐变成了只要是一道数据结构的题目都会扔进来的博客了……） 可能会用到的数据结构： 平衡树（splay、fhq treap） 线段树（包括主席树或权值线段树等） 树状数组 ```STL```（如```std::set```或者```std::vector```） ~~奇奇怪怪的科技（例如分块等等）~~ # I.[CF19D Points](https://www.luogu.com.cn/problem/CF19D) 树套树第一题。 思路1.线段树套线段树 因为内外的操作类似，很容易就能想到使用线段树套线段树，然后在线段树上二分来找到答案。 复杂度是$O(n\log^2 n)$，常数极大，因此被卡了。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n; vector<pair<int,int> >vp; struct opt{ int tp,x,y; }q[200100]; struct Inner_SegTree{ vector<int>val,sum; Inner_SegTree(){ val.clear(),sum.clear(); } int size(){ return val.size(); } void insert(int x){ val.push_back(x); } void construct(){ sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin()); sum.assign(val.size()<<2,0); } int ask(int x,int l,int r,int k){ if(val[r-1]<=k||!sum[x])return 0x3f3f3f3f; if(r-l==1)return val[l]; register int mid=(l+r)>>1; register int tmp=ask(x<<1|1,l,mid,k); if(tmp!=0x3f3f3f3f)return tmp; return ask(x+1<<1,mid,r,k); } void add(int x,int l,int r,int P,int k){ if(val[l]>P||val[r-1]<P)return; sum[x]+=k; if(r-l==1)return; register int mid=(l+r)>>1; add(x<<1|1,l,mid,P,k),add(x+1<<1,mid,r,P,k); } }; struct Outer_SegTree{ vector<int>val; vector<Inner_SegTree>inn; inline int size(){ return val.size(); } inline void insert_outer(int x){ val.push_back(x); } inline void insert_inner(int x,int l,int r,int P,int Q){ if(val[l]>P||val[r-1]<P)return; inn[x].insert(Q); if(r-l==1)return; int mid=(l+r)>>1; insert_inner(x<<1|1,l,mid,P,Q),insert_inner(x+1<<1,mid,r,P,Q); } inline void construct_outer(){ sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin()); inn.resize(val.size()<<2); } inline void construct_inner(){ for(register auto x:vp)insert_inner(0,0,val.size(),x.first,x.second); for(register auto &x:inn)x.construct(); } inline void add(int x,int l,int r,int P,int Q,int k){ if(val[l]>P||val[r-1]<P)return; inn[x].add(0,0,inn[x].size(),Q,k); if(r-l==1)return; register int mid=(l+r)>>1; add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k); } inline pair<int,int> ask(int x,int l,int r,int P,int Q){ register int pmt=inn[x].ask(0,0,inn[x].size(),Q); if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f); if(r-l==1)return make_pair(val[l],pmt); register int mid=(l+r)>>1; register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q); if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp; return ask(x+1<<1,mid,r,P,Q); } inline void iterate(int x,int l,int r){ printf("%d:(%d,%d):",x,l,r); for(register auto i:inn[x].val)printf("%d ",i);puts(""); if(r-l==1)return; register int mid=(l+r)>>1; iterate(x<<1|1,l,mid),iterate(x+1<<1,mid,r); } }seg; inline void read(int &x){ x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline void print(int x){ if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n); for(register int i=1;i<=n;i++){ char s[10]; scanf("%s",s),read(q[i].x),read(q[i].y); if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x); if(s[0]=='r')q[i].tp=2; if(s[0]=='f')q[i].tp=3; } seg.construct_outer(); // for(auto x:seg.val)printf("%d ",x);puts(""); seg.construct_inner(); // seg.iterate(0,0,seg.size()); for(register int i=1;i<=n;i++){ if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1); if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1); if(q[i].tp==3){ register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y); if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n'); else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n'); } } return 0; } ``` 思路2.线段树套```set```。 因为内层线段树里面要实现的操作一共只有插入、删除和求```upper_bound```，因此直接用```std::set```替代即可。 似乎线段树比```set```常数还要小？最终结果是```set```时间长一点，仍然TLE。 ```cpp #include<bits/stdc++.h> using namespace std; int n; vector<pair<int,int> >vp; struct opt{ int tp,x,y; }q[200100]; struct Inner_Set:set<int>{ int ask(int x){ set<int>::iterator it=upper_bound(x); if(it==end())return 0x3f3f3f3f; return *it; } }; struct Outer_SegTree{ vector<int>val; vector<Inner_Set>inn; inline int size(){ return val.size(); } inline void insert_outer(int x){ val.push_back(x); } inline void construct_outer(){ sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin()); inn.resize(val.size()<<2); } inline void add(int x,int l,int r,int P,int Q,int k){ if(val[l]>P||val[r-1]<P)return; if(k==1)inn[x].insert(Q); else inn[x].erase(Q); if(r-l==1)return; register int mid=(l+r)>>1; add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k); } inline pair<int,int> ask(int x,int l,int r,int P,int Q){ register int pmt=inn[x].ask(Q); if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f); if(r-l==1)return make_pair(val[l],pmt); register int mid=(l+r)>>1; register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q); if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp; return ask(x+1<<1,mid,r,P,Q); } }seg; inline void read(int &x){ x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline void print(int x){ if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n); for(register int i=1;i<=n;i++){ char s[10]; scanf("%s",s),read(q[i].x),read(q[i].y); if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x); if(s[0]=='r')q[i].tp=2; if(s[0]=='f')q[i].tp=3; } seg.construct_outer(); for(register int i=1;i<=n;i++){ if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1); if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1); if(q[i].tp==3){ register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y); if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n'); else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n'); } } return 0; } ``` 思路3.树状数组套```set```。 介于这题卡常卡的丧心病狂，考虑用常数更小的树状数组维护```set```。 思路就是用树状数组维护$y$坐标，支持单点的```set```插入/删除以及后缀$\max$（关于后缀的方法，实际上只需要把正常树状数组里面$+\operatorname{lowbit}$和$-\operatorname{lowbit}$的地方互换一下即可。 复杂度$O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> int n,val[200100],m; set<pii>s[200100]; struct opt{ int tp,x,y; }q[200100]; inline void read(int &x){ x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline void print(int x){ if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } void ins(int x,pii k){ while(x)s[x].insert(k),x-=x&-x; } void del(int x,pii k){ while(x)s[x].erase(k),x-=x&-x; } pii ask(int x,pii k){ pii res=make_pair(0x3f3f3f3f,0x3f3f3f3f); while(x<=m)res=min(res,*s[x].lower_bound(k)),x+=x&-x; return res; } int main(){ read(n); for(register int i=1;i<=n;i++){ char str[10]; scanf("%s",str),read(q[i].x),read(q[i].y); if(str[0]=='a')q[i].tp=1; if(str[0]=='r')q[i].tp=2; if(str[0]=='f')q[i].tp=3,q[i].x++,q[i].y++; val[++m]=q[i].y; } sort(val+1,val+m+1),m=unique(val+1,val+m+1)-val+1; for(int i=1;i<=m;i++)s[i].insert(make_pair(0x3f3f3f3f,0x3f3f3f3f)); for(register int i=1;i<=n;i++){ if(q[i].tp==1)ins(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y)); if(q[i].tp==2)del(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y)); if(q[i].tp==3){ register pii tmp=ask(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y)); if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n'); else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n'); } } return 0; } ``` # II.[Dynamic Rankings](https://www.luogu.com.cn/problem/P2617) 树状数组套权值线段树。 正经不带修的方法就是主席树（即一堆权值线段树并一起）。现在带修了，那就把这些主席树拆开，拆成$n$棵权值线段树，然后用树状数组进行单点修改以及前缀求和，复杂度$O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) int n,m,root[100100],cnt,bin[1001000],tp,lim,num[100100]; vector<int>v; struct node{ int lson,rson,sum; }seg[20001000]; int newid(){ if(!tp)return ++cnt; return bin[tp--]; } void ADD(int &x,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x)x=newid(); seg[x].sum+=val; if(l==r)return; ADD(seg[x].lson,l,mid,P,val),ADD(seg[x].rson,mid+1,r,P,val); if(!seg[x].sum)bin[++tp]=x,x=0; } void add(int x,int y,int z){ while(x<=n)ADD(root[x],1,lim,y,z),x+=x&-x; } int Query(vector<int>&x,vector<int>&y,int l,int r,int k){ if(l==r)return l; int lsum=0; for(auto i:x)lsum+=seg[seg[i].lson].sum; for(auto i:y)lsum-=seg[seg[i].lson].sum; if(k<=lsum){ for(auto &i:x)i=seg[i].lson; for(auto &i:y)i=seg[i].lson; return Query(x,y,l,mid,k); }else{ for(auto &i:x)i=seg[i].rson; for(auto &i:y)i=seg[i].rson; return Query(x,y,mid+1,r,k-lsum); } } int ask(int l,int r,int k){ vector<int>x,y; l--; while(r)x.push_back(root[r]),r-=r&-r; while(l)y.push_back(root[l]),l-=l&-l; return Query(x,y,1,lim,k); } struct opt{ int op,x,y,z; }q[100100]; void iterate(int x,int l,int r){ if(!x)return; iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&num[i]),v.push_back(num[i]); for(int i=1;i<=m;i++){ char s[10]; scanf("%s",s); if(s[0]=='Q')q[i].op=1,scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z); else q[i].op=2,scanf("%d%d",&q[i].x,&q[i].y),v.push_back(q[i].y); } sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size(); // for(auto i:v)printf("%d ",i);puts(""); for(int i=1;i<=n;i++)add(i,num[i]=lower_bound(v.begin(),v.end(),num[i])-v.begin()+1,1); for(int i=1;i<=m;i++){ if(q[i].op==1)printf("%d\n",v[ask(q[i].x,q[i].y,q[i].z)-1]); else add(q[i].x,num[q[i].x],-1),add(q[i].x,num[q[i].x]=lower_bound(v.begin(),v.end(),q[i].y)-v.begin()+1,1); } return 0; } ``` # III.[CF1093E Intersection of Permutations](https://www.luogu.com.cn/problem/CF1093E) 首先，我们如果令$c[i]$表示$b[i]$在数组$a$中出现的位置， 那么对于一次询问，答案就是$c$中下标在$[l_2,r_2]$间的数字中，值位于$[l_1,r_1]$间的数量。 思路1.树状数组套权值线段树。 很明显，这题的操作如果不带修可以用主席树完成（下标在$[l_2,r_2]$里面的树上进行值域查询）。带了修改，则套上树状数组完事。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) int n,m,root[200100],cnt,bin[10010000],tp,num[200100],a[200100],b[200100]; struct node{ int lson,rson,sum; }seg[20001000]; int newid(){ if(!tp)return ++cnt; return bin[tp--]; } void ADD(int &x,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x)x=newid(); seg[x].sum+=val; if(l!=r)ADD(seg[x].lson,l,mid,P,val),ADD(seg[x].rson,mid+1,r,P,val); if(!seg[x].sum)bin[++tp]=x,x=0; } void add(int x,int y,int z){ while(x<=n)ADD(root[x],1,n,y,z),x+=x&-x; } int Query(int x,int l,int r,int L,int R){ if(!x||l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; return Query(seg[x].lson,l,mid,L,R)+Query(seg[x].rson,mid+1,r,L,R); } int ask(int l,int r,int L,int R){ l--; int res=0; while(r)res+=Query(root[r],1,n,L,R),r-=r&-r; while(l)res-=Query(root[l],1,n,L,R),l-=l&-l; return res; } int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]=i; for(int i=1,x;i<=n;i++)scanf("%d",&x),b[i]=a[x]; for(int i=1;i<=n;i++)add(i,b[i],1); for(int i=1,t1,t2,t3,t4,t5;i<=m;i++){ scanf("%d",&t1); if(t1==1)scanf("%d%d%d%d",&t2,&t3,&t4,&t5),printf("%d\n",ask(t4,t5,t2,t3)); else scanf("%d%d",&t2,&t3),add(t2,b[t2],-1),add(t3,b[t3],-1),swap(b[t2],b[t3]),add(t2,b[t2],1),add(t3,b[t3],1); } return 0; } ``` 思路2.奇奇怪怪的分块-ver1.0 我们在数组$c$上分块，在每个块内排序。每次整块二分，散块直接暴力，复杂度$O(n\sqrt{n}\log n)$。 因为实现很糟糕，因此它T掉了。 TLE代码： ```cpp #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; const int BBB=600; int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim; inline void SWAP(int x,int y){ swap(c[x],c[y]); for(register int i=lp[BLK[x]];i<lp[BLK[x]+1];i++)d[i]=c[i]; sort(d+lp[BLK[x]],d+lp[BLK[x]+1]); for(register int i=lp[BLK[y]];i<lp[BLK[y]+1];i++)d[i]=c[i]; sort(d+lp[BLK[y]],d+lp[BLK[y]+1]); } inline int CALC(int l,int r,int L,int R){ register int res=0; if(BLK[L]==BLK[R]){ for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r); return res; } for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r); for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r); for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l); return res; } inline void read(int &x){ x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline int read(){ register int x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void print(int x){ if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n),read(m); for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB; for(register int i=0;i<n;i++)c[i]=d[i]=ra[read()]; lim=BLK[n-1]+1; for(register int i=0;i<lim;i++)lp[i]=i*BBB; lp[lim]=n,BLK[n]=lim; for(register int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]); for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){ read(t1); if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n'); else read(t2),read(t3),t2--,t3--,SWAP(t2,t3); } return 0; } ``` 思路3.奇奇怪怪的分块-ver2.0 设块长为$k$，我们分析一下各个操作的复杂度： 整块复杂度为$O(k\log\dfrac{n}{k})=O(k\log n)$ 散块复杂度为$O(\dfrac{n}{k})$ 修改复杂度为$O(\dfrac{n}{k}\log\dfrac{n}{k})=\dfrac{n}{k}\log n$ 则当$k=\sqrt{n}$时复杂度最优，为$O(\sqrt{n}\log n)$。 我们如果只考虑询问复杂度的话，这个$k$是可以取到$\sqrt{n\log n}$的。关键是修改。 有两种思路。 1. 考虑将修改也分块。将修改储存下来，每累计$\sqrt{n\log n}$个修改后，就暴力$O(n\log n)$全部推平重新排序。则每次询问时，只需要$O(\sqrt{n\log n})$遍历所有修改并更新答案即可。复杂度$O(\sqrt{n\log n})$。 2. 原本的修改，我们是$\dfrac{n}{k}\log n$重新排序的；发现修改只作用于一个位置；故可以直接$O(k)$插入排序，或者直接套上```std::set```让修改优化到$O(\log k)$。（实际上，套上```set```后就已经相当于一种树套树了，是分块套平衡树） 代码： ```cpp #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; const int BBB=1000; int n,m,BLK[200100],ra[200100],c[200100],d[200100],lp[1000],lim; vector<pair<int,int> >v; inline int CALC(int l,int r,int L,int R){ register int res=0; for(auto x:v){ res-=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r); res-=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r); swap(c[x.first],c[x.second]); res+=(x.first>=L)&&(x.first<R)&&(c[x.first]>=l)&&(c[x.first]<r); res+=(x.second>=L)&&(x.second<R)&&(c[x.second]>=l)&&(c[x.second]<r); } for(int i=v.size()-1;i>=0;i--)swap(c[v[i].first],c[v[i].second]); if(BLK[L]==BLK[R]){ for(register int i=L;i<R;i++)res+=(c[i]>=l&&c[i]<r); return res; } for(register int i=L;i<lp[BLK[L]+1];i++)res+=(c[i]>=l&&c[i]<r); for(register int i=lp[BLK[R]];i<R;i++)res+=(c[i]>=l&&c[i]<r); for(register int i=BLK[L]+1;i<BLK[R];i++)res+=lower_bound(d+lp[i],d+lp[i+1],r)-lower_bound(d+lp[i],d+lp[i+1],l); return res; } void init(){ for(auto x:v)swap(c[x.first],c[x.second]); v.clear(); for(int i=0;i<n;i++)d[i]=c[i]; for(int i=0;i<lim;i++)sort(d+lp[i],d+lp[i+1]); } inline void read(int &x){ x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline int read(){ register int x=0; register char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } inline void print(int x){ if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n),read(m); for(register int i=0;i<n;i++)ra[read()]=i,BLK[i]=i/BBB; for(register int i=0;i<n;i++)c[i]=ra[read()]; lim=BLK[n-1]+1; for(register int i=0;i<lim;i++)lp[i]=i*BBB; lp[lim]=n,BLK[n]=lim; init(); for(register int i=1,t1,t2,t3,t4,t5;i<=m;i++){ read(t1); if(t1==1)read(t2),read(t3),read(t4),read(t5),t2--,t4--,print(CALC(t2,t3,t4,t5)),putchar('\n'); else read(t2),read(t3),t2--,t3--,v.push_back(make_pair(t2,t3)); if(v.size()>=BBB)init(); } return 0; } ``` # IV.[【模板】二逼平衡树（树套树）](https://www.luogu.com.cn/problem/P3380) 树状数组套权值线段树最好了……$n\log^2n$的复杂度可比$n\log^3n$的什么线段树套平衡树要强一百万倍！~~其实是我不会写~~ 分析一下操作： 1. 二分出来最大的$<k$的数后直接权值线段树上查询前缀和。 2. 就是II.[Dynamic Rankings](https://www.luogu.com.cn/problem/P2617)。 3. 直接修改。 4. 权值线段树上二分前驱。 5. 权值线段树上二分后继。 操作全都是$O(\log^2n)$的。 敲出来，一遍$90\%$，TLE一个点，祭出快读，AC。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) int n,m,cnt,bin[1001000],tp,root[50100],lim,val[50100]; struct node{ int lson,rson,sum; }seg[5010000]; vector<int>v; inline void newnode(int &x){ if(!tp)x=++cnt; else x=bin[tp--]; } inline void segmod(int &x,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x)newnode(x); seg[x].sum+=val; if(l!=r)segmod(seg[x].lson,l,mid,P,val),segmod(seg[x].rson,mid+1,r,P,val); if(!seg[x].sum)bin[++tp]=x,x=0; } inline void finmod(int x,int P,int k){ while(x<=n)segmod(root[x],1,lim,P,k),x+=x&-x; } inline void modify(int x,int y){ y=lower_bound(v.begin(),v.end(),y)-v.begin()+1; finmod(x,val[x],-1); finmod(x,val[x]=y,1); } inline int segkth(vector<int>&x,vector<int>&y,int l,int r,int k){ int lsum=0; if(l==r)return v[l-1]; for(auto i:x)lsum+=seg[seg[i].lson].sum; for(auto i:y)lsum-=seg[seg[i].lson].sum; if(lsum>=k){ for(auto &i:x)i=seg[i].lson; for(auto &i:y)i=seg[i].lson; return segkth(x,y,l,mid,k); }else{ for(auto &i:x)i=seg[i].rson; for(auto &i:y)i=seg[i].rson; return segkth(x,y,mid+1,r,k-lsum); } } inline int finkth(int l,int r,int k){ vector<int>x,y; l--; while(l)y.push_back(root[l]),l-=l&-l; while(r)x.push_back(root[r]),r-=r&-r; return segkth(x,y,1,lim,k); } inline int segrak(int x,int l,int r,int L,int R){ if(!x||l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; return segrak(seg[x].lson,l,mid,L,R)+segrak(seg[x].rson,mid+1,r,L,R); } inline int finrak(int x,int y){ int sum=0; while(x)sum+=segrak(root[x],1,lim,1,y),x-=x&-x; return sum; } inline int rak(int l,int r,int x){ x=lower_bound(v.begin(),v.end(),x)-v.begin(); return finrak(r,x)-finrak(l-1,x)+1; } inline int segpre(vector<int>&x,vector<int>&y,int l,int r,int k){ int sum=0; for(auto i:x)sum+=seg[i].sum; for(auto i:y)sum-=seg[i].sum; if(!sum||l>k)return *v.begin(); if(l==r)return v[l-1]; vector<int>p,q; p.clear(),q.clear(); for(auto i:x)p.push_back(seg[i].rson); for(auto i:y)q.push_back(seg[i].rson); int tmp=segpre(p,q,mid+1,r,k); if(tmp!=*v.begin())return tmp; p.clear(),q.clear(); for(auto i:x)p.push_back(seg[i].lson); for(auto i:y)q.push_back(seg[i].lson); return segpre(p,q,l,mid,k); } inline int finpre(int l,int r,int k){ k=lower_bound(v.begin(),v.end(),k)-v.begin(); vector<int>x,y; l--; while(l)y.push_back(root[l]),l-=l&-l; while(r)x.push_back(root[r]),r-=r&-r; return segpre(x,y,1,lim,k); } inline int segsuf(vector<int>&x,vector<int>&y,int l,int r,int k){ int sum=0; for(auto i:x)sum+=seg[i].sum; for(auto i:y)sum-=seg[i].sum; if(!sum||r<k)return *v.rbegin(); if(l==r)return v[l-1]; vector<int>p,q; p.clear(),q.clear(); for(auto i:x)p.push_back(seg[i].lson); for(auto i:y)q.push_back(seg[i].lson); int tmp=segsuf(p,q,l,mid,k); if(tmp!=*v.rbegin())return tmp; p.clear(),q.clear(); for(auto i:x)p.push_back(seg[i].rson); for(auto i:y)q.push_back(seg[i].rson); return segsuf(p,q,mid+1,r,k); } inline int finsuf(int l,int r,int k){ k=upper_bound(v.begin(),v.end(),k)-v.begin()+1; vector<int>x,y; l--; while(l)y.push_back(root[l]),l-=l&-l; while(r)x.push_back(root[r]),r-=r&-r; return segsuf(x,y,1,lim,k); } struct opt{ int op,t1,t2,t3; }q[50100]; inline void read(int &x){ x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } inline void print(int x){ if(x<0)putchar('-'),print(-x); else if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n),read(m),v.push_back(-2147483647),v.push_back(2147483647); for(int i=1;i<=n;i++)read(val[i]),v.push_back(val[i]); for(int i=1;i<=m;i++){ read(q[i].op),read(q[i].t1),read(q[i].t2); if(q[i].op==3)v.push_back(q[i].t2); else read(q[i].t3); } sort(v.begin(),v.end()),v.resize(lim=(unique(v.begin(),v.end())-v.begin())); // for(auto x:v)printf("%d ",x);puts(""); for(int i=1;i<=n;i++)finmod(i,val[i]=lower_bound(v.begin(),v.end(),val[i])-v.begin()+1,1); // puts("IN"); for(int i=1;i<=m;i++){ if(q[i].op==1)print(rak(q[i].t1,q[i].t2,q[i].t3)),putchar('\n'); if(q[i].op==2)print(finkth(q[i].t1,q[i].t2,q[i].t3)),putchar('\n'); if(q[i].op==3)modify(q[i].t1,q[i].t2); if(q[i].op==4)print(finpre(q[i].t1,q[i].t2,q[i].t3)),putchar('\n'); if(q[i].op==5)print(finsuf(q[i].t1,q[i].t2,q[i].t3)),putchar('\n'); } return 0; } ``` # V.[【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810) ~~树套树比CDQ分治可爱一万倍！！！数据结构什么的最可爱了！！！~~ 那么树套树如何进行三维偏序呢？ 首先，第一维直接排序掉。 第二位用树状数组处理。 第三维套上权值线段树。 具体地说，因为我们要支持任何地方的单点修改以及前缀查询，就不得不套上树状数组。 这样，树套树便能完美替代一切CDQ能做的事。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) int n,m,cnt,root[200100],res[200100]; struct obj{ int a,b,c; friend bool operator <(const obj &x,const obj &y){ if(x.a!=y.a)return x.a<y.a; if(x.b!=y.b)return x.b<y.b; return x.c<y.c; } friend bool operator ==(const obj &x,const obj &y){ return x.a==y.a&&x.b==y.b&&x.c==y.c; } }q[100100]; struct SegTree{ int lson,rson,sum; }seg[10010000]; void add(int &x,int l,int r,int P){ if(l>P||r<P)return; if(!x)x=++cnt; seg[x].sum++; if(l==r)return; add(seg[x].lson,l,mid,P),add(seg[x].rson,mid+1,r,P); } void ADD(int x,int y){ while(x<=m)add(root[x],1,m,y),x+=x&-x; } int sum(int x,int l,int r,int P){ if(!x||l>P)return 0; if(r<=P)return seg[x].sum; return sum(seg[x].lson,l,mid,P)+sum(seg[x].rson,mid+1,r,P); } int SUM(int x,int y){ int Sum=0; while(x)Sum+=sum(root[x],1,m,y),x-=x&-x; return Sum; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c); sort(q+1,q+n+1); for(int i=1,j=1;i<=n;i=j){ while(q[j]==q[i])ADD(q[j].b,q[j].c),j++; res[SUM(q[i].b,q[i].c)-1]+=j-i; } for(int i=0;i<n;i++)printf("%d\n",res[i]); return 0; } ``` # VI.[[CQOI2011]动态逆序对](https://www.luogu.com.cn/problem/P3157) 这题需要支持查询前缀大于某个值的数量、后缀小于某个值的数量以及在某个地方插入值。 换句话说，我们要支持在以下标为$x$轴，权值为$y$轴的二维平面上动态删点以及询问矩形和。 如果我们把删点的时间看做$z$轴的话，那就是典型的三维偏序。 直接树套树完成。 代码（常数贼大，勉强卡过）： ```cpp #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define mid ((l+r)>>1) int n,m,cnt,root[2][100100],a[100100],b[100100],c[100100]; ll res[100100],all; struct node{ int lson,rson,sum; }seg[20010000]; void add(int &x,int l,int r,int P){ if(l>P||r<P)return; if(!x)x=++cnt; seg[x].sum++; if(l==r)return; add(seg[x].lson,l,mid,P),add(seg[x].rson,mid+1,r,P); } void ADD(int x,int y){ int tmp; tmp=x; while(tmp<=n)add(root[0][tmp],1,n,y),tmp+=tmp&-tmp; tmp=x; while(tmp>=1)add(root[1][tmp],1,n,y),tmp-=tmp&-tmp; } int ask(int x,int l,int r,int L,int R){ if(!x||l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R); } ll ASK(int x,int y){ ll s=0; int tmp; tmp=x-1; while(tmp>=1)s+=ask(root[0][tmp],1,n,y,n),tmp-=tmp&-tmp; tmp=x+1; while(tmp<=n)s+=ask(root[1][tmp],1,n,1,y),tmp+=tmp&-tmp; return s; } bool on[100100]; int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)c[a[i]=read()]=i; for(int i=1;i<=m;i++)on[c[b[i]=read()]]=true; for(int i=1;i<=n;i++)if(!on[i])all+=ASK(i,a[i]),ADD(i,a[i]); for(int i=m;i;i--)all+=ASK(c[b[i]],b[i]),ADD(c[b[i]],b[i]),res[i]=all; for(int i=1;i<=m;i++)printf("%lld\n",res[i]); return 0; } ``` # VII.[[ZJOI2013]K大数查询](https://www.luogu.com.cn/problem/P3332) 这题常卡的我快哭了QaQ 首先，我们仍然考虑树套树。 1. 下标树套权值树（即我们前几题的一贯做法） 我们发现，要在区间树上打上区间添加数的```tag```，并且用```tag```树的并集进行二分。 因此最终的结果就是，大区间被分割成$\log n$个小区间，但是每个小区间的$\log n$个父亲区间的```tag```树都是必须选的。因此总共有$\log^2n$个```tag```树在一起二分，因此总复杂度就是$\log^3n$的。并且写起来还贼恶心。介于这题贼卡长，我不认为这种方法有通过的可能性。 2. 权值树套下标树 现在，我们就是在权值树的某个叶节点上的下标树内，打上一个区间加的```tag```。当然咯，这叶节点的所有父亲的下标树，也是要打```tag```的。 最终的结果就是，修改就是在$\log n$个下标树内打区间加```tag```，复杂度$\log^2n$。 然后询问。就直接在权值树上二分，同时在下标树上查询区间和，复杂度$\log^2n$。 被卡长的代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,Inc,root[200100],dis[200100],tp; struct Inner{ int lson,rson,tag; ll sum; }inn[20010000]; inline void pushdown(const register int &x,const register int &l,const register int &r){ register int mid=(l+r)>>1,&val=inn[x].tag; if(!inn[x].lson)inn[x].lson=++Inc; if(!inn[x].rson)inn[x].rson=++Inc; inn[inn[x].lson].sum+=1ll*val*(mid-l+1),inn[inn[x].lson].tag+=val; inn[inn[x].rson].sum+=1ll*val*(r-mid),inn[inn[x].rson].tag+=val; val=0; } inline void Inner_Add(register int &x,const register int &l,const register int &r,const register int &L,const register int &R){ if(!x)x=++Inc; if(L<=l&&r<=R){inn[x].sum+=r-l+1,inn[x].tag++;return;} if(inn[x].tag)pushdown(x,l,r); register int mid=(l+r)>>1; if(mid>=L)Inner_Add(inn[x].lson,l,mid,L,R); if(mid<R)Inner_Add(inn[x].rson,mid+1,r,L,R); inn[x].sum=inn[inn[x].lson].sum+inn[inn[x].rson].sum; } inline ll Inner_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R){ if(L<=l&&r<=R)return inn[x].sum; if(inn[x].tag)pushdown(x,l,r); register int mid=(l+r)>>1; ll res=0; if(mid>=L&&inn[x].lson)res+=Inner_Ask(inn[x].lson,l,mid,L,R); if(mid<R&&inn[x].rson)res+=Inner_Ask(inn[x].rson,mid+1,r,L,R); return res; } inline void Outer_Add(const register int &x,const register int &l,const register int &r,const register int &P,const register int &L,const register int &R){ Inner_Add(root[x],1,n,L,R); if(l==r)return; register int mid=(l+r)>>1; if(mid>=P)Outer_Add(x<<1,l,mid,P,L,R); else Outer_Add(x<<1|1,mid+1,r,P,L,R); } inline int Outer_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register ll &k){ if(l==r)return l; register ll rsum=Inner_Ask(root[x<<1|1],1,n,L,R); register int mid=(l+r)>>1; if(rsum>=k)return Outer_Ask(x<<1|1,mid+1,r,L,R,k); else return Outer_Ask(x<<1,l,mid,L,R,k-rsum); } struct Query{ int tp,l,r; ll k; }q[50100]; inline void read(register int &x){ register char c=getchar(); register int fl=1; while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=fl; } inline void read(register ll &x){ register char c=getchar(); register int fl=1; while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=fl; } inline void print(register int x){ if(x<0)putchar('-'),print(-x); else if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n),read(m); for(register int i=1;i<=m;i++){ read(q[i].tp),read(q[i].l),read(q[i].r),read(q[i].k); if(q[i].tp==1)dis[++tp]=q[i].k; } sort(dis+1,dis+tp+1),tp=unique(dis+1,dis+tp+1)-dis-1; for(register int i=1;i<=m;i++){ if(q[i].tp==1)Outer_Add(1,1,tp,lower_bound(dis+1,dis+tp+1,q[i].k)-dis,q[i].l,q[i].r); else print(dis[Outer_Ask(1,1,tp,q[i].l,q[i].r,q[i].k)]),putchar('\n'); } return 0; } ``` 能用的优化就只有在下标树上的**标记永久化**了。 因此现学了这个东西，敲出来常数果然快了很多，勉强卡过了： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,Inc,root[200100],dis[200100],tp; struct Inner{ int lson,rson,tag; ll sum; }inn[20010000]; inline void Inner_Add(register int &x,const register int &l,const register int &r,const register int &L,const register int &R){ if(!x)x=++Inc; inn[x].sum+=max(min(R,r)-max(L,l)+1,0); if(L<=l&&r<=R){inn[x].tag++;return;} register int mid=(l+r)>>1; if(mid>=L)Inner_Add(inn[x].lson,l,mid,L,R); if(mid<R)Inner_Add(inn[x].rson,mid+1,r,L,R); } inline ll Inner_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register int add=0){ if(!x)return 1ll*add*max(min(R,r)-max(L,l)+1,0); if(L<=l&&r<=R)return 1ll*add*(r-l+1)+inn[x].sum; register int mid=(l+r)>>1; register ll res=0; if(mid>=L)res+=Inner_Ask(inn[x].lson,l,mid,L,R,add+inn[x].tag); if(mid<R)res+=Inner_Ask(inn[x].rson,mid+1,r,L,R,add+inn[x].tag); return res; } inline void Outer_Add(const register int &x,const register int &l,const register int &r,const register int &P,const register int &L,const register int &R){ Inner_Add(root[x],1,n,L,R); if(l==r)return; register int mid=(l+r)>>1; if(mid>=P)Outer_Add(x<<1,l,mid,P,L,R); else Outer_Add(x<<1|1,mid+1,r,P,L,R); } inline int Outer_Ask(const register int &x,const register int &l,const register int &r,const register int &L,const register int &R,const register ll &k){ if(l==r)return l; register ll rsum=Inner_Ask(root[x<<1|1],1,n,L,R); register int mid=(l+r)>>1; if(rsum>=k)return Outer_Ask(x<<1|1,mid+1,r,L,R,k); else return Outer_Ask(x<<1,l,mid,L,R,k-rsum); } struct Query{ int tp,l,r; ll k; }q[50100]; inline void read(register int &x){ register char c=getchar(); register int fl=1; while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=fl; } inline void read(register ll &x){ register char c=getchar(); register int fl=1; while(c>'9'||c<'0')fl=(c=='-'?-fl:fl),c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=fl; } inline void print(register int x){ if(x<0)putchar('-'),print(-x); else if(x<=9)putchar('0'+x); else print(x/10),putchar('0'+x%10); } int main(){ read(n),read(m); for(register int i=1;i<=m;i++){ read(q[i].tp),read(q[i].l),read(q[i].r),read(q[i].k); if(q[i].tp==1)dis[++tp]=q[i].k; } sort(dis+1,dis+tp+1),tp=unique(dis+1,dis+tp+1)-dis-1; for(register int i=1;i<=m;i++){ if(q[i].tp==1)Outer_Add(1,1,tp,lower_bound(dis+1,dis+tp+1,q[i].k)-dis,q[i].l,q[i].r); else print(dis[Outer_Ask(1,1,tp,q[i].l,q[i].r,q[i].k)]),putchar('\n'); } return 0; } ``` # VIII.[CF785E Anton and Permutation](https://www.luogu.com.cn/problem/CF785E) 我们看一下交换以后，哪些逆序对会受到影响。 设交换了位置$(x,y)$，它们原本的值是$val_x,val_y$。不妨设$x<y$。 对于一个位置$i<x$，$x,y$在交换后仍然都排在它后面，不受影响； 对于一个位置$i>y$，$x,y$在交换后仍然都排在它前面，不受影响； 对于一个位置$i\in(x,y)$，这时就会产生影响了。 对于一个$val_i>\max(val_x,val_y)$或$val_i<\min(val_x,val_y)$，交换后前后的大小关系不变，不受影响。 则受影响的只有$i\in(i,j),val_i\in(val_x,val_y)$，这时要么新出现两个逆序对，要么消失两个逆序对。 树套树维护一下，复杂度$O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) typedef long long ll; int n,m,root[200100],bin[1001000],tp,cnt,val[200100]; ll res; struct node{ int lson,rson,sum; }seg[20010000]; void newnode(int &x){ if(!tp)x=++cnt; else x=bin[tp--]; } void add(int &x,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x)newnode(x); seg[x].sum+=val; if(l!=r)add(seg[x].lson,l,mid,P,val),add(seg[x].rson,mid+1,r,P,val); if(!seg[x].sum)bin[++tp]=x,x=0; } void ADD(int x,int y,int k){ while(x<=n)add(root[x],1,n,y,k),x+=x&-x; } int ask(int x,int l,int r,int L,int R){ if(!x||l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R); } int ASK(int x,int L,int R){ ll ret=0; while(x)ret+=ask(root[x],1,n,L,R),x-=x&-x; return ret; } ll SWAP(int x,int y){ if(x==y)return res; if(x>y)swap(x,y); ADD(x,val[x],-1),ADD(y,val[y],-1); if(val[x]<val[y])res++,res+=(ASK(y-1,val[x],val[y])-ASK(x,val[x],val[y]))<<1; else res--,res-=(ASK(y-1,val[y],val[x])-ASK(x,val[y],val[x]))<<1; swap(val[x],val[y]); ADD(x,val[x],1),ADD(y,val[y],1); return res; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)ADD(i,val[i]=i,1); for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),printf("%lld\n",SWAP(x,y)); return 0; } ``` # IX.[[TJOI2017]不勤劳的图书管理员](https://www.luogu.com.cn/problem/P3759) 我要举报……出题人语文明显不太好…… 首先，这题就是上一题的带权版。 然后，这题带了权后和上一题就不太一样了。 当你交换位置$x,y$的书后，（默认$x<y$） 位置在$x$前或在$y$后的书不受影响； 位置在$x,y$之间，且$val_z\in(val_x,val_y)$的书$z$，效果和之前一样。只不过，这次还要算上$x$和$y$的贡献。 位置在$x,y$之间，且$val_z\in(1,val_x)$的书$z$，虽然它自己的贡献没变，但是它对$x,y$的贡献却改变了；具体的说，改变了$val_y-val_x$。 位置在$x,y$之间，且$val_z\in(val_y,n)$的书$z$，类似的，改变了$val_x-val_y$。 然后因为出题人语文不好，我整整在错误的方向上努力了一晚上…… 代码（比第一篇暴力的题解还要慢……）： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define mid ((l+r)>>1) #define pii pair<int,int> pii operator +(const pii &x,const pii &y){ return make_pair((x.first+y.first)%mod,(x.second+y.second)%mod); } void operator +=(pii &x,const pii &y){ (x.first+=y.first)%=mod,(x.second+=y.second)%=mod; } pii operator -(const pii &x,const pii &y){ return make_pair((x.first-y.first+mod)%mod,(x.second-y.second+mod)%mod); } typedef long long ll; int n,m,root[50100],cnt,val[50100],bok[50100],pos[50100],res; struct node{ int lson,rson; pii sum; }seg[10010000]; void add(int &x,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x)x=++cnt; (seg[x].sum.first+=(val+mod)%mod)%=mod; (seg[x].sum.second+=(val>0?1:-1)+mod)%=mod; if(l!=r)add(seg[x].lson,l,mid,P,val),add(seg[x].rson,mid+1,r,P,val); } void ADD(int x,int y,int k){ while(x<=n)add(root[x],1,n,y,k),x+=x&-x; } pii ask(int x,int l,int r,int L,int R){ if(!x||l>R||r<L)return make_pair(0,0); if(L<=l&&r<=R)return seg[x].sum; return ask(seg[x].lson,l,mid,L,R)+ask(seg[x].rson,mid+1,r,L,R); } pii ASK(int x,int L,int R){ pii ret=make_pair(0,0); while(x)ret+=ask(root[x],1,n,L,R),x-=x&-x; return ret; } int SWAP(int x,int y){ if(x==y)return res; if(x>y)swap(x,y); ADD(x,bok[x],-val[x]),ADD(y,bok[y],-val[y]); if(bok[x]<bok[y]){ pii tmp; tmp=ASK(y-1,bok[x],bok[y])-ASK(x,bok[x],bok[y]); (res+=(tmp.first<<1)%mod)%=mod; (res+=1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod; tmp=ASK(y-1,1,bok[x])-ASK(x,1,bok[x]); (res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod; tmp=ASK(y-1,bok[y],n)-ASK(x,bok[y],n); (res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod; } else{ pii tmp; tmp=ASK(y-1,bok[y],bok[x])-ASK(x,bok[y],bok[x]); (res+=mod-(tmp.first<<1)%mod)%=mod; (res+=mod-1ll*(tmp.second+1)*(val[x]+val[y])%mod)%=mod; tmp=ASK(y-1,1,bok[y])-ASK(x,1,bok[y]); (res+=1ll*(val[y]-val[x]+mod)%mod*tmp.second%mod)%=mod; tmp=ASK(y-1,bok[x],n)-ASK(x,bok[x],n); (res+=1ll*(val[x]-val[y]+mod)%mod*tmp.second%mod)%=mod; } swap(bok[x],bok[y]),swap(val[x],val[y]); ADD(x,bok[x],val[x]),ADD(y,bok[y],val[y]); return res; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&bok[i],&val[i]); pii tmp=ASK(i,bok[i],n); (res+=tmp.first)%=mod; (res+=1ll*tmp.second*val[i]%mod)%=mod; ADD(i,bok[i],val[i]); } for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),printf("%d\n",SWAP(x,y)); return 0; } ``` # X.[CF650D Zip-line](https://www.luogu.com.cn/problem/CF650D) 我们考虑在修改一个位置后，新的LIS可能有哪些。 1. 就是原序列中的LIS。 设原序列LIS长度为$len$。 此时有两种可能： A.被修改的位置在LIS中不是不可替代的（换句话说，有至少一条LIS不经过此位置）。此时，长度就是$len$。 B.被修改的位置在LIS中不可替代（换句话说，所有LIS都经过此位置）。此时，长度是$len-1$。 至于如何判断是不是不可替代的吗……可以记录以当前位置开头和结尾的LIS数量，然后与总LIS数量比较。如果开头结尾的LIS数量之积等于总LIS数量，则该位置是不可替代的。 因为LIS数量非常非常大，因此模上一个大数哈希一下即可。 2. 不是原序列中的LIS。 则我们要找到所有在它前面且比它小的位置中前缀长度的最大值，以及所有在它后面且比它大的位置中后缀长度的最大值，然后拼在一起完成。 考虑用主席树维护即可。 但是！！！这题卡空间，两棵主席树就是$40$倍空间，跑不过去。 被卡的主席树代码： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define mid ((l+r)>>1) #define pii pair<int,int> #define mp make_pair #define ff first #define ss second int n,root1[400100],root2[400100],a[400100],m,lim,cnt; pii mx; pii f[400100],g[400100]; vector<int>v; struct SegTree{ int lson,rson; pii sum; }seg[16001000]; pii operator +=(pii&x,const pii&y){ if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod; else if(x.ff<y.ff)x=y; } pii operator +(const pii&x,const pii&y){ if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod); return max(x,y); } void modify(int &x,int y,int l,int r,int P,pii val){ if(l>P||r<P)return; x=++cnt; seg[x]=seg[y],seg[x].sum+=val; if(l!=r)modify(seg[x].lson,seg[y].lson,l,mid,P,val),modify(seg[x].rson,seg[y].rson,mid+1,r,P,val); } pii query(int x,int l,int r,int L,int R){ if(l>R||r<L)return mp(0,0); if(L<=l&&r<=R)return seg[x].sum; return query(seg[x].lson,l,mid,L,R)+query(seg[x].rson,mid+1,r,L,R); } void build(int &x,int l,int r){ x=++cnt; if(l!=r)build(seg[x].lson,l,mid),build(seg[x].rson,mid+1,r); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]); sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size(); for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; build(root1[0],1,lim); for(int i=1;i<=n;i++){ f[i]=query(root1[i-1],1,lim,1,a[i]-1),f[i].first++; if(f[i].first==1)f[i].second++; modify(root1[i],root1[i-1],1,lim,a[i],f[i]),mx+=f[i]; } build(root2[n+1],1,lim); for(int i=n;i>=1;i--){ g[i]=query(root2[i+1],1,lim,a[i]+1,lim),g[i].first++; if(g[i].first==1)g[i].second++; modify(root2[i],root2[i+1],1,lim,a[i],g[i]); } for(int i=1,x,y,res;i<=m;i++){ scanf("%d%d",&x,&y); if(f[x].first+g[x].first-1==mx.first&&1ll*f[x].second*g[x].second%mod==mx.second)res=mx.first-1; else res=mx.first; res=max(res,query(root1[x-1],1,lim,1,lower_bound(v.begin(),v.end(),y)-v.begin()).first+1+query(root2[x+1],1,lim,upper_bound(v.begin(),v.end(),y)-v.begin()+1,lim).first); printf("%d\n",res); } return 0; } ``` 主席树是暴力的思想，但是是在线的。如果我们把它离线下来，就可以在建主席树时直接回答当前位置的询问。而主席树实际上是线段树的前缀和，故直接用线段树维护即可。只需要$4$倍空间。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) #define pii pair<int,int> #define mp make_pair #define ff first #define ss second int n,a[400100],m,lim,res[400100]; pii mx; pii f[400100],g[400100],seg[1600100]; vector<int>v; vector<pii>q[400100]; pii operator +=(pii&x,const pii&y){ if(x.ff==y.ff)(x.ss+=y.ss),x.ss%=mod; else if(x.ff<y.ff)x=y; } pii operator +(const pii&x,const pii&y){ if(x.ff==y.ff)return make_pair(x.ff,(x.ss+y.ss)%mod); return max(x,y); } void modify(int x,int l,int r,int P,pii val){ if(l>P||r<P)return; seg[x]+=val; if(l!=r)modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val); } pii query(int x,int l,int r,int L,int R){ if(l>R||r<L)return mp(0,0); if(L<=l&&r<=R)return seg[x]; return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R); } void build(int x,int l,int r){ seg[x]=mp(0,0); if(l!=r)build(lson,l,mid),build(rson,mid+1,r); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]); sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size(); for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),q[x].push_back(mp(y,i)); build(1,1,lim); for(int i=1;i<=n;i++){ f[i]=query(1,1,lim,1,a[i]-1),f[i].first++; if(f[i].first==1)f[i].second++; for(auto j:q[i])res[j.second]=query(1,1,lim,1,lower_bound(v.begin(),v.end(),j.first)-v.begin()).first+1; modify(1,1,lim,a[i],f[i]),mx+=f[i]; } build(1,1,lim); for(int i=n;i>=1;i--){ g[i]=query(1,1,lim,a[i]+1,lim),g[i].first++; if(g[i].first==1)g[i].second++; int fal=(f[i].first+g[i].first-1==mx.first&&1ll*f[i].second*g[i].second%mod==mx.second?mx.first-1:mx.first); for(auto j:q[i])res[j.second]+=query(1,1,lim,upper_bound(v.begin(),v.end(),j.first)-v.begin()+1,lim).first,res[j.second]=max(res[j.second],fal); modify(1,1,lim,a[i],g[i]); } for(int i=1;i<=m;i++)printf("%d\n",res[i]); return 0; } ``` # XI.[CF85D Sum of Medians](https://www.luogu.com.cn/problem/CF85D) 这题做法有无数种，其中最暴力的一种就是~~用```vector```爆算~~用$5$棵fhq treap直接处理。比线段树要好想的多。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,root[5],cnt,bin[100100],tp; struct treap{ int lson,rson,val,rd,sz; ll sum; }t[100100]; int newnode(int val){ int x=(tp?bin[tp--]:++cnt); t[x].lson=t[x].rson=0,t[x].sum=t[x].val=val,t[x].rd=rand()*rand(),t[x].sz=1; return x; } void pushup(int x){ t[x].sum=t[x].val,t[x].sz=1; if(t[x].lson)t[x].sum+=t[t[x].lson].sum,t[x].sz+=t[t[x].lson].sz; if(t[x].rson)t[x].sum+=t[t[x].rson].sum,t[x].sz+=t[t[x].rson].sz; } void split(int x,int k,int &u,int &v){ if(!x){u=v=0;return;} if(t[x].val<=k)u=x,split(t[x].rson,k,t[x].rson,v); else v=x,split(t[x].lson,k,u,t[x].lson); pushup(x); } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].rd<t[y].rd){t[x].rson=merge(t[x].rson,y),pushup(x);return x;} else{t[y].lson=merge(x,t[y].lson),pushup(y);return y;} } int main(){ srand(19260817); scanf("%d",&n); for(int i=1,x;i<=n;i++){ char s[10]; scanf("%s",s); if(s[0]=='a'){ scanf("%d",&x); int u[5],v[5],sz=1; for(int i=0;i<5;i++)split(root[i],x,u[i],v[i]),sz+=t[u[i]].sz,root[i]=u[i]; x=newnode(x); root[sz%5]=merge(root[sz%5],x); for(int i=0;i<5;i++)root[i]=merge(root[i],v[(i+4)%5]); } if(s[0]=='d'){ scanf("%d",&x); int u[5],v[5],w[5]; for(int i=0;i<5;i++)split(root[i],x,u[i],v[i]),split(u[i],x-1,root[i],w[i]); for(int i=0;i<5;i++)root[i]=merge(root[i],v[(i+1)%5]); } if(s[0]=='s')printf("%lld\n",t[root[3]].sum); } return 0; } ``` # XII.初级版：[[NOI2003]文本编辑器](https://www.luogu.com.cn/problem/P4008)；进阶版：[[AHOI2006]文本编辑器](https://www.luogu.com.cn/problem/P4567) 两道题操作基本一致，唯一的区别就是进阶版多了一个翻转操作，因此干脆合在一起讲。 可以使用splay或fhq treap通过。个人认为fhq treap更加直观。 光标的位置，我们用一个值$tar$表示。 ```Move/Next/Prev```：直接修改$tar$的值即可。 ```Insert```：笛卡尔树$O(n)$建树并插入。 ```Delete```：```split```出有效区间然后删掉即可。可以采取空间回收，这是很好的习惯，因为你不知道会不会RE/MLE。 ```Get```：直接输出```split```后右半部最靠左那个地方的字符即可。 ```Rotate```：fhq treap上打区间翻转的tag即可。 [[NOI2003]文本编辑器](https://www.luogu.com.cn/problem/P4008)代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,rt,cnt,bin[5001000],tp,tar,stk[5001000],bd; char s[5001000]; void getstring(int len){ char c=getchar(); for(int i=0;i<len;i++){ while(c>126||c<32)c=getchar(); s[i]=c,c=getchar(); } } int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-48,c=getchar(); return x; } struct treap{ int lson,rson,rd,sz; char ch; }t[5001000]; int newnode(char ch){ int x=tp?bin[tp--]:++cnt; t[x].ch=ch,t[x].lson=t[x].rson=0,t[x].sz=1,t[x].rd=rand()*rand(); return x; } void pushup(int x){ t[x].sz=1; if(t[x].lson)t[x].sz+=t[t[x].lson].sz; if(t[x].rson)t[x].sz+=t[t[x].rson].sz; } void split(int x,int k,int &u,int &v){ if(!x){u=v=0;return;} if(t[t[x].lson].sz>=k)v=x,split(t[x].lson,k,u,t[x].lson); else u=x,split(t[x].rson,k-t[t[x].lson].sz-1,t[x].rson,v); pushup(x); } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].rd>t[y].rd){t[x].rson=merge(t[x].rson,y),pushup(x);return x;} else{t[y].lson=merge(x,t[y].lson),pushup(y);return y;} } void iterate(int x){ if(!x)return; iterate(t[x].lson); putchar(t[x].ch); iterate(t[x].rson); } void oldnode(int x){ if(!x)return; oldnode(t[x].lson),oldnode(t[x].rson),bin[++tp]=x; } int build(int len){ int las; for(int i=0;i<len;i++){ int x=newnode(s[i]); las=0; while(bd&&t[stk[bd]].rd<t[x].rd)pushup(stk[bd]),las=stk[bd--]; if(bd)t[stk[bd]].rson=x; t[stk[++bd]=x].lson=las; } while(bd)pushup(stk[bd--]); return stk[1]; } void Move(){tar=read();} void Insert(){ int len=read(); getstring(len); int a,b; split(rt,tar,a,b); rt=merge(merge(a,build(len)),b); } void Delete(){ int len=read(); int a,b,c; split(rt,tar,a,b); split(b,len,b,c); oldnode(b); rt=merge(a,c); } void Get(){ int len=read(); int a,b,c; split(rt,tar,a,b); split(b,len,b,c); iterate(b);putchar('\n'); rt=merge(merge(a,b),c); } void Prev(){tar--;} void Next(){tar++;} int main(){ n=read(); while(n--){ scanf("%s",s); if(s[0]=='I')Insert(); else if(s[0]=='M')Move(); else if(s[0]=='D')Delete(); else if(s[0]=='G')Get(); else if(s[0]=='P')Prev(); else if(s[0]=='N')Next(); } return 0; } ``` [[AHOI2006]文本编辑器](https://www.luogu.com.cn/problem/P4567)代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,stk[5001000],tp,bin[5001000],bd,cnt,tar,rt; char s[5001000]; void getstring(int len){ for(int i=0;i<len;i++)s[i]=getchar(); } int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } struct treap{ int lson,rson,rd,sz; char ch; bool rev; }t[5001000]; int newnode(char ch){ int x=tp?bin[tp--]:++cnt; t[x].lson=t[x].rson=0,t[x].rd=rand()*rand(),t[x].sz=1,t[x].ch=ch,t[x].rev=false; return x; } void oldnode(int x){ if(!x)return; oldnode(t[x].lson),oldnode(t[x].rson),bin[++tp]=x; } void pushup(int x){ t[x].sz=1; if(t[x].lson)t[x].sz+=t[t[x].lson].sz; if(t[x].rson)t[x].sz+=t[t[x].rson].sz; } void REV(int x){ swap(t[x].lson,t[x].rson),t[x].rev^=1; } void pushdown(int x){ if(!t[x].rev)return; REV(t[x].lson),REV(t[x].rson),t[x].rev=false; } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].rd>t[y].rd){pushdown(x),t[x].rson=merge(t[x].rson,y),pushup(x);return x;} else{pushdown(y),t[y].lson=merge(x,t[y].lson),pushup(y);return y;} } void split(int x,int k,int &u,int &v){ if(!x){u=v=0;return;} pushdown(x); if(t[t[x].lson].sz>=k)v=x,split(t[x].lson,k,u,t[x].lson); else u=x,split(t[x].rson,k-t[t[x].lson].sz-1,t[x].rson,v); pushup(x); } void Insert(){ int len=read(); getstring(len); for(int i=0;i<len;i++){ int x=newnode(s[i]),las=0; while(bd&&t[stk[bd]].rd<t[x].rd)pushup(stk[bd]),las=stk[bd--]; if(bd)t[stk[bd]].rson=x; t[stk[++bd]=x].lson=las; } while(bd)pushup(stk[bd--]); int a,b; split(rt,tar,a,b); rt=merge(merge(a,stk[1]),b); } void Delete(){ int len=read(); int a,b,c; split(rt,tar,a,b); split(b,len,b,c); rt=merge(a,c),oldnode(b); } void Rotate(){ int len=read(); int a,b,c; split(rt,tar,a,b); split(b,len,b,c); REV(b),rt=merge(merge(a,b),c); } void Move(){tar=read();} void Next(){tar++;} void Prev(){tar--;} void leftmost(int x){ pushdown(x); if(!t[x].lson){ putchar(t[x].ch); if(t[x].ch!='\n')putchar('\n'); }else leftmost(t[x].lson); } /* void iterate(int x){ if(!x)return; pushdown(x); iterate(t[x].lson); putchar(t[x].ch); iterate(t[x].rson); } */ void Get(){ int a,b; split(rt,tar,a,b); leftmost(b); rt=merge(a,b); } int main(){ n=read(); while(n--){ scanf("%s",s); if(s[0]=='M')Move(); else if(s[0]=='I')Insert(); else if(s[0]=='D')Delete(); else if(s[0]=='R')Rotate(); else if(s[0]=='G')Get(); else if(s[0]=='P')Prev(); else if(s[0]=='N')Next(); // iterate(rt),putchar('\n'); } return 0; } ``` # XIII.[CF226E Noble Knight's Path](https://www.luogu.com.cn/problem/CF226E) 这题分为在线和离线两种做法~~然而我只会在线~~ 在线的思路很简单，即先**树剖**，然后建出**主席树**。主席树一维维护的是时间，每一棵主席树内部维护的是树剖剖出来的结果。 然后对于每一次询问： 首先先从两边跳链，找到LCA，并找出两点路径间没有被“亵渎”的城堡数。如果这一数量小于询问，直接输出$-1$。 否则，先从$x$往上一直跳到LCA，如果这一段中未被“亵渎”的城堡数已经足够了，就直接输出；否则，从$y$点向上跳，类似地找未被亵渎的城堡。 那怎么输出呢？这就要在**线段树上二分**了。当然，反正总复杂度已经是$\log^2$了，你要嫌麻烦直接写$\log^2$的二分套线段树也没有问题，毕竟线段树上二分写起来确实挺恶心的。不过这里写的还是线段树上二分。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int N=100100; int n,m,des[N]; //------------------------Chain Decompotision--------------- int dfn[N],rev[N],fa[N],dep[N],son[N],top[N],sz[N],head[N],cnt,tot; struct node{ int to,next; }edge[200100]; void ae(int u,int v){ edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++; edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++; } void dfs1(int x,int Fa){ fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1; for(int i=head[x],y;i!=-1;i=edge[i].next){ if((y=edge[i].to)==fa[x])continue; dfs1(y,x),sz[x]+=sz[y]; if(sz[son[x]]<sz[y])son[x]=y; } } void dfs2(int x){ if(son[x])top[son[x]]=top[x],dfn[son[x]]=++tot,rev[tot]=son[x],dfs2(son[x]); for(int i=head[x],y;i!=-1;i=edge[i].next){ y=edge[i].to; if(y==fa[x]||y==son[x])continue; top[y]=y,dfn[y]=++tot,rev[tot]=y,dfs2(y); } } //--------------Persistent Segment Tree-------------------- #define mid ((l+r)>>1) int rt[N],newid; struct SegTree{ int lson,rson,sum; }seg[20001000]; void build(int &x,int l,int r){ x=++newid; if(l!=r)build(seg[x].lson,l,mid),build(seg[x].rson,mid+1,r); } void modify(int &x,int y,int l,int r,int P){ if(l>P||r<P)return; seg[x=++newid]=seg[y],seg[x].sum++; if(l!=r)modify(seg[x].lson,seg[y].lson,l,mid,P),modify(seg[x].rson,seg[y].rson,mid+1,r,P); } int asksize(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; return asksize(seg[x].lson,l,mid,L,R)+asksize(seg[x].rson,mid+1,r,L,R); } int rangeask(int x,int y,int l,int r,int k){ if(l==r)return rev[l]; if((mid-l+1)-(seg[seg[y].lson].sum-seg[seg[x].lson].sum)>=k)return rangeask(seg[x].lson,seg[y].lson,l,mid,k); else return rangeask(seg[x].rson,seg[y].rson,mid+1,r,k-((mid-l+1)-(seg[seg[y].lson].sum-seg[seg[x].lson].sum))); } int askkth(int x,int y,int l,int r,int L,int R,int &k,bool &findans){ if(l>R||r<L)return 0; if(L<=l&&r<=R){ if((r-l+1)-(seg[y].sum-seg[x].sum)>=k){findans=true;return rangeask(x,y,l,r,k);} else{k-=(r-l+1)-(seg[y].sum-seg[x].sum);return 0;}; } int tmp=askkth(seg[x].lson,seg[y].lson,l,mid,L,R,k,findans); if(findans)return tmp; return askkth(seg[x].rson,seg[y].rson,mid+1,r,L,R,k,findans); } #define AS(A,B,L,R) (R-L+1)-(asksize(rt[B],1,n,L,R)-asksize(rt[A],1,n,L,R)) int main(){ scanf("%d",&n),memset(head,-1,sizeof(head)); for(int i=1,x;i<=n;i++){ scanf("%d",&x); if(x)ae(x,i); } dfs1(1,0),top[1]=dfn[1]=rev[1]=tot=1,dfs2(1); build(rt[0],1,n); scanf("%d",&m); for(int i=1,a,b,c,d,tp,res;i<=m;i++){ scanf("%d",&tp); if(tp==1)scanf("%d",&a),des[a]=i,modify(rt[i],rt[i-1],1,n,dfn[a]); else{ rt[i]=rt[i-1],res=0; scanf("%d%d%d%d",&a,&b,&c,&d); if(des[a]<=d)c++; int x=a,y=b,len=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); len+=AS(d,i,dfn[top[x]],dfn[x]),x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); len+=AS(d,i,dfn[x],dfn[y]); len-=(des[b]<=d); if(len<c){puts("-1");continue;} //---------------------getpath&LCA------------------------- int LCA=x; x=a; bool getans=false; while(dep[x]>=dep[LCA]){ int anc=(dep[top[x]]<dep[LCA]?LCA:top[x]); int tmp=AS(d,i,dfn[anc],dfn[x]); if(c>tmp)c-=tmp,len-=tmp; else{c=tmp-c+1;res=askkth(rt[d],rt[i],1,n,dfn[anc],dfn[x],c,getans);break;} x=fa[top[x]]; } if(getans){printf("%d\n",res);continue;} //--------------------check A----------------------------- y=b; c=len-c+1; if(des[b]<=d)c++; while(true){ int dfntop=dfn[top[y]]; if(dep[top[y]]<=dep[LCA])dfntop=dfn[LCA]+1; int tmp=AS(d,i,dfntop,dfn[y]); if(c>tmp)c-=tmp; else{c=tmp-c+1;res=askkth(rt[d],rt[i],1,n,dfntop,dfn[y],c,getans);break;} y=fa[top[y]]; } printf("%d\n",res); } } return 0; } ``` # XIV.[SP1557 GSS2 - Can you answer these queries II](https://www.luogu.com.cn/problem/SP1557) 我认为这是GSS题目中难度最大的一道，不接受反驳。 这题中出现多次的只给算一次，应该咋办呢？ 我们回忆起这种情况的经典老题：[[SDOI2009]HH的项链](https://www.luogu.com.cn/problem/P1972)。正解是将询问离线后按照右端点递增排序，然后出现多次的，就只计算从最后一次出现的位置到当前这个位置这段区间的贡献。 于是本题也可以类似地做。 我们仍然按照右端点递增顺序枚举，设当前右端点为$i$。我们维护对于每个位置$j$，子段$[j,i]$的和，设为$s_j$。则当$i$从$i-1$移动到$i$时，区间$[las_{a_i}+1,i]$中的所有$s_j$都会被增加$a_i$。于是我们可以用线段树维护$s$数组。 则我们发现，对于一次询问$[l,r]$，我们只需要求出当$i=r$时，区间$[l,r]$中的**历史最大值**即可。 我们考虑对于线段树上每个节点维护这样一些东西： - $mx$，它为区间中当前所有$s_i$的最大值。 - $MX$，它为区间中历史$s_i$的最大值。 - $tag$，它为区间的懒标记。 - $TAG$，它为从上次```pushdown```以来，$tag$的最大值。 当我们修改一个位置的值的时候： - $mx$增加这对应的值； - $tag$增加对应的值； - $MX$与当前$mx$取$\max$； - $TAG$与当前$tag$取$\max$； 当我们```pushdown```的时候： - 子节点的$MX$与$mx_{son}+TAG_{fa}$取$\max$； - 子节点的$TAG$与$tag_{son}+TAG_{fa}$取$\max$； - 之后，子节点的$mx$与$tag$正常地更新。 - 然后，父节点的$tag$与$TAG$清空。 我们可以把这俩玩意轻松地二合一： ```void ADD(int x,int y,int z=0){z=max(z,y),seg[x].MX=max(seg[x].MX,seg[x].mx+z),seg[x].TAG=max(seg[x].TAG,seg[x].tag+z),seg[x].mx+=y,seg[x].tag+=y;}``` 询问的时候，就直接返回对应区间的$MX$即可。 时间复杂度$O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,a[100100],res[100100]; map<int,int>mp; struct Query{ int l,r,id; friend bool operator <(const Query &x,const Query &y){ return x.r<y.r; } }q[100100]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ ll mx,tag,MX,TAG;//mx:the current maximum in the section; MX:the history maximum in the section; tag:the lazy tag for mx; TAG:the lazy tag for MX }seg[400100]; void ADD(int x,int y,int z=0){z=max(z,y),seg[x].MX=max(seg[x].MX,seg[x].mx+z),seg[x].TAG=max(seg[x].TAG,seg[x].tag+z),seg[x].mx+=y,seg[x].tag+=y;} #define pushdown(x) ADD(lson,seg[x].tag,seg[x].TAG),ADD(rson,seg[x].tag,seg[x].TAG),seg[x].tag=seg[x].TAG=0 #define pushup(x) seg[x].mx=max(seg[lson].mx,seg[rson].mx),seg[x].MX=max(seg[lson].MX,seg[rson].MX) void modify(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(L<=l&&r<=R){ADD(x,val);return;} pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x); } int query(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].MX; pushdown(x); return max(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R)); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; sort(q+1,q+m+1); for(int i=1,j=1;i<=n;i++){ modify(1,1,n,mp[a[i]]+1,i,a[i]),mp[a[i]]=i; while(j<=m&&q[j].r<=i)res[q[j].id]=query(1,1,n,q[j].l,q[j].r),j++; } for(int i=1;i<=m;i++)printf("%d\n",res[i]); return 0; } ``` # XV.[CF319E Ping-Pong](https://www.luogu.com.cn/problem/CF319E) 好题。 首先，离线下来离散化显然是不用说的。 然后观察这里“可以移动”的定义，发现明显可以类比图论中的连边。发现边只有有向边（两区间包含）和无向边（两区间相交）两种，又因为我们只管连通性，所以无向边可以直接使用并查集维护。而包含关系又具有可传递性，故我们最终会发现必定存在一条路径使得最多经过一条有向边（经过多条有向边的路径可以被合并）。于是我们如果使用并查集维护的话，则只需要判断所有互相可达的小区间**合并**后，询问的两个区间是否相同或者后者包含前者即可。 然后就是这题的精髓所在了—— 我们将每个区间在线段树中拆成$\log n$个区间，使用```vector```存在节点上。则对于线段树中的某个叶子节点，它的所有父亲节点上的区间中，包含了**所有包含当前叶节点**的区间。 于是我们在插入一个区间后，它左右两端所在的节点的所有祖先节点上的区间都与它有交；而因为题目保证插入的区间长度递增，所以这必定连的都是无向边，故我们直接使用并查集合并即可。合并之后，在每个节点的```vector```内，只需保留当前区间即可。 在合并完之后，就直接拆区间即可。判断就依靠我们上文提到的性质判断。 时间复杂度$O\Big(n\log n\alpha(n)\Big)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,cnt; struct oper{ int tp,l,r; }q[100100]; vector<int>v[800100],dis; int L[100100],R[100100],dsu[100100]; int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);} #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) void merge(int x,int l,int r,int P,int id){ if(l>P||r<P)return; if(!v[x].empty()){ for(auto ip:v[x])ip=find(ip),dsu[ip]=id,L[id]=min(L[id],L[ip]),R[id]=max(R[id],R[ip]); v[x].clear(),v[x].push_back(id); } if(l!=r)merge(lson,l,mid,P,id),merge(rson,mid+1,r,P,id); } void assign(int x,int l,int r,int id){ if(r<=L[id]||l>=R[id])return; if(L[id]<l&&r<R[id]){v[x].push_back(id);return;} assign(lson,l,mid,id),assign(rson,mid+1,r,id); } int main(){ scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&q[i].tp,&q[i].l,&q[i].r); if(q[i].tp==1)dis.push_back(q[i].l),dis.push_back(q[i].r); } sort(dis.begin(),dis.end()),dis.resize(n=unique(dis.begin(),dis.end())-dis.begin()); for(int i=1;i<=m;i++){ if(q[i].tp==1){ cnt++; dsu[cnt]=cnt,q[i].l=lower_bound(dis.begin(),dis.end(),q[i].l)-dis.begin()+1,q[i].r=lower_bound(dis.begin(),dis.end(),q[i].r)-dis.begin()+1; L[cnt]=q[i].l,R[cnt]=q[i].r; merge(1,1,n,q[i].l,cnt),merge(1,1,n,q[i].r,cnt); assign(1,1,n,cnt); }else{ int x=q[i].l,y=q[i].r; x=find(x),y=find(y); puts(x==y||(L[y]<L[x]&&L[x]<R[y])||(L[y]<R[x]&&R[x]<R[y])?"YES":"NO"); } } return 0; } ``` # XVI.[CF360B Levko and Array](https://www.luogu.com.cn/problem/CF360B) 明显可以二分答案为$x$。二分之后，我们考虑DP验证。 我们设$f_i$表示$a_i$强制保留时，最多可以保留多少个数。则我们显然有转移方程 $$\Large f_i=\max\limits_{j\in[1,i),|a_i-a_j|\leq(i-j)x}f_j+1$$ 考虑到转移的限制： $$j<i,|a_i-a_j|\leq(i-j)x$$ 绝对值可被拆开，得到 $$j<i,a_i-a_j\leq(i-j)x,a_i-a_j\geq(j-i)x$$ 考虑继续拆开，得到 $$j<i,jx+a_j\leq ix+a_j,jx-a_j\leq ix-a_i$$ 明显此时已经是一个三维偏序问题，直接使用树套树/CDQ分治，即可以$n\log^3n$通过本题。 考虑某个加强版，此时若有$n\leq 2\times10^5$，如何对敌？ 考虑$(j-i)x\leq a_i-a_j\leq(i-j)x$的限制，它实际上已经包含了$j<i$的限制（因为当$j>i$时两个不等式显然不可能都成立）；故我们直接以这两个做二维偏序即可。时间复杂度$O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,a[200100],t[200100],lim; void add(int x,int y){while(x<=lim)t[x]=max(t[x],y),x+=x&-x;} int ask(int x){int ret=0;while(x)ret=max(ret,t[x]),x-=x&-x;return ret;} pair<ll,ll>p[200100]; vector<ll>v; bool che(int ip){ v.clear(),memset(t,0,sizeof(t)); for(int i=1;i<=n;i++)p[i]=make_pair(1ll*ip*i-a[i],1ll*ip*i+a[i]),v.push_back(p[i].second); sort(v.begin(),v.end()),v.resize(lim=unique(v.begin(),v.end())-v.begin()); for(int i=1;i<=n;i++)p[i].second=lower_bound(v.begin(),v.end(),p[i].second)-v.begin()+1; sort(p+1,p+n+1); int mx=0; for(int i=1,tmp;i<=n;i++)tmp=ask(p[i].second)+1,mx=max(mx,tmp),add(p[i].second,tmp); return mx+m>=n; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); int l=0,r=2e9; while(l<r){ int mid=(0ll+l+r)>>1; if(che(mid))r=mid; else l=mid+1; } printf("%d\n",r); return 0; } ``` # XVII.[CF1413F Roads and Ramen](https://www.luogu.com.cn/problem/CF1413F) 首先，注意到本题等价于求**路径上所有边权的异或和为$0$的路径**长度的最大值。 然后，我们要猜/证明出一个结论，即任意一条极长合法路径，其必有一个端点是直径端点。 证明： 我们设有一条直径$(S,T)$。我们再设$col_i$表示从$i$节点到根节点（不妨设为$1$号节点）上所有边权的异或和。 1. $col_S=col_T$ 此时显然有$(S,T)$合法，又有$(S,T)$是直径，故$(S,T)$即为答案。 2. $col_S\neq col_T$ 假设当前我们有一条合法路径$(s,t)$；则显然，必有$s,t$的颜色同$S,T$中某一个点的颜色相等，假设是$S$。则$(s,S),(t,S)$两条路径中较长的一条的长度肯定大于等于$(s,t)$的长度，这是直径的性质。 于是我们就直接找到直径$(S,T)$，对二者各维护一棵线段树，查询所有到它距离为偶数的点中深度最大值即可。 时间复杂度$O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,head[500100],cnt; struct node{ int to,next; bool tp; }edge[1001000]; struct SegTree{ int dfn[500100],sz[500100],rev[500100],dep[500100],tot; bool ini[500100]; int mx[2000100][2]; bool tag[2001000]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) #define REV(x) tag[x]^=1,swap(mx[x][0],mx[x][1]) void pushdown(int x){if(tag[x])REV(lson),REV(rson),tag[x]=false;} void pushup(int x){mx[x][0]=max(mx[lson][0],mx[rson][0]),mx[x][1]=max(mx[lson][1],mx[rson][1]);} void dfs(int x,int fa){ dfn[x]=++tot,sz[x]=1,rev[tot]=x; for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dep[edge[i].to]=dep[x]+1,ini[edge[i].to]=ini[x]^edge[i].tp,dfs(edge[i].to,x),sz[x]+=sz[edge[i].to]; } void build(int x,int l,int r){ if(l==r){mx[x][ini[rev[l]]]=dep[rev[l]];return;} build(lson,l,mid),build(rson,mid+1,r),pushup(x); } void modify(int x,int l,int r,int L,int R){ if(l>R||r<L)return; if(L<=l&&r<=R){REV(x);return;} pushdown(x),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R),pushup(x); } }seg[2]; void ae(int u,int v,bool w){ edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].tp=w,head[u]=cnt++; edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].tp=w,head[v]=cnt++; } pair<int,int>dfs(int x,int fa){ pair<int,int>ret=make_pair(-1,x); for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)ret=max(ret,dfs(edge[i].to,x)); ret.first++; return ret; } int main(){ scanf("%d",&n),memset(head,-1,sizeof(head)); for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z); int S=dfs(1,0).second,T=dfs(S,0).second; seg[0].dfs(S,0),seg[1].dfs(T,0); seg[0].build(1,1,n),seg[1].build(1,1,n); scanf("%d",&m); for(int i=1,x;i<=m;i++){ scanf("%d",&x),x--; int u=edge[x<<1].to,v=edge[x<<1|1].to; if(seg[0].dep[u]<seg[0].dep[v])swap(u,v); seg[0].modify(1,1,n,seg[0].dfn[u],seg[0].dfn[u]+seg[0].sz[u]-1); if(seg[1].dep[u]<seg[1].dep[v])swap(u,v); seg[1].modify(1,1,n,seg[1].dfn[u],seg[1].dfn[u]+seg[1].sz[u]-1); printf("%d\n",max(seg[0].mx[1][0],seg[1].mx[1][0])); } return 0; } ``` # XVIII.[CF679E Bear and Bad Powers of 42](https://www.luogu.com.cn/problem/CF679E) 一个显然的想法是，观察到可能的值域（$10^{14}$）内不会有很多（准确地说，一共$11$个）$42$的整数次幂。于是我们考虑每次暴力修改，则每个数最多被处理$11$次，复杂度显然是可以承受的。 于是我们现在问题就转变为判断一个区间中是否存在$42$的整数次幂。 我们对于每个数，维护这个数到下一个$42$的次幂的距离，并在区间上维护这一距离的$\min$。在区间加的时候，代表区间加的tag增加，同时代表区间$\min$的tag减少。 假如区间$\min$的tag在减少后为$0$了，就直接返回找到了；否则，如果其大于$0$，返回没找到；否则，即其小于$0$，无法判断有没有找到，需要继续往子区间内遍历。 假如遍历到一个位置，发现这个位置的区间修改的tag不为$0$（这可能意味着这段区间刚刚被进行了一次区间修改，或是访问到了叶节点——叶节点的区间修改tag（即它自己的值）显然是不为$0$的），那就可以直接由这个tag推出区间中的$\min$（毕竟整个区间的值都是相等的），再返回这个$\min$是否为$0$即可。 这也意味着我们的```pushdown```函数要比较细心：假设当前区间修改tag不为$0$，显然下传时，应该把儿子的tag全都覆盖掉——区间修改tag赋成下传的tag，区间加的tag赋成$0$；同时，**区间$\min$的值也要下传**，这就避免了在儿子处再算一遍的局面。 假设当前区间加tag不为$0$（显然，此时区间修改tag肯定为$0$），下传时注意判断儿子的区间修改tag是否为$0$，为$0$则加到区间加tag上，否则直接加到区间修改tag上；同时，在修改后，记得同时修改区间$\min$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m; const int lim=11; ll pov[20]={1,42,1764,74088,3111696,130691232,5489031744ll,230539333248ll,9682651996416ll,406671383849472ll,17080198121677824ll}; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ ll tagmodi,tagadd,mn; }seg[400100]; void ADD(int x,ll y){if(seg[x].tagmodi)seg[x].tagmodi+=y;else seg[x].tagadd+=y;seg[x].mn-=y;} void REFRESH(int x){seg[x].mn=*lower_bound(pov,pov+lim,seg[x].tagmodi)-seg[x].tagmodi;} void MODI(int x,ll y){seg[x].tagmodi=y,seg[x].tagadd=0,REFRESH(x);} void pushdown(int x){ if(seg[x].tagmodi){ seg[lson].tagmodi=seg[rson].tagmodi=seg[x].tagmodi; seg[lson].mn=seg[rson].mn=seg[x].mn; seg[lson].tagadd=seg[rson].tagadd=0; seg[x].tagmodi=0; } if(seg[x].tagadd)ADD(lson,seg[x].tagadd),ADD(rson,seg[x].tagadd),seg[x].tagadd=0; } void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);} void build(int x,int l,int r){ if(l==r){scanf("%lld",&seg[x].tagmodi),REFRESH(x);return;} build(lson,l,mid),build(rson,mid+1,r),pushup(x); } void setval(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(L<=l&&r<=R){MODI(x,val);return;} pushdown(x),setval(lson,l,mid,L,R,val),setval(rson,mid+1,r,L,R,val),pushup(x); } bool find(int x,int l,int r){ if(seg[x].mn>=0)return seg[x].mn==0; if(seg[x].tagmodi){REFRESH(x);return seg[x].mn==0;} pushdown(x); bool ret=find(lson,l,mid)|find(rson,mid+1,r); pushup(x); return ret; } bool add(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return false; if(L<=l&&r<=R){ ADD(x,val); return find(x,l,r); } pushdown(x); bool ret=add(lson,l,mid,L,R,val)|add(rson,mid+1,r,L,R,val); pushup(x); return ret; } ll query(int x,int l,int r,int P){ if(l==r)return seg[x].tagmodi; pushdown(x); ll ret=(P<=mid?query(lson,l,mid,P):query(rson,mid+1,r,P)); pushup(x); return ret; } //void iterate(int x,int l,int r){if(l==r)printf("(%lld:%lld)",seg[x].tagmodi,seg[x].mn);else pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r),pushup(x);} int main(){ scanf("%d%d",&n,&m); build(1,1,n); for(int i=1,a,b,c,d;i<=m;i++){ scanf("%d%d",&a,&b); if(a==1)printf("%lld\n",query(1,1,n,b)); else{ scanf("%d%d",&c,&d); if(a==2)setval(1,1,n,b,c,d); else while(add(1,1,n,b,c,d)); } // iterate(1,1,n),puts(""); } return 0; } ``` # XIX.[「JOI 2013 Final」バブルソート 冒泡排序](https://loj.ac/problem/2765) 首先，有一个常识性结论，就是冒泡排序的次数等于逆序对数。所以本题等价于交换两个数使得减少的逆序对数最多。 于是我们翻出VIII.[CF785E Anton and Permutation](https://www.luogu.com.cn/problem/CF785E)中给出的结论——当$i<j$且$a_i>a_j$时，交换一对$(i,j)$，减少的逆序对数就等于将所有$P_i=(i,a_i)$映射到平面上后，以$P_i$为左上角、$P_j$为右下角的矩形中点的个数$\times2$，再加上其本身的$1$对逆序对。当然，出现在边界上的点要特判掉（这些点只能贡献$1$次）。 稍微想想就可以发现，最优的$(i,j)$，$P_i$一定不在某个$P_k$的右下方，$P_j$一定不在某个$P_k$的左上方。换言之，$P_i$只出现在$a_i$的前缀最大值的位置，$P_j$只出现在$a_j$的后缀最小值的位置。 我们考虑对于某个点$k$，它可以对哪些$(i,j)$产生贡献——明显，只有在其左上方的$P_i$和右下方的$P_j$，可以从它收到贡献。而画出图来就能发现，所有合法的$i$，在前缀最大值中是一段区间$[i_l,i_r]$；所有合法的$j$，也是一段区间$[j_l,j_r]$。 于是，我们发现它实际上被转成了一个二维矩形覆盖问题，其中一维是$i$，另一位是$j$。于是直接扫描线维护过去，求覆盖最大值即可。同时注意特判边界，以及不存在这样的$(i,j)$对的情形（即原序列本身已是一个递增/不降序列，递增时答案恒为$1$，不降时答案恒为$0$）。 代码： ```cpp #include<bits/stdc++.h> using namespace std; #define emp emplace_back typedef long long ll; int n,m,a[100100],pre[100100],PRE,suf[100100],SUF,t[100100]; ll res; void add(int x){while(x)t[x]++,x-=x&-x;} void sum(int x){for(x++;x<=m;x+=x&-x)res-=t[x];} void cheinc(){ bool ok=true; for(int i=2;i<=n;i++)ok&=(a[i]>a[i-1]); if(ok){puts("1");exit(0);} ok=true; for(int i=2;i<=n;i++)ok&=(a[i]>=a[i-1]); if(ok){puts("0");exit(0);} } struct Data{ int l,r,d; Data(int L,int R,int D){l=L,r=R,d=D;} }; vector<Data>v[100100]; vector<int>u; struct SegTree{ int tag,mx; }seg[400100]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) #define ADD(x,y) seg[x].tag+=y,seg[x].mx+=y #define pushdown ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0 #define pushup seg[x].mx=max(seg[lson].mx,seg[rson].mx) void modify(int x,int l,int r,int L,int R,int D){ if(l>R||r<L)return; if(L<=l&&r<=R)ADD(x,D); else pushdown,modify(lson,l,mid,L,R,D),modify(rson,mid+1,r,L,R,D),pushup; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),u.push_back(a[i]); sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin()); for(int i=1;i<=n;i++)a[i]=lower_bound(u.begin(),u.end(),a[i])-u.begin()+1; // for(int i=1;i<=n;i++)printf("%d ",a[i]);puts(""); cheinc(); for(int i=1;i<=n;i++)if(!PRE||a[i]>a[pre[PRE]])pre[++PRE]=i; for(int i=n;i>=1;i--)if(!SUF||a[i]<a[suf[SUF]])suf[++SUF]=i; reverse(suf+1,suf+SUF+1); // for(int i=1;i<=PRE;i++)printf("%d ",pre[i]);puts(""); // for(int i=1;i<=SUF;i++)printf("%d ",suf[i]);puts(""); for(int i=1,j=1,k=1;i<=n;i++){ while(j<=PRE&&i>pre[j])j++; while(k<=SUF&&i>suf[k])k++; int J=upper_bound(pre+1,pre+PRE+1,i,[](int x,int y){return a[x]<a[y];})-pre; int K=lower_bound(suf+1,suf+SUF+1,i,[](int x,int y){return a[x]<a[y];})-suf-1; v[J].emp(k,K,2),v[j].emp(k,K,-2); if(J&&a[pre[J-1]]==a[i])v[J-1].emp(k,K,1),v[J].emp(k,K,-1); if(K<=SUF&&a[suf[K+1]]==a[i])v[J].emp(K+1,K+1,1),v[j].emp(K+1,K+1,-1); } for(int i=1;i<=PRE;i++){ for(auto j:v[i])modify(1,1,SUF,j.l,j.r,j.d); res=max(res,1ll*seg[1].mx); } // printf("%d\n",res); for(int i=1;i<=n;i++)sum(a[i]),add(a[i]); printf("%lld\n",-1-res); return 0; } ``` # XX.[[APIO2018] New Home 新家](https://www.luogu.com.cn/problem/P4632) [题解](https://www.luogu.com.cn/blog/Troverld/solution-p4632) # XXI.[[APIO2015]八邻旁之桥](https://www.luogu.com.cn/problem/P3644) 首先先忽略所有在同侧的人，考虑异侧的人。 则明显，如果我们只在$p$位置修一座桥，则一个从某侧的$x$到另一侧的$y$的人，其一共要走的距离就是 $$|p-x|+|p-y|$$ （忽略了桥长，因为桥长可以被统一计算） 于是我们发现，此时$x$和$y$是独立的。于是问题就转成了数轴上有很多点，要求一个点 $p$ 到所有点的距离和最小。 通过逐步调整法，我们可以发现$p$即为所有点的中位数。（因为点的数量是偶数，所以会有两个中位数，此时选择任何一个都是可以的） 进一步拆开绝对值符号之后，会发现是$(\text{更大的一半数之和})-(\text{更小的一半数之和})$。 现在有两座桥了。我们会发现，假如我们对所有人按照$x+y$排序，则一定是前一半的人走左侧的桥，后一半人走右侧的桥。这可以通过画出图来证明：两端都在左侧桥左方的人，或是都在右侧桥右方的人，显然走相应的桥最优；两端各在两侧桥两边的人，显然走任何一座桥都是可以的；唯独两端在两侧桥之间的人，画出图来，会发现走离其更近的桥更优，而比较就是按$x+y$比较的。 于是我们现在就可以枚举这个断点，两边就分别转成了一座桥的问题。于是我们现在就要对于每个前缀和后缀，求出其中$(\text{更大的一半数之和})-(\text{更小的一半数之和})$，并将两边拼在一起。 如何求出呢？ ~~平衡树~~ 那就太可怕了。直接使用两个堆即可，其中一个是大根堆，维护前一半数；一个是小根堆，维护后一半数。当加入一个人时，先把其$x$和$y$全部插入大根堆，然后再平衡两个堆的大小即可。假如发现平衡过后，大根堆的顶大于小根堆的顶，就交换堆顶元素即可。 时间复杂度$O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,r; pair<int,int>p[100100]; vector<int>v[2]; char s[4]; ll all,mn=0x3f3f3f3f3f3f3f3f,pre[100100],suf[100100],PRE,SUF; priority_queue<int>P,Q;//P:greater heap for smaller part; Q:smaller heap for greater part int main(){ scanf("%d%d",&m,&r); for(int i=1,x,y;i<=r;i++){ scanf("%s%d",s,&x); scanf("%s%d",s+1,&y); if(s[0]==s[1])all+=abs(x-y); else p[++n]=make_pair(x,y); } all+=n; sort(p+1,p+n+1,[](pair<int,int>u,pair<int,int>v){return u.first+u.second<v.first+v.second;}); while(!P.empty())P.pop();while(!Q.empty())Q.pop();PRE=SUF=0; for(int i=1;i<=n;i++){ PRE+=p[i].first,PRE+=p[i].second; P.push(p[i].first),P.push(p[i].second); while(P.size()!=Q.size())PRE-=P.top(),SUF+=P.top(),Q.push(-P.top()),P.pop(); while(P.top()>-Q.top()){ int x=P.top(),y=-Q.top(); PRE-=x,PRE+=y; SUF+=x,SUF-=y; P.pop(),Q.pop(); P.push(y),Q.push(-x); } pre[i]=SUF-PRE; } while(!P.empty())P.pop();while(!Q.empty())Q.pop();PRE=SUF=0; for(int i=n;i>=1;i--){ PRE+=p[i].first,PRE+=p[i].second; P.push(p[i].first),P.push(p[i].second); while(P.size()!=Q.size())PRE-=P.top(),SUF+=P.top(),Q.push(-P.top()),P.pop(); while(P.top()>-Q.top()){ int x=P.top(),y=-Q.top(); PRE-=x,PRE+=y; SUF+=x,SUF-=y; P.pop(),Q.pop(); P.push(y),Q.push(-x); } suf[i]=SUF-PRE; } if(m==1)mn=min(pre[n],suf[1]); else for(int i=0;i<=n;i++)mn=min(mn,pre[i]+suf[i+1]); printf("%lld\n",all+mn); return 0; } ``` # XXII.[CF477E Dreamoon and Notepad](https://www.luogu.com.cn/problem/CF477E) [题解](https://www.luogu.com.cn/blog/Troverld/solution-cf477e) # XXIII.[[JOI 2020 Final] 火事](https://www.luogu.com.cn/problem/P6881) [题解](https://www.luogu.com.cn/blog/Troverld/solution-p6881) # XXIV.[[Code+#1]Yazid 的新生舞会](https://www.luogu.com.cn/problem/P4062) 关于众数，我们通常是对于每个数求出它作为众数的区间数。 考虑某个数 $x$。我们可以发现，如果令 $a_i=x$ 的所有位置有 $b_i=1$，其余位置有 $b_i=-1$，则如果某个区间 $[l,r]$ 关于 $b$ 的区间和 $>0$ 的话，则有 $x$ 是 $[l,r]$ 的绝对众数。 考虑区间和可以被拆成前缀和之差。于是我们考虑求出 $b$ 的前缀和 $s$ 数组。则，对于位置 $i$，我们需要找出有多少个 $j$，满足 $j<i\land s_j<s_i$。 这明显是二维数点问题，常规做法是线段树。但是，我们不能对所有颜色全部从头到尾做一遍二维数点，不然复杂度就是 $O(n^2\log n)$ 的。考虑 $s_i$ 数组有何性质。 稍加观察可以发现，$s$ 数组在大部分位置都是有 $s_i=s_{i-1}-1$ 的，只有在 $a_i=x$ 处才会出现例外；于是我们就可以考虑相邻的两个 $a_j=a_i=x$。它实际在线段树上的贡献，是 $[s_j,s_i)$ 区间 $+1$，可以直接完成。 然后考虑一个单独的 $a_i$，我们要做的是在线段树上求前缀和；现在既然是 $[j,i)$ 的区间了，那么我们就对 $[s_j,s_i)$ 中的所有东西都求前缀和。实际上就是对线段树上每个位置乘上了一个系数，直接在线段树上同时维护系数即可。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,a[500100]; vector<int>v[500100]; ll res; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>=0?(l+r)>>1:(l+r-1)>>1) struct Segtree{ int tag,sum; ll mus; }seg[4001000]; void ADD(int x,int l,int r,int y=1){seg[x].tag+=y,seg[x].sum+=(r-l+1)*y,seg[x].mus+=1ll*((n-l)+(n-r))*(r-l+1)*y/2;} void pushdown(int x,int l,int r){ADD(lson,l,mid,seg[x].tag),ADD(rson,mid+1,r,seg[x].tag),seg[x].tag=0;} void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum,seg[x].mus=seg[lson].mus+seg[rson].mus;} void reset(int x,int l,int r){ seg[x].tag=seg[x].sum=seg[x].mus=0; if(l==r)return; if(seg[lson].sum)reset(lson,l,mid); if(seg[rson].sum)reset(rson,mid+1,r); } void modify(int x,int l,int r,int L,int R){ if(l>R||r<L)return; if(L<=l&&r<=R)ADD(x,l,r); else pushdown(x,l,r),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R),pushup(x); } ll querytri(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].mus-1ll*seg[x].sum*(n-R-1); pushdown(x,l,r); return querytri(lson,l,mid,L,R)+querytri(rson,mid+1,r,L,R); } ll querypla(int x,int l,int r,int L,int R){ if(l>=L)return 0; if(r<L)return 1ll*seg[x].sum*(R-L+1); pushdown(x,l,r); return querypla(lson,l,mid,L,R)+querypla(rson,mid+1,r,L,R); } int main(){ scanf("%d%d",&n,&a[0]); for(int i=0;i<n;i++)v[i].push_back(0); for(int i=1;i<=n;i++)scanf("%d",&a[i]),v[a[i]].push_back(i); for(int i=0;i<n;i++)v[i].push_back(n+1); for(int i=0;i<n;i++){ if(v[i].size()==2)continue; int las=0; for(int j=1;j+1<v[i].size();j++){ // printf("ADD:[%d,%d]\n",las-(v[i][j]-v[i][j-1]-1),las); modify(1,-n,n,las-(v[i][j]-v[i][j-1]-1),las); las-=(v[i][j]-v[i][j-1]-1)-1; res+=querytri(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1)+querypla(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1); // printf("SUM:[%d,%d]:%lld\n",las-(v[i][j+1]-v[i][j]),las-1,query(1,-n,n,las-(v[i][j+1]-v[i][j]),las-1)); } reset(1,-n,n); } printf("%lld\n",res); return 0; } ``` # XXV.[CF702F T-Shirts](https://www.luogu.com.cn/problem/CF702F) 一句没有输出的调试语句忘删了，然后浪费了半小时debug\kk…… 首先观察到我们可以将所有物品按照quality为第一关键字递减排序，然后再关于price为第二关键字排序，这样所有人购买的东西就都必定是按照其一个子序列的顺序购买的。 于是把询问离线下来，然后就转成了对于所有 $\geq c$ 的询问，将其值减去 $c$ 的套路问题。 然后这就是[某道原题](http://www.lydsy.com/JudgeOnline/problem.php?id=4923)了。因为该原题以前是做过的，这里不再赘述（直接上平衡树暴力维护即可） 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,rt; pair<int,int>p[200100],q[200100]; struct Treap{ int ch[2],rd,val,tot,tagv,tagt; }t[200100]; #define lson t[x].ch[0] #define rson t[x].ch[1] void SUB(int x,int y){t[x].val-=y,t[x].tagv+=y;} void ADD(int x,int y=1){t[x].tot+=y,t[x].tagt+=y;} void pushdown(int x){ if(lson)SUB(lson,t[x].tagv),ADD(lson,t[x].tagt); if(rson)SUB(rson,t[x].tagv),ADD(rson,t[x].tagt); t[x].tagt=t[x].tagv=0; } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].rd>t[y].rd){pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y);return x;} else{pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]);return y;} } void split(int x,int k,int &u,int &v){ if(!x){u=v=0;return;} pushdown(x); if(t[x].val<k)u=x,split(rson,k,rson,v); else v=x,split(lson,k,u,lson); } void reset(int &RT,int x){ if(!x)return; pushdown(x); int a,b; split(RT,t[x].val,a,b); reset(a,lson),reset(b,rson); lson=rson=0; RT=merge(merge(a,x),b); } void func(int k){ int a,b,c; split(rt,k,a,b); if(b)ADD(b),SUB(b,k); split(b,2*k,b,c); reset(a,b); rt=merge(a,c); } void iterate(int x){ if(!x)return; pushdown(x); iterate(lson),iterate(rson); } int stk[200100],tp; int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } void print(int x){if(x<=9)putchar('0'+x);else print(x/10),putchar('0'+x%10);} int main(){ m=read(); for(int i=1;i<=m;i++)p[i].second=read(),p[i].first=-read();sort(p+1,p+m+1); n=read();for(int i=1;i<=n;i++)q[i].first=t[i].val=read(),q[i].second=i,t[i].rd=rand()*rand(); sort(q+1,q+n+1); for(int i=1;i<=n;i++){ int x=q[i].second; while(tp&&t[stk[tp]].rd<t[x].rd)t[x].ch[0]=stk[tp--]; if(tp)t[stk[tp]].ch[1]=x; stk[++tp]=x; }rt=stk[1]; for(int i=1;i<=m;i++)func(p[i].second); iterate(rt);for(int i=1;i<=n;i++)printf("%d",t[i].tot),putchar(' '); return 0; } ``` # XXVI.[CF1458C Latin Square](https://www.luogu.com.cn/problem/CF1458C) 实际上此题使用的数据结构不很高级，甚至可以说很不高级——因为全程只用了数组。但是本题的思想绝对是非常高级的。 我们考虑上数据结构维护该操作。上下左右移动显然是没问题的；但是行中列中轮换应该咋办呢？ 我们先考虑如果只有行上轮换应该怎么办。这玩意没什么好的数据结构维护，但如果我们把它二维数点地展开成$(i,p_i)$就会发现，轮换一次就是$(i,p_i)\rightarrow(p_i,i)$，即交换两维。这也是轮换的一个奇妙性质。 然后我们把它换成三维坐标$(i,j,a_{i,j})$，就会发现行上轮换就是交换$i,a_{i,j}$，列上轮换就是交换$j,a_{i,j}$。这时候便很好维护了。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int T,n,m,a[1010][1010],b[1010][1010],p[3],d[3],t[3]; char s[100100]; int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]),a[i][j]--; scanf("%s",s); for(int i=0;i<3;i++)p[i]=i,d[i]=0; for(int i=0;i<m;i++){ if(s[i]=='U')(d[p[0]]+=n-1)%=n; if(s[i]=='D')(++d[p[0]])%=n; if(s[i]=='L')(d[p[1]]+=n-1)%=n; if(s[i]=='R')(++d[p[1]])%=n; if(s[i]=='I')swap(p[1],p[2]); if(s[i]=='C')swap(p[0],p[2]); } for(t[0]=0;t[0]<n;t[0]++)for(t[1]=0;t[1]<n;t[1]++){ t[2]=a[t[0]][t[1]]; b[(t[p[0]]+d[p[0]])%n][(t[p[1]]+d[p[1]])%n]=(t[p[2]]+d[p[2]])%n; } for(int i=0;i<n;i++){for(int j=0;j<n;j++)printf("%d ",b[i][j]+1);puts("");}puts(""); } return 0; } ``` # XXVII.[CF573E Bear and Bowling](https://www.luogu.com.cn/problem/CF573E) 考虑暴力的DP。设 $f_{i,j}$ 表示前 $i$ 个元素中选择长度为 $j$ 的子序列所能得到的最大收益。 考虑由 $f_i$ 转移到 $f_{i+1}$。明显，一共有两种转移方式：$f_{i,j}\rightarrow f_{i+1,j}$，或 $f_{i,j}+(j+1)a_{i+1}\rightarrow f_{i+1,j+1}$ 大胆猜测，采取转移一的，一定是 $f_i$ 上一段前缀（可以用暴力莽一下试试看）。于是我们全程采取一棵平衡树维护每个 $f_i$ 数组。当进行转移的时候，二分求出上述分界点（这里不能使用平衡树上二分，因为需要同时检查相邻两个数的值）。然后就是单点插入、区间等差数列加了，都是基础操作。 总复杂度 $O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll res; int n,a[100100],rt,cnt; struct Treap{ int ch[2],sz,rd; ll val,tag,dif; }t[100100]; #define lson t[x].ch[0] #define rson t[x].ch[1] void pushup(int x){t[x].sz=t[lson].sz+t[rson].sz+1;} void ADD(int x,ll val,ll dif){t[x].val+=val,t[x].tag+=val,t[x].dif+=dif;} void pushdown(int x){ if(lson)ADD(lson,t[x].tag-t[x].dif*(t[t[lson].ch[1]].sz+1),t[x].dif); if(rson)ADD(rson,t[x].tag+t[x].dif*(t[t[rson].ch[0]].sz+1),t[x].dif); t[x].dif=t[x].tag=0; } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].rd>t[y].rd){pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y),pushup(x);return x;} else{pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y);return y;} } void split(int x,int k,int &u,int &v){ if(!x){u=v=0;return;} pushdown(x); if(t[lson].sz>=k)v=x,split(lson,k,u,lson); else u=x,split(rson,k-t[lson].sz-1,rson,v); pushup(x); } ll kth(int k){ if(!k)return 0; int a,b,c; split(rt,k-1,a,b); split(b,1,b,c); ll ret=t[b].val; rt=merge(merge(a,b),c); return ret; } void Insert(int k,ll y){//insert an element and let it be the k-th one int a,b; split(rt,k-1,a,b); int x=++cnt; t[x].val=y,t[x].rd=rand()*rand(); rt=merge(merge(a,x),b); } void Add(int k,int y){ int a,b; split(rt,k-1,a,b); t[b].val+=1ll*(k+t[t[b].ch[0]].sz)*y; t[b].tag+=1ll*(k+t[t[b].ch[0]].sz)*y; t[b].dif+=y; rt=merge(a,b); } void Iterate(int x){ if(!x)return; pushdown(x),Iterate(lson),Iterate(rson); res=max(res,t[x].val); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ int l=1,r=i; while(l<r){ int mid=(l+r)>>1; if(kth(mid-1)+1ll*a[i]*mid>=kth(mid))r=mid; else l=mid+1; } Insert(r,kth(r-1)); Add(r,a[i]); } Iterate(rt); printf("%lld\n",res); return 0; } ``` # XXVIII.[[UOJ#576][ULR#1]服务器调度](https://uoj.ac/problem/576) 非常可怕的大数据结构题，原版代码整整码了9K，就算稍微合并合并也剩下7K…… 首先，我们考虑对每种颜色，建出一棵虚树。考虑求出虚树的一条直径。则有个结论是原树上到任意一点最远的点肯定是此直径的端点之一。 例如，我们考虑下方的这棵树： ``` O / \ Z V / \ M Y / \ X U ``` 设我们求出虚树的直径是 `X,Y`。我们考虑求出该直径的中点是 `M`。则显然，`M` 一定位于 `X` 和 `Y` 中深度更大的那一个节点到二者 `LCA` 的路径上。例如，在上图中，就可以看到图上的 `M` 在深度更大的 `X` 一侧。我们在接下来的讲解中，都会默认 `X` 是更深的那一个。同时，可以找到它们的 `LCA` 是 `Z`。 则，`M` 及 `M` 子树中所有节点，关于此种颜色的最远点都是 `Y`；而 `M` 子树外所有节点的最远点都是 `X`。 ------ 我们先考虑子树中的一个点，上述的 `U`。明显，此种颜色对其贡献，是 $dis_U+dis_Y-2dis_{\text{lca}(U,Y)}$。 我们发现，必有 $\text{lca}(U,Y)=Z$。故上式可以被转换成 $dis_U+dis_Y-2dis_Z$。 此式可以被拆作两部分——$dis_U$，此部分我们接下来再说。$dis_Y-2dis_Z$，其对于 `M` 子树中所有点（即所有可能的 `U`）都是常数，故我们可以直接上一棵线段树对其进行子树加来维护此部分。 ------ 我们再考虑子树外的一个点，上述的 `V`。则此种颜色对其贡献是 $dis_V+dis_X-2dis_{\text{lca}(V,X)}$。 此式可以被拆作三部分。第一部分，$dis_V$。结合上前面的 $dis_U$，我们发现其范围就是整棵树。则，每种颜色都会对整棵树覆盖一次，一共有 $m$ 种颜色，则一共会覆盖 $m$ 次。在询问时，我们直接上一个前缀和维护子树中所有东西的 $dis$ 之和，再乘上一个 $m$ 即为此部分答案。 第二部分，$dis_X$。其仍是常数，仍可使用我们上述的子树加线段树处理。 第三部分，$-2dis_{\text{lca}(V,X)}$。其可被先转换成 $-2dis_{\text{lca}(V,M)}$，但仍然不好处理。 我们考虑对 `M` 到根的路径上**所有边**都打上一个 $-2$ 的 `tag`（使用树剖）。这样，点 `V` 到根的路径上所有边的长度的带权（权为 `tag`）和就是 $dis_{\text{lca}(V,M)}$。但是，一个问题是，此方案不仅会影响 `M` 子树外的点，更会影响 `M` 子树中的点。 但是，我们发现，此方案对 `M` 子树中所有点的影响都是固定的——都是 $-2dis_M$。故我们直接仍在上述子树加线段树上把这部分影响给它补回去即可，即执行子树加 $2dis_M$。 ------ 我们再来考虑求答案时的操作。子树加线段树上的操作以及前缀和之类的都可以简单完成。关键还是上述 `V` 的第三部分操作比较烦人——它要求出子树中所有点到根路径的带权距离和。设当前询问的点是 `Q`。 考虑每条边被覆盖多少次。明显，`Q` 到根路径上所有边，覆盖其的路径数量都为 `Q` 的子树大小。故我们只需求出 `Q` 到根路径的带权长度，再乘上 `Q` 的子树大小，即为此部分贡献。到根路径的带权长度，仍可使用树剖解决。 而考虑 `Q` 子树中的任意一条边 `X-Y`，其中 `X` 是 `Y` 的父亲，其被覆盖了 `Y` 子树大小次。故我们仍可以求带权子树和，此处权仍然是边上的 `tag`，但值是 $\text{边的长度}\times\text{Y子树大小}$。则其可再开一棵线段树解决。 ------ 于是我们便解决了这个问题。剩下的就是我们之前忽略的一些问题了。例如，对于每种颜色，如何维护其直径？ 众所周知的是，有一个结论，两组点集合并时，新点集的直径的端点一定来自于两点集中原本的直径端点（不管其是来自于同一点集还是不同点集）。这就意味着我们可以使用线段树维护不同颜色的端点了（当然，用的是动态开点线段树。实际上直接开 $m$ 棵平衡树维护也不失为一个好选择，但是那样子码量和常数都会噌噌上涨）。 ------ 最后是具体实现时的一些问题。例如，虽然总复杂度是 $O(n\log^2n)$ 的（来自于树剖），但是事实上是常数极大（毕竟我们前面开了好几棵线段树），需要榨取所有可以被优化的常数。所以，求直径时用 $O(1)$ 的 `RMQ-LCA` 罢。而同时，为了实现求一条直径的中点，我们还要再预处理倍增数组以方便树上二分。~~于是你将会发现本题需要全部三种LCA算法~~。 同时，因为各种东西全掺在一块会使得条理很不清晰，大剂量的 `namespace` 等封装在 `debug` 时是很有必要的（同时，也方便把已经 `debug` 完的部分缩起来避免看偏） 但是，就算这样说，最后还免不得TLE的悲惨命运。以下是TLE的初版代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; const int N=200100; int col[N]; int dep[N],dis[N],fa[N],dfn[N],rev[N],top[N],sz[N],num[N]; namespace TRE{//works about the original tree int head[N],cnt; struct node{int to,next,val;}edge[N]; void ae(int u,int v,int w){edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;} namespace SPR{//tree-chain separation. int tot,son[N]; void dfs1(int x){ sz[x]=1; for(int i=head[x],y;i!=-1;i=edge[i].next){ dep[y=edge[i].to]=dep[x]+1,dis[y]=dis[x]+edge[i].val,fa[y]=x,dfs1(y),sz[x]+=sz[y]; if(sz[y]>=sz[son[x]])son[x]=y; } } void dfs2(int x){ dfn[x]=++tot,rev[tot]=x; if(!top[x])top[x]=x; if(son[x])top[son[x]]=top[x],dfs2(son[x]); for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=son[x])dfs2(edge[i].to); } } namespace ST{//ST table for LCA part int MN[N<<1][20],LG[N<<1],FIR[N],lim; void dfs(int x){ MN[++lim][0]=x,FIR[x]=lim; for(int i=head[x];i!=-1;i=edge[i].next)dfs(edge[i].to),MN[++lim][0]=x; } int MIN(int x,int y){return dep[x]<dep[y]?x:y;} void init(){ for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1; for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)MN[i][j]=MIN(MN[i][j-1],MN[i+(1<<(j-1))][j-1]); } int LCA(int x,int y){ x=FIR[x],y=FIR[y]; if(x>y)swap(x,y); int k=LG[y-x+1]; return MIN(MN[x][k],MN[y-(1<<k)+1][k]); } int DIS(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];} } using ST::LCA; namespace DOB{//doubling on tree part for ancestor tracing int anc[N<<1][20]; void init(){ for(int i=1;i<=n;i++)anc[i][0]=fa[i]; for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1]; } int MID(int &x,int &y){//using doubling on tree to calculate the midpoint of a route int z=LCA(x,y); if(dis[x]<=dis[y])swap(x,y); int r=x; for(int i=19;i>=0;i--)if(dep[r]-(1<<i)>=dep[z]&&dis[x]-dis[anc[r][i]]<=dis[y]+dis[anc[r][i]]-2*dis[z])r=anc[r][i]; return r; } } void init(){SPR::dfs1(1),SPR::dfs2(1),ST::dfs(1),ST::init(),DOB::init();} } using TRE::LCA; using TRE::DOB::MID; using TRE::ST::DIS; namespace DIA{//calculating the diameter of the tree int rt[N],cnt,bin[N*20],tp; struct SegTree{//a dynamic-nodeadding segtree, calculating diameters of each colour's virtual trees int lson,rson,u,v; }seg[N*20]; #define mid ((l+r)>>1) void pushup(int &x){ seg[x].u=seg[x].v=0; if(!seg[x].lson&&!seg[x].rson){bin[++tp]=x,x=0;return;} if(!seg[x].rson){seg[x].u=seg[seg[x].lson].u,seg[x].v=seg[seg[x].lson].v;return;} if(!seg[x].lson){seg[x].u=seg[seg[x].rson].u,seg[x].v=seg[seg[x].rson].v;return;} int a[4]={seg[seg[x].lson].u,seg[seg[x].lson].v,seg[seg[x].rson].u,seg[seg[x].rson].v}; for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)if((!seg[x].u&&!seg[x].v)||DIS(seg[x].u,seg[x].v)<DIS(a[i],a[j]))seg[x].u=a[i],seg[x].v=a[j]; } int NewNode(){return tp?bin[tp--]:++cnt;} void Insert(int &x,int l,int r,int P){ // printf("%d %d:%d\n",l,r,P); if(l>P||r<P)return; if(!x)x=NewNode(); if(l==r){seg[x].u=seg[x].v=rev[P];return;} Insert(seg[x].lson,l,mid,P),Insert(seg[x].rson,mid+1,r,P),pushup(x); } void Delete(int &x,int l,int r,int P){ if(l>P||r<P)return; if(l==r){seg[x].u=seg[x].v=0,bin[++tp]=x,x=0;return;} Delete(seg[x].lson,l,mid,P),Delete(seg[x].rson,mid+1,r,P),pushup(x); } // void Iterate(int x,int l,int r){ // if(!x)return; // printf("%d:[%d,%d]:(%d,%d)\n",x,l,r,seg[x].u,seg[x].v); // Iterate(seg[x].lson,l,mid),Iterate(seg[x].rson,mid+1,r); // } #undef mid } ll sumdis[N]; namespace SUB{ #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ll sum,tag;}seg[N<<2]; void ADD(int x,int l,int r,ll y){seg[x].sum+=y*(r-l+1),seg[x].tag+=y;} void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;} void pushdown(int x,int l,int r){ADD(lson,l,mid,seg[x].tag),ADD(rson,mid+1,r,seg[x].tag),seg[x].tag=0;} void modify(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(L<=l&&r<=R){ADD(x,l,r,val);return;} pushdown(x,l,r),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x); } ll query(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; pushdown(x,l,r);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R); } #undef lson #undef rson #undef mid } namespace ALT{//segtree of alter-subtree jobs(using SPR things) namespace SBT{//segment tree for subtree works #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ll sumsz,tag,sum;}seg[N<<2]; void ADD(int x,ll y){seg[x].tag+=y,seg[x].sum+=y*seg[x].sumsz;} void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;} void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;} void build(int x,int l,int r){ if(l==r){seg[x].sumsz=1ll*sz[rev[l]]*num[rev[l]];return;} build(lson,l,mid),build(rson,mid+1,r),seg[x].sumsz=seg[lson].sumsz+seg[rson].sumsz; } void modify(int x,int l,int r,int L,int R,ll val){ if(l>R||r<L)return; if(L<=l&&r<=R){ADD(x,val);return;} pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x); } ll query(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; pushdown(x);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R); } #undef lson #undef rson #undef mid } namespace CHT{//segtree of chain jobs #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ll sumnum,tag,sum;}seg[N<<2]; void ADD(int x,ll y){seg[x].tag+=y,seg[x].sum+=y*seg[x].sumnum;} void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;} void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum;} void build(int x,int l,int r){ if(l==r){seg[x].sumnum=num[rev[l]];return;} build(lson,l,mid),build(rson,mid+1,r),seg[x].sumnum=seg[lson].sumnum+seg[rson].sumnum; } void modify(int x,int l,int r,int L,int R,ll val){ if(l>R||r<L)return; if(L<=l&&r<=R){ADD(x,val);return;} pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x); } ll query(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; pushdown(x);return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R); } #undef lson #undef rson #undef mid } void modify(int l,int r,int val){SBT::modify(1,1,n,l,r,val),CHT::modify(1,1,n,l,r,val);} void chainmod(int x,int val){while(x)modify(dfn[top[x]],dfn[x],val),x=fa[top[x]];} ll chainsum(int x){ll ret=0;while(x)ret+=CHT::query(1,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];return ret;} } void diameter(int x,int y,int dir){//works need to do when have a diameter of (x-y). int m=MID(x,y); int z=LCA(x,y); // printf("%d %d %d %d\n",x,y,m,z); // printf("%d %d %d %d\n",x,y,m,z); SUB::modify(1,1,n,dfn[m],dfn[m]+sz[m]-1,dir*(dis[y]-2*dis[z]+2*dis[m])); // printf("SUB%d:%d\n",m,dis[y]-2*dis[z]); // printf("ALTER%d:%d\n",m,dis[x]); // printf("CHAIN%d:%d\n",m,-2); SUB::modify(1,1,n,1,dfn[m]-1,dir*dis[x]); SUB::modify(1,1,n,dfn[m]+sz[m],n,dir*dis[x]); ALT::chainmod(m,-2*dir); } int m,q; ll query(int x){ ll res=0; res+=(sumdis[dfn[x]+sz[x]-1]-sumdis[dfn[x]-1])*m; res+=SUB::query(1,1,n,dfn[x],dfn[x]+sz[x]-1); // printf("CHAS:%d\n",ALT::chainsum(fa[x])); // printf("SBT:%d\n",ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1)); res+=ALT::chainsum(fa[x])*sz[x]; res+=ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1); return res; } #define dia(i) DIA::seg[DIA::rt[i]].u,DIA::seg[DIA::rt[i]].v int main(){ scanf("%d%d%d",&n,&m,&q),memset(TRE::head,-1,sizeof(TRE::head)); for(int i=1;i<=n;i++)scanf("%d",&col[i]); for(int i=2;i<=n;i++)scanf("%d",&fa[i]); for(int i=2;i<=n;i++)scanf("%d",&num[i]),TRE::ae(fa[i],i,num[i]); TRE::init(); ALT::SBT::build(1,1,n); ALT::CHT::build(1,1,n); // for(int i=1;i<=n;i++)printf("%d:FA:%d SZ:%d SN:%d DF:%d RV:%d TP:%d DP:%d\n",i,fa[i],sz[i],TRE::SPR::son[i],dfn[i],rev[i],top[i],dep[i]); for(int i=1;i<=n;i++)sumdis[i]=sumdis[i-1]+dis[rev[i]]; for(int i=1;i<=n;i++)DIA::Insert(DIA::rt[col[i]],1,n,dfn[i]); // diameter(dia(4),1); // m=1; // printf("%d\n",query(4)); // m=4; // diameter(dia(4),-1); for(int i=1;i<=m;i++)diameter(dia(i),1); for(int t,x;q;q--){ scanf("%d%d",&t,&x); if(t==1){ diameter(dia(col[x]),-1),DIA::Delete(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1); scanf("%d",&col[x]); diameter(dia(col[x]),-1),DIA::Insert(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1); }else printf("%lld\n",query(x)); } return 0; } ``` 最终，我用树状数组替换掉了其中三棵线段树（将其模板化）。最终便卡过去了。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; const int N=200100; int col[N]; int dep[N],dis[N],fa[N],dfn[N],rev[N],top[N],sz[N],num[N]; namespace TRE{//works about the original tree int head[N],cnt; struct node{int to,next,val;}edge[N]; void ae(int u,int v,int w){edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;} namespace SPR{//tree-chain separation. int tot,son[N]; void dfs1(int x){ sz[x]=1; for(int i=head[x],y;i!=-1;i=edge[i].next){ dep[y=edge[i].to]=dep[x]+1,dis[y]=dis[x]+edge[i].val,fa[y]=x,dfs1(y),sz[x]+=sz[y]; if(sz[y]>=sz[son[x]])son[x]=y; } } void dfs2(int x){ dfn[x]=++tot,rev[tot]=x; if(!top[x])top[x]=x; if(son[x])top[son[x]]=top[x],dfs2(son[x]); for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=son[x])dfs2(edge[i].to); } } namespace ST{//ST table for LCA part int MN[N<<1][20],LG[N<<1],FIR[N],lim; void dfs(int x){ MN[++lim][0]=x,FIR[x]=lim; for(int i=head[x];i!=-1;i=edge[i].next)dfs(edge[i].to),MN[++lim][0]=x; } int MIN(int x,int y){return dep[x]<dep[y]?x:y;} void init(){ for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1; for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)MN[i][j]=MIN(MN[i][j-1],MN[i+(1<<(j-1))][j-1]); } int LCA(int x,int y){ x=FIR[x],y=FIR[y]; if(x>y)swap(x,y); int k=LG[y-x+1]; return MIN(MN[x][k],MN[y-(1<<k)+1][k]); } int DIS(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];} } using ST::LCA; namespace DOB{//doubling on tree part for ancestor tracing int anc[N<<1][20]; void init(){ for(int i=1;i<=n;i++)anc[i][0]=fa[i]; for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1]; } int MID(int &x,int &y){//using doubling on tree to calculate the midpoint of a route int z=LCA(x,y); if(dis[x]<=dis[y])swap(x,y); int r=x; for(int i=19;i>=0;i--)if(dep[r]-(1<<i)>=dep[z]&&dis[x]-dis[anc[r][i]]<=dis[y]+dis[anc[r][i]]-2*dis[z])r=anc[r][i]; return r; } } void init(){SPR::dfs1(1),SPR::dfs2(1),ST::dfs(1),ST::init(),DOB::init();} } using TRE::LCA; using TRE::DOB::MID; using TRE::ST::DIS; namespace DIA{//calculating the diameter of the tree int rt[N],cnt,bin[N*20],tp; struct SegTree{//a dynamic-nodeadding segtree, calculating diameters of each colour's virtual trees int lson,rson,u,v; }seg[N*20]; #define mid ((l+r)>>1) void pushup(int &x){ seg[x].u=seg[x].v=0; if(!seg[x].lson&&!seg[x].rson){bin[++tp]=x,x=0;return;} if(!seg[x].rson){seg[x].u=seg[seg[x].lson].u,seg[x].v=seg[seg[x].lson].v;return;} if(!seg[x].lson){seg[x].u=seg[seg[x].rson].u,seg[x].v=seg[seg[x].rson].v;return;} int a[4]={seg[seg[x].lson].u,seg[seg[x].lson].v,seg[seg[x].rson].u,seg[seg[x].rson].v}; for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)if((!seg[x].u&&!seg[x].v)||DIS(seg[x].u,seg[x].v)<DIS(a[i],a[j]))seg[x].u=a[i],seg[x].v=a[j]; } int NewNode(){return tp?bin[tp--]:++cnt;} void Insert(int &x,int l,int r,int P){ // printf("%d %d:%d\n",l,r,P); if(l>P||r<P)return; if(!x)x=NewNode(); if(l==r){seg[x].u=seg[x].v=rev[P];return;} Insert(seg[x].lson,l,mid,P),Insert(seg[x].rson,mid+1,r,P),pushup(x); } void Delete(int &x,int l,int r,int P){ if(l>P||r<P)return; if(l==r){seg[x].u=seg[x].v=0,bin[++tp]=x,x=0;return;} Delete(seg[x].lson,l,mid,P),Delete(seg[x].rson,mid+1,r,P),pushup(x); } // void Iterate(int x,int l,int r){ // if(!x)return; // printf("%d:[%d,%d]:(%d,%d)\n",x,l,r,seg[x].u,seg[x].v); // Iterate(seg[x].lson,l,mid),Iterate(seg[x].rson,mid+1,r); // } #undef mid } struct BIT{//a universal template of fenwick tree ll s[N];//the prefix sum of original array ll t1[N],t2[N];//the unweighted and weighted fenwick ll&operator[](const int &x){return s[x];} BIT(){memset(s,0,sizeof(s)),memset(t1,0,sizeof(t1)),memset(t2,0,sizeof(t2));} void ADD(int x,int y){for(int i=x;i<=n;i+=i&-i)t1[i]+=y,t2[i]+=1ll*s[x-1]*y;} ll SUM(int x){ ll sum=0; for(int i=x;i;i-=i&-i)sum+=t1[i]; sum*=s[x]; for(int i=x;i;i-=i&-i)sum-=t2[i]; return sum; } void ADD(int l,int r,int val){if(l<=r)ADD(l,val),ADD(r+1,-val);} ll SUM(int l,int r){return SUM(r)-SUM(l-1);} }SUB,SBT,CHT; ll sumdis[N]; namespace ALT{//segtree of alter-subtree jobs(using SPR things) void modify(int l,int r,int val){SBT.ADD(l,r,val),CHT.ADD(l,r,val);} void chainmod(int x,int val){while(x)modify(dfn[top[x]],dfn[x],val),x=fa[top[x]];} ll chainsum(int x){ll ret=0;while(x)ret+=CHT.SUM(dfn[top[x]],dfn[x]),x=fa[top[x]];return ret;} } void diameter(int x,int y,int dir){//works need to do when have a diameter of (x-y). int m=MID(x,y); int z=LCA(x,y); SUB.ADD(dfn[m],dfn[m]+sz[m]-1,dir*(dis[y]-2*dis[z]+2*dis[m])); SUB.ADD(1,dfn[m]-1,dir*dis[x]); SUB.ADD(dfn[m]+sz[m],n,dir*dis[x]); ALT::chainmod(m,-2*dir); } int m,q; ll query(int x){ ll res=0; res+=(sumdis[dfn[x]+sz[x]-1]-sumdis[dfn[x]-1])*m; res+=SUB.SUM(dfn[x],dfn[x]+sz[x]-1); // printf("CHAS:%d\n",ALT::chainsum(fa[x])); // printf("SBT:%d\n",ALT::SBT::query(1,1,n,dfn[x],dfn[x]+sz[x]-1)); res+=ALT::chainsum(fa[x])*sz[x]; res+=SBT.SUM(dfn[x],dfn[x]+sz[x]-1); return res; } #define dia(i) DIA::seg[DIA::rt[i]].u,DIA::seg[DIA::rt[i]].v int main(){ scanf("%d%d%d",&n,&m,&q),memset(TRE::head,-1,sizeof(TRE::head)); for(int i=1;i<=n;i++)scanf("%d",&col[i]); for(int i=2;i<=n;i++)scanf("%d",&fa[i]); for(int i=2;i<=n;i++)scanf("%d",&num[i]),TRE::ae(fa[i],i,num[i]); TRE::init(); for(int i=1;i<=n;i++)SUB[i]=i; for(int i=1;i<=n;i++)SBT[i]=SBT[i-1]+1ll*sz[rev[i]]*num[rev[i]]; for(int i=1;i<=n;i++)CHT[i]=CHT[i-1]+num[rev[i]]; // for(int i=1;i<=n;i++)printf("%d:FA:%d SZ:%d SN:%d DF:%d RV:%d TP:%d DP:%d\n",i,fa[i],sz[i],TRE::SPR::son[i],dfn[i],rev[i],top[i],dep[i]); for(int i=1;i<=n;i++)sumdis[i]=sumdis[i-1]+dis[rev[i]]; for(int i=1;i<=n;i++)DIA::Insert(DIA::rt[col[i]],1,n,dfn[i]); // diameter(dia(4),1); // m=1; // printf("%d\n",query(4)); // m=4; // diameter(dia(4),-1); for(int i=1;i<=m;i++)diameter(dia(i),1); for(int t,x;q;q--){ scanf("%d%d",&t,&x); if(t==1){ diameter(dia(col[x]),-1),DIA::Delete(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1); scanf("%d",&col[x]); diameter(dia(col[x]),-1),DIA::Insert(DIA::rt[col[x]],1,n,dfn[x]),diameter(dia(col[x]),1); }else printf("%lld\n",query(x)); } return 0; } ``` # XXIX.[CF576E Painting Edges](https://www.luogu.com.cn/problem/CF576E) 首先，这个trick很常见，应该默认就能想到线段树分治的做法。但是，同样可以实现该trick的LCT维护关于删除时间的最大生成树的做法，因为我们并不知道删除时间是什么，所以不太好写（但是是能写的）。故我们只考虑线段树分治做法。 线段树分治，只需要用一个带权并查集维护二分图即可。时间复杂度 $O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,c,q,U[500100],V[500100],nex[500100],las[500100],id[500100],col[500100]; bool res[500100]; struct dat{int u,v,lu,lv;bool ru,rv;dat(int a,int b,int c,int d,bool e,bool f){u=a,v=b,lu=c,lv=d,ru=e,rv=f;}}; struct UFS{ int dsu[500100],len[500100]; bool rev[500100]; stack<dat>s; void init(){for(int i=1;i<=n;i++)dsu[i]=i;} int findfa(int x){return dsu[x]==x?x:findfa(dsu[x]);} bool findcol(int x){return dsu[x]==x?rev[x]:findcol(dsu[x])^rev[x];} bool merge(int u,int v){ bool cu=findcol(u),cv=findcol(v); u=findfa(u),v=findfa(v); if(u==v)return false; if(len[u]>len[v])swap(u,v),swap(cu,cv); s.push(dat(u,v,len[u],len[v],rev[u],rev[v])); len[v]=max(len[v],len[u]+1),dsu[u]=v,rev[u]^=(cu==cv); return true; } bool ask(int u,int v){return findfa(u)!=findfa(v)||findcol(u)!=findcol(v);} void undo(){ dsu[s.top().u]=s.top().u,len[s.top().u]=s.top().lu,rev[s.top().u]=s.top().ru; dsu[s.top().v]=s.top().v,len[s.top().v]=s.top().lv,rev[s.top().v]=s.top().rv; s.pop(); } }t[51]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) vector<int>v[2001000]; void modify(int x,int l,int r,int L,int R,int k){if(l>R||r<L)return;if(L<=l&&r<=R)v[x].push_back(k);else modify(lson,l,mid,L,R,k),modify(rson,mid+1,r,L,R,k);} void solve(int x,int l,int r){ // printf("%d[%d,%d]\n",x,l,r); vector<int>u; for(auto i:v[x])if(t[col[i]].merge(U[id[i]],V[id[i]]))u.push_back(col[i]); if(l==r){ if(t[col[l]].ask(U[id[l]],V[id[l]]))res[l]=true,modify(1,1,q,l+1,nex[l]-1,l); else{ res[l]=false; if(las[l])modify(1,1,q,l+1,nex[l]-1,las[l]); if(nex[l]<=q)las[nex[l]]=las[l]; } }else solve(lson,l,mid),solve(rson,mid+1,r); for(auto i:u)t[i].undo(); } int main(){ scanf("%d%d%d%d",&n,&m,&c,&q); for(int i=1;i<=c;i++)t[i].init(); for(int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]); for(int i=1;i<=q;i++)scanf("%d%d",&id[i],&col[i]),nex[las[id[i]]]=i,las[id[i]]=i; memset(las,0,sizeof(las));for(int i=1;i<=q;i++)if(!nex[i])nex[i]=q+1;else las[nex[i]]=i; solve(1,1,q); for(int i=1;i<=q;i++)puts(res[i]?"YES":"NO"); return 0; } ``` # XXX.[CF505E Mr. Kitayuta vs. Bamboos](https://www.luogu.com.cn/problem/CF505E) “最大值最小”，条件反射套个二分上去。 于是现在问题转变成判定型问题。 正着搞不好处理 $\max(h_i-p,0)$ 这种套了 $\max$ 的限制，干脆正难则反，考虑倒着处理。 于是问题转变为 第 $i$ 天开头所有竹子高度减少 $a_i$，然后你可以选几棵再给它补回来 $p$。目标是所有竹子在结尾时高度不低于 $h_i$，但同时还要保证任意时刻竹子高度不会被减成负数。 如何构造补竹子的顺序呢？考虑贪心——每次总是补那些最快被减成负数的竹子。换句话说，可以用一颗堆来维护所有在结尾时高度低于 $h_i$ 的竹子，因为竹子只要保证最终高度符合要求，对中间的高度除了非零外别无要求，所以此种贪心正确。当前高度不合法，当且仅当某一时刻竹子出现负数或者是最终堆非空（意味着尚有高度不合要求的竹子）。 时间复杂度 $O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,k,p,h[100100],a[100100]; struct dat{ ll tim,tot; int id; dat(ll A,ll B,int C){tim=A,tot=B,id=C;} friend bool operator<(const dat&u,const dat&v){return u.tim>v.tim;} }; priority_queue<dat>q; bool che(ll ip){ while(!q.empty())q.pop(); for(int i=1;i<=n;i++)if(ip-1ll*m*a[i]<h[i])q.push(dat(ip/a[i],ip,i)); for(int i=1;i<=m;i++){ if(!q.empty()&&q.top().tim<i)return false; for(int j=1;j<=k;j++)if(!q.empty()){ dat x=q.top();q.pop(); x.tot+=p,x.tim=x.tot/a[x.id]; if(x.tot-1ll*m*a[x.id]<h[x.id])q.push(x); } } return q.empty(); } int main(){ scanf("%d%d%d%d",&n,&m,&k,&p); for(int i=1;i<=n;i++)scanf("%d%d",&h[i],&a[i]); ll l=1,r=1e14; while(l<r){ ll mid=(l+r)>>1; if(che(mid))r=mid; else l=mid+1; } printf("%lld\n",r); return 0; } ``` # XXXI.[CF626G Raffles](https://www.luogu.com.cn/problem/CF626G) 首先，我们列出“往一个奖池内多投一张彩票”，在奖项为 $c$、初始有 $a$ 张、当前已经又投了 $r$ 张时的额外收益： $$c\times\Big(\dfrac{r+1}{a+r+1}-\dfrac{r}{a+r}\Big)$$ 稍微化简一下就能得到 $$\dfrac{ca}{(a+r+1)(a+r)}$$ 明显，随着 $r$ 的增大，分子不变，分母是增函数，于是整个额外收益就是减函数——这意味着你往一个奖池里投越多彩票，单张彩票所取得的收益就越小。这意味着我们可以搞一个贪心，用一个堆维护所有奖池内再投一张彩票所能取得的收益，然后每次弹出其中的最大值，并将最大值所在的奖池的下一张彩票加入堆中。 现在，它开始修改 $a$ 了，我们应该怎么做呢？ 暴力从当前已投入的所有彩票中，找出收益最小的那一张，并将其与当前未投入的所有彩票中收益最大的那一张比较，若没有未投入的那张大就暴力更换（这意味着要用 `multiset` 来替换堆），直到替换会使答案更劣为止。该做法的正确性显然，但是复杂度是不是不太对劲？ 我们思考一下，仅仅是 $a$ 变换了 $1$，对全局的影响应该不会太大——事实上，受到影响而不再投入的彩票数量是 $O(1)$ 的！ 这样，暴力的正确性和复杂度都有保证。 实现时，不管它“不超过一半”的限制，仅仅把投入一半以上彩票时额外投入一张的收益为 $0$ 会让代码实现简单很多。 时间复杂度 $O(n\log n)$， 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const double eps=1e-12; int n,m,q,a[200100],c[200100],r[200100]; double F(int X,int R){ if(R<0)return 0x3f3f3f3f; if(R>=a[X])return 0; return 1.0*c[X]*a[X]/(a[X]+R+1)/(a[X]+R); } double G(int x){return 1.0*c[x]*min(r[x],a[x])/(a[x]+min(r[x],a[x]));} struct dat{ double val; int id,lot; dat(int X,int Y){id=X,lot=Y,val=F(id,lot);} friend bool operator<(const dat&u,const dat&v){return fabs(u.val-v.val)<eps?u.id<v.id:u.val<v.val;} }; multiset<dat>all,cho; double res; void Push(){ auto it=--cho.end(); res+=it->val; int x=it->id; all.erase(dat(x,r[x]-1)),all.insert(*it); cho.erase(it),cho.insert(dat(x,++r[x])); } void Pop(){ auto it=all.begin(); res-=it->val; int x=it->id; cho.erase(dat(x,r[x])),cho.insert(*it); all.erase(it),all.insert(dat(x,--r[x]-1)); } void read(int &x){ x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } int main(){ read(n),read(m),read(q); for(int i=1;i<=n;i++)read(c[i]); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=n;i++)all.insert(dat(i,-1)),cho.insert(dat(i,0)); while(m--)Push(); // printf("%lf\n",res); for(int i=1,x,y;i<=q;i++){ read(y),read(x); all.erase(dat(x,r[x]-1)),cho.erase(dat(x,r[x])),res-=G(x); if(y==1)a[x]++;else a[x]--; all.insert(dat(x,r[x]-1)),cho.insert(dat(x,r[x])),res+=G(x); while(cho.rbegin()->val>all.begin()->val+eps)Pop(),Push(); printf("%.8lf\n",res); } return 0; } ``` # XXXII.[CF1491H Yuezheng Ling and Dynamic Tree](https://www.luogu.com.cn/problem/CF1491H) 首先，相信大家都做过[[HNOI2010]弹飞绵羊](https://www.luogu.com.cn/problem/P3203)这道经典原题，而这题显然是那题的增强版。 众所周知，该原题有两种常见解法：LCT或分块。凭直觉发现LCT不可能处理这种区间修改问题，于是我们考虑分块。 分块的话，就需要维护一个位置在跳完它所在的那个块后的落点。但这里为了方便求LCA，所以我们借鉴树剖的思想，令 $go_x$ 为离开块前最后一个到达的节点，令 $len_x$ 表示其在块内跳的次数。 我们发现，若一个块被修改了超过块长次，则其中所有元素的 $go_x$ 都必定为其自身，$len_x$ 都必定为 $0$，就可以直接打 `tag` 维护里面所有元素的 $a_x$ 了。 于是对于每次修改，我们暴力重构未满的块，若块长是 $\sqrt{n}$，则一共 $\sqrt n$ 个块，每块被修改 $\sqrt n$ 次，每次修改 $\sqrt n$ 个元素，总复杂度 $O(n\sqrt n)$，可以接受。 下面考虑求LCA。明显，我们可以先跑出从 $x,y$ 到根的路径上所有需要的点（指所有 $go_x$ 及其父亲）的 $dep$，然后就可以像树剖一样处理，直到两个东西的 $go$ 相同。此时它们必在同一块内，直接暴力即可。此部分复杂度 $O(\sqrt n)$。 故总复杂度 $O(n\sqrt n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int BBB=500; int n,m,a[100100],BLK[100100],go[100100],len[100100],dep[100100],lp[510],tag[510],num; bool fin[510]; void rebuild(int id,int L,int R,int x){ if(L<=lp[id]&&R>=lp[id+1]-1&&fin[id]){tag[id]+=x,tag[id]=min(tag[id],n);return;} fin[id]=true; for(int i=lp[id];i<lp[id+1];i++){ a[i]=max(0,a[i]-tag[id]); if(L<=i&&i<=R)a[i]=max(0,a[i]-x); if(a[i]<lp[id])go[i]=i,len[i]=0;else go[i]=go[a[i]],len[i]=len[a[i]]+1,fin[id]=false; } tag[id]=0; } #define fa(x) max(a[x]-tag[BLK[x]],0) int chain(int x){ if(x==0)return dep[x]=0; dep[go[x]]=chain(fa(go[x]))+1; if(!go[x])dep[go[x]]=0; return dep[x]=dep[go[x]]+len[x]; } int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } void modify(){ int L=read()-1,R=read()-1,x=read(); for(int i=BLK[L];i<=BLK[R];i++)rebuild(i,L,R,x); } bool lab[100100]; void LCA(){ // printf("BEF:%d\n",dep[0]); int x=read()-1,y=read()-1; chain(x),chain(y); // printf("AFT:%d\n",dep[0]); while(go[x]!=go[y]){ if(dep[go[x]]<dep[go[y]])swap(x,y); x=fa(go[x]); } lab[0]=true; for(int i=x;i&&BLK[i]==BLK[x];i=fa(i))lab[i]=true; for(int i=y;BLK[i]==BLK[y];i=fa(i))if(lab[i]){printf("%d\n",i+1);break;} for(int i=x;i&&BLK[i]==BLK[x];i=fa(i))lab[i]=false; } int main(){ // freopen("I.in","r",stdin); n=read(),m=read(),a[0]=-1; for(int i=1;i<n;i++)a[i]=read()-1,BLK[i]=i/BBB; lp[num=BLK[n]=BLK[n-1]+1]=n;for(int i=0;i<num;i++)lp[i]=i*BBB; for(int i=0;i<num;i++)rebuild(i,-1,-1,0); for(int i=1;i<=m;i++)if(read()==1)modify();else LCA(); return 0; } ``` # XXXIII.[[APIO2019]路灯](https://www.luogu.com.cn/problem/P5445) 实际上本来是在刷CDQ分治的题来着的，但是CDQ分治是众所周知地抽象，所以在碰到三维数点问题时，除非卡空间，否则一律请选择树套树…… 我们可以用 `set` 来维护连通性。显然，若 $[l,r]$ 这一段的路灯全亮，则所有 $a,b\in[l,r+1]$ 都是合法的。 考虑差分。当一段 $[l,r]$ 初次联通，就矩形加 $T-t$，其中 $T$ 是总时间，$t$ 是当前时间；当其初次不连通，就矩形减 $T-t$。 维护联通与否可以使用珂朵莉树，或者说，`set` 套 `pair`。 明显，这是带时间轴矩形加问题，是三维数点问题，鉴于CDQ太难写，我选择BIT套权值线段树。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,rt[300100],cnt; #define mid ((l+r)>>1) struct node{int lson,rson,tag;}seg[20010000]; void modify(int &x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(!x)x=++cnt; if(L<=l&&r<=R)seg[x].tag+=val; else modify(seg[x].lson,l,mid,L,R,val),modify(seg[x].rson,mid+1,r,L,R,val); } int query(int x,int l,int r,int P){ if(l>P||r<P||!x)return 0; return seg[x].tag+query(seg[x].lson,l,mid,P)+query(seg[x].rson,mid+1,r,P); } void ADD(int x,int L,int R,int val){while(x<=n)modify(rt[x],1,n,L,R,val),x+=x&-x;} int SUM(int x,int P){int ret=0;while(x)ret+=query(rt[x],1,n,P),x-=x&-x;return ret;} void ADD(int l,int r,int val){ADD(l,l,r,val),ADD(r+1,l,r,-val);} set<pair<int,int> >s; char str[300100],rts[10]; int main(){ scanf("%d%d",&n,&m),scanf("%s",str+1); for(int i=1,j=1;i<=n;i=j){ while(j<=n&&str[i]==str[j])j++; if(str[i]=='1')s.insert(make_pair(i,j-1)),ADD(i,j-1,m); } for(int i=1,a,b;i<=m;i++){ scanf("%s%d",rts,&a); if(rts[0]=='t'){ if(str[a]=='1'){ auto it=--s.upper_bound(make_pair(a,0x3f3f3f3f)); int L=it->first,R=it->second;s.erase(it); ADD(L,R,i-m); if(L!=a)ADD(L,a-1,m-i),s.insert(make_pair(L,a-1)); if(R!=a)ADD(a+1,R,m-i),s.insert(make_pair(a+1,R)); }else{ auto it=s.lower_bound(make_pair(a,0x3f3f3f3f)); int L=a,R=a; if(it!=s.end()&&it->first==a+1)ADD(it->first,it->second,i-m),R=it->second,it=s.erase(it); if(it!=s.begin()&&(--it)->second==a-1)ADD(it->first,it->second,i-m),L=it->first,s.erase(it); ADD(L,R,m-i),s.insert(make_pair(L,R)); } // for(auto i:s)printf("(%d %d)",i.first,i.second);puts(""); str[a]^=1; // printf("%s\n",str+1); }else{ scanf("%d",&b),b--; int ret=SUM(a,b); auto it=s.upper_bound(make_pair(a,0x3f3f3f3f)); if(it!=s.begin()){ --it; if(it->first<=a&&it->second>=b)ret+=i-m; } printf("%d\n",ret); } } return 0; } ``` # XXXIV.[[九省联考2018]IIIDX](https://www.luogu.com.cn/problem/P4364) 首先，一个非常naive的想法是，建出通关的树出来，然后dfs它，在访问到一个节点时，将现有最小的值赋给它，然后从大到小遍历每个子节点。 这个算法会被 $d$ 相同的情形叉掉，因为它可以构造出这样一组数据：若某个节点的子树为 $1$，且它的兄长（指与它有同一父亲，且权值小于它的最大节点）的子树不为 $1$，且它的值和兄长的值相同。这时，我们可以掏出兄长的一个儿子，将其与该节点交换，并发现树仍然合法，但是字典序变大了。 于是我们开始思考这个问题的本质。 我们发现，用任意一组点集覆盖任意一棵子树，都能保证产生一组解。于是我们萌生了一个念头，能不能从小到大确定每个数的值，且使得剩余的数存在一种合法解？显然这种方法是一定正确的。 我们发现，假如一个点 $x$ 的子树大小是 $sz_x$，且赋值为 $b_i$，则其子树中每个点的权值都 $\geq b_i$。这就意味着，对于 $x$ 的子树，我们需要恰好 $sz_x$ 个 $\geq b_i$ 的节点来填满这棵子树。并且，依照我们上面的发现，这是充要条件。 于是问题转换为找到最大的 $b_i$ 使得存在上述点集。 我们考虑用一棵线段树维护，线段树上每个下标 $u$ 存了 $\geq u$ 的尚未被动用的权值数。在确定一个点的权值为 $b_i$ 后，我们需要对于 $\leq b_i$ 的所有位置全都减去 $sz_i$，因为这其中每个位置都确定可用的权值减少了 $sz_i$。但是这并不意味着 $>b_i$ 的权值数就不会变化，因为谁又知道子树中到底选了哪些数呢？ 因此，在确定一个 $b_i$ 时，我们不能简单地找到最大的权值数 $\geq sz_i$ 的下标，而应找到对于所有 $v\leq u$，都有 $v$ 的权值数 $\geq sz_i$ 的最大 $u$。这是很显然的。 而这是线段树二分的常规操作。随便写写就行了。 需要注意的是，确定 $b_i$ 时的操作的本质是**预订**，这就意味着当操作真正进行到儿子时，需要把父亲预订的那些位置给退回，同时注意一个父亲只能被退回一次。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,fa[500100],sz[500100],a[500100],b[500100]; double k; vector<int>v; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{int tag,mn;}seg[2001000]; void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);} void ADD(int x,int y){seg[x].mn+=y,seg[x].tag+=y;} void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;} void modify(int x,int l,int r,int P,int val){ if(l>P)return; if(r<=P){ADD(x,val);return;} pushdown(x),modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val),pushup(x); } int innersearch(int x,int l,int r,int val){ if(l==r)return seg[x].mn>=val?l:l-1; pushdown(x); if(seg[lson].mn>=val)return innersearch(rson,mid+1,r,val); else return innersearch(lson,l,mid,val); } int outersearch(int x,int l,int r,int P,int val){ // printf("%d[%d,%d]:%d,%d\n",x,l,r,P,val); if(r<P)return -1; if(l>=P){ // printf("[%d,%d]:%d %d\n",l,r,val,seg[x].mn); if(seg[x].mn>=val)return -1; return innersearch(x,l,r,val); } pushdown(x); int tmp=outersearch(lson,l,mid,P,val); if(tmp!=-1)return tmp; return outersearch(rson,mid+1,r,P,val); } bool vis[500100]; void iterate(int x,int l,int r){ if(l==r)printf("%d ",seg[x].mn); else pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r); } int main(){ scanf("%d%lf",&n,&k); for(int i=n,x;i;i--)sz[fa[i]=i/k]+=++sz[i],scanf("%d",&a[i]),v.push_back(a[i]); sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin()); for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1,modify(1,1,m,a[i],1); // for(int i=1;i<=n;i++)printf("%d %d\n",i,fa[i]); // for(int i=1;i<=n;i++)printf("%d ",sz[i]);puts(""); // iterate(1,1,m);puts(""); vis[0]=true,b[0]=1; for(int i=1;i<=n;i++){ if(!vis[fa[i]])modify(1,1,m,b[fa[i]],sz[fa[i]]-1),vis[fa[i]]=true; // puts(""); // iterate(1,1,m);puts(""); b[i]=outersearch(1,1,m,b[fa[i]],sz[i]); if(b[i]==-1)b[i]=m; // printf("%d:%d\n",sz[i],b[i]); modify(1,1,m,b[i],-sz[i]); // iterate(1,1,m);puts(""); } for(int i=1;i<=n;i++)printf("%d ",v[b[i]-1]); return 0; } ``` # XXXV.[CF36E Two Paths](https://www.luogu.com.cn/problem/CF36E) 为什么这题会被归到数据结构博客里呢？因为我的代码使用了大剂量的 `STL`。 ~~我吹爆 `list` 有没有！再也不手写链表了（并不），但是在欧拉路问题上真的贼好用！~~ 首先，覆盖所有边恰一次，妥妥的欧拉路模型。 然后就先考虑如何判无解了。怎样无解呢？ 1. 有少于 $2$ 条边。（如果不是样例给了，大概很难注意到……） 2. 有超过 $2$ 个连通块。 3. 仅有一个连通块，且连通块中奇点数大于 $4$。 4. 有两个连通块，且其中某一个块中奇点数大于 $2$。 那么，是否所有条件都满足，就一定有解呢？ 是的。 假如从**欧拉路**的方向考虑，就会非常麻烦，因为你找出的欧拉路删去后可能使得这张图分成许多不连通的图。 因此，这里有一个很好的思路：在两个奇点间连边，这样就会转换为**欧拉回路**，然后在欧拉回路上断去新加的边就行了。 具体而言，对于两个连通块的情形，显然上述结论正确，因为每个连通块都必然符合条件。 然后，对于仅有一个连通块的情形，其中可能有 $0$ 个，$2$ 个或是 $4$ 个奇点。 $0$ 个奇点就搜出回路然后随便砍两刀断环成链即可。 $2$ 个奇点就在额外连的那条边处砍一刀，然后再随便砍一刀就行。 $4$ 个奇点这两刀必须砍在额外的两条边的位置。这形成的两条链必然非空，因为这两条新边必然无公共端点，即其在欧拉环上必然不相邻。 时间复杂度 $O(m)$。 致死量 `STL` 的代码： ```cpp #include<bits/stdc++.h> using namespace std; int m,n,X[10010],Y[10010],dsu[20010],lim,id[20010]; bool deg[20010],used[10010]; vector<int>v,u[20010],w[20010]; int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);} void merge(int x,int y){ x=find(x),y=find(y); if(x==y)return; dsu[y]=x; } #define lst list<int>::iterator list<int>ls; void dfs(lst pos,int x){ while(true){ while(!w[x].empty()&&used[w[x].back()])w[x].pop_back(); if(w[x].empty())return; int i=w[x].back(),y=X[i]^Y[i]^x;w[x].pop_back(),used[i]=true; dfs(ls.insert(pos,i),y); } } vector<int>s[3]; int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&X[i],&Y[i]),v.push_back(X[i]),v.push_back(Y[i]); if(m==1){puts("-1");return 0;} sort(v.begin(),v.end()),v.resize(n=unique(v.begin(),v.end())-v.begin()); for(int i=1;i<=n;i++)dsu[i]=i; for(int i=1;i<=m;i++)merge(X[i]=lower_bound(v.begin(),v.end(),X[i])-v.begin()+1,Y[i]=lower_bound(v.begin(),v.end(),Y[i])-v.begin()+1),deg[X[i]]^=1,deg[Y[i]]^=1; // for(int i=1;i<=m;i++)printf("%d %d\n",X[i],Y[i]); // for(int i=1;i<=n;i++)printf("(%d,%d)",find(i),deg[i]);puts(""); for(int i=1;i<=n;i++)if(dsu[i]==i)id[i]=++lim; for(int i=1;i<=n;i++)u[id[find(i)]].push_back(i); if(lim>=3){puts("-1");return 0;} for(int i=1;i<=m;i++)w[X[i]].push_back(i),w[Y[i]].push_back(i); if(lim==1){ vector<int>sp; for(auto i:u[1])if(deg[i])sp.push_back(i); if(sp.size()>4){puts("-1");return 0;} for(int i=0;i<sp.size();i+=2){ int eid=m+i/2+1; X[eid]=sp[i],Y[eid]=sp[i+1],w[sp[i]].push_back(eid),w[sp[i+1]].push_back(eid); } dfs(ls.begin(),u[1].back()); // printf("%d\n",sp.size()); if(sp.empty()){ s[1].push_back(ls.front()),ls.pop_front(); for(auto i:ls)s[2].push_back(i); } if(sp.size()==2){ while(ls.front()<=m)ls.push_back(ls.front()),ls.pop_front(); ls.pop_front(); s[1].push_back(ls.front()),ls.pop_front(); while(!ls.empty())s[2].push_back(ls.front()),ls.pop_front(); } if(sp.size()==4){ while(ls.front()<=m)ls.push_back(ls.front()),ls.pop_front(); ls.pop_front(); while(ls.front()<=m)s[1].push_back(ls.front()),ls.pop_front(); ls.pop_front(); while(!ls.empty())s[2].push_back(ls.front()),ls.pop_front(); } } if(lim==2){ for(int i=1;i<=2;i++){ ls.clear(); vector<int>sp; for(auto j:u[i])if(deg[j])sp.push_back(j); if(sp.size()>2){puts("-1");return 0;} if(!sp.empty())X[m+1]=sp[0],Y[m+1]=sp[1],w[sp[0]].push_back(m+1),w[sp[1]].push_back(m+1),used[m+1]=false; dfs(ls.begin(),u[i].back()); if(!sp.empty()){while(ls.front()<=m)ls.push_back(ls.front()),ls.pop_front();ls.pop_front();} while(!ls.empty())s[i].push_back(ls.front()),ls.pop_front(); } } for(int i=1;i<=2;i++){ printf("%d\n",s[i].size()); for(auto j:s[i])printf("%d ",j);puts(""); } return 0; } ``` # XXXVI.[[十二省联考2019]异或粽子](https://www.luogu.com.cn/problem/P5283) 好像对可持久化结构有了新的认识（ 首先，我们考虑，区间异或和，可以直接被转换为前缀异或和的异或和，即 $s_r\operatorname{xor}s_{l-1}$。于是我们考虑对于每个 $s_r$ 找到与其异或起来最大的 $s_{l-1}$。 显然，可以建一棵可持久化01trie，每个位置的trie上记录了 $s_{0\sim i-1}$，然后只需用经典套路找出对于 $s_r$ 最大的 $s_{l-1}$ 即可。 现在考虑回答询问。依照某种套路，我们可以用一个堆维护对于每个 $r$ 最大的 $s_{l-1}$，然后每次从堆中找到最大的 $r$，并且把这个 $r$ 对应的次大的 $l-1$ 找出来。 于是我们需要支持动态地从01trie上删数。 在普通01trie上这是很好做的；但是这里可持久化了，要是直接减少区间中数的个数可能会影响到之后的trie。 于是我们便想到，减少一个数时，额外再拷贝一条新链出来就行了。（只不过这样空间复杂度就是 $32(n+q)$ 的，但此题空间一个 `G`，可以随意挥霍） 于是便做完了，时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned int ui; typedef long long ll; int n,m,cnt,rt[500100]; struct Trie{ int ch[2],sz; }t[30001000]; const int LG=31; ll res; ui a[500100]; void ins(int &x,int y,ui z,int del,int dep){ x=++cnt,t[x]=t[y],t[x].sz+=del; if(dep==-1)return; ins(t[x].ch[(z>>dep)&1],t[y].ch[(z>>dep)&1],z,del,dep-1); } ui findmx(int x,ui z,int dep){ if(dep==-1)return 0; // printf("%d:(%d,%d):%u,%d\n",x,ch[x][0],ch[x][1],z,dep); if(t[t[x].ch[!((z>>dep)&1)]].sz)return findmx(t[x].ch[!((z>>dep)&1)],z,dep-1)+(1<<dep); return findmx(t[x].ch[(z>>dep)&1],z,dep-1); } void iterate(int x,int dep,ui val){ if(!x)return; if(dep==-1){printf("(%u:%d)",val,t[x].sz);return;} iterate(t[x].ch[0],dep-1,val),iterate(t[x].ch[1],dep-1,val+(1<<dep)); } priority_queue<pair<ui,int> >q; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%u",&a[i]),a[i]^=a[i-1],ins(rt[i],rt[i-1],a[i-1],1,LG),q.push(make_pair(findmx(rt[i],a[i],LG),i)); while(m--){ ui z=q.top().first;int i=q.top().second; q.pop();res+=z,ins(rt[i],rt[i],z^a[i],-1,LG); if(t[rt[i]].sz)q.push(make_pair(findmx(rt[i],a[i],LG),i)); } printf("%lld\n",res); return 0; } ``` # XXXVII.[[十二省联考2019]春节十二响](https://www.luogu.com.cn/problem/P5290) 考虑一个simple的情形：假如一个点有两条链作为儿子，应该怎么样才好？ 明显，同一条链上的点不能在一起，于是链上的一个点只能与另一条链上的点匹配。明显匹配应该从大往小配（两个大的配了，这样最终便少了一个较大的）。于是我们用两个堆记录两条链，每次匹配堆顶的两个元素即可。 现在考虑从叶子开始处理。对于一个只有叶子作为儿子的节点，显然可以依照上述方法将叶子合在一起；接着，考虑该点的最深的有不止一个儿子的祖先。显然，因为我们合并了叶子，所以该点的儿子一定是数条链（如果不是链的话，我们要么可以合并叶子形成链，要么可以找到更深的使得儿子是不止一条链的节点）。不妨从三条链的情形开始考虑。 显然，对于该点子树外的点来说，子树内的情形并无影响，反正要么是与该点匹配（但这与合并链无关），要么是与三条链中每条上至多一个点匹配，而如果三条链上的点已经互相有了配对关系也无影响，只需要与配对完后剩下的那个点配对即可。接着，考虑第三条链上的点，同理，其只能与前两条链上至多一个点匹配，也是预先匹配并无影响。这样，我们就可以先合并前两条链，再合并第三条链，最终得到一条大链。这样子，对于拥有众多链作为儿子的节点，一定可以全部并作一条大链，不断并下去，最终会得到唯一一条链，而这条链就是答案。 可以使用启发式合并堆来处理上述过程。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,a[200100],fa[200100],id[200100]; priority_queue<int>q[200100]; long long res; void merge(int&x,int y){ if(q[x].size()<q[y].size())swap(x,y); vector<int>v; while(!q[y].empty())v.push_back(max(q[x].top(),q[y].top())),q[x].pop(),q[y].pop(); while(!v.empty())q[x].push(v.back()),v.pop_back(); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),id[i]=i; for(int i=2;i<=n;i++)scanf("%d",&fa[i]); for(int i=n;i;i--)q[id[i]].push(a[i]),merge(id[fa[i]],id[i]); while(!q[id[1]].empty())res+=q[id[1]].top(),q[id[1]].pop(); printf("%lld\n",res); return 0; } ``` # XXXVIII.[[NOI2016] 网格](https://www.luogu.com.cn/problem/P1173) 首先，答案一定 $\leq2$，因为四个角的跳蚤被围住只需要两个蛐蛐，而如果蛐蛐占住了一个角又会产生新的角。 $-1$ 的情形比较容易，要么空隙少于 $2$ 个，要么仅剩的两个空隙在一起。两种情况下 $n\times m$ 都与 $c$ 同级别，因此可以暴力。 $0$ 的情形等价于存在不连通的部分。可以发现，蛐蛐形成的八连通块，找到块中所有节点周边八个跳蚤并跑跳蚤的四联通性。若发现八连通块周边的跳蚤属于两个及以上不同的连通块，则即为 $0$。 $1$ 的情形等价于存在割点。割点有两种可能，一是 $n,m$ 中至少有一个为 $1$，二是蛐蛐把跳蚤分出了割点。假如依旧只找周边 $8$ 个跳蚤跑割点的话，那周边一圈的节点可能会被当成割点，比如这个样例，其中 `#` 代表蛐蛐。 ``` ... ... ..# ... ... ``` 但是我们发现，只需要选取周边两圈的节点即可规避上述问题。但是，需要注意的是，割点只能统计周边一圈的节点，否则会被 ``` #.... ..... ..... ..... ....# ``` 这组样例干掉——正中央的那个节点是割点，但不是内圈割点，因此不能计入。 然后剩余的情景即为 $2$。 需要注意的是，本题数据范围很大，存图要么用 `unordered_map`，要么手写哈希表。这里试了试哈希表，还挺好写的。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int M=3001000; int T,n,m,c,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},X[100100],Y[100100]; const int P=4999999; const int HT=5000000; const int BS=1e9+7; struct HashTable{ int head[HT],val[HT],nxt[HT],rx[HT],ry[HT],cnt; int HASH(int x,int y){return (1ll*x*m+y)%P;} void clear(){memset(head,-1,sizeof(head));} void ins(int x,int y,int z){ int p=HASH(x,y); nxt[cnt]=head[p],val[cnt]=z,rx[cnt]=x,ry[cnt]=y,head[p]=cnt++; } int fnd(int x,int y){for(int i=head[HASH(x,y)];i!=-1;i=nxt[i])if(rx[i]==x&&ry[i]==y)return val[i];return -1;} }m1,m2; bool checkimp(){//the function for impossibility check. if(1ll*n*m-c<2)return true; if(1ll*n*m-c>2)return false; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){ if(m1.fnd(i,j)!=-1)continue; for(int k=0;k<4;k++){ int I=i+dx[k],J=j+dy[k]; if(!I||!J||I>n||J>m||m1.fnd(I,J)!=-1)continue; return true; } } return false; } int cnt,bcm,cid[100100],dsu[100100]; pair<int,int>p[M]; vector<int>v[M]; int blk[M]; void floodfill(int x){ blk[x]=bcm; for(auto y:v[x])if(!blk[y])floodfill(y); } int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);} void merge(int x,int y){x=find(x),y=find(y);if(x!=y)dsu[y]=x;} bool checkdisc(){//check if the graph is disconnected. for(int i=1;i<=cnt;i++)if(!blk[i])bcm++,floodfill(i); for(int i=1;i<=c;i++)dsu[i]=i,cid[i]=0; for(int i=1;i<=c;i++)for(int j=-1;j<=1;j++)for(int k=-1;k<=1;k++){ if(!j&&!k||X[i]+j<1||Y[i]+k<1||X[i]+j>n||Y[i]+k>m)continue; int tmp=m1.fnd(X[i]+j,Y[i]+k); if(tmp!=-1)merge(i,tmp); } for(int i=1;i<=c;i++)for(int j=0;j<4;j++){ int x=X[i]+dx[j],y=Y[i]+dy[j]; int id=m2.fnd(x,y);if(id==-1)continue; if(!cid[find(i)])cid[find(i)]=blk[id]; else if(cid[find(i)]!=blk[id])return true; } return false; } int dfn[M],low[M],tot,cut; bool fir[M]; void Tarjan(int x,bool rt){ dfn[x]=low[x]=++tot; int son=0; for(auto y:v[x]){ if(!dfn[y])son++,Tarjan(y,false),low[x]=min(low[x],low[y]),cut+=(!rt&&dfn[x]<=low[y]&&fir[x]); else low[x]=min(low[x],dfn[y]); } if(rt&&son>=2&&fir[x])cut++; } bool checkcut(){ if(n==1||m==1)return true; for(int i=1;i<=cnt;i++)if(!dfn[i])Tarjan(i,true); return cut>=1; } void read(int &x){ x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } int mian(){ read(n),read(m),read(c); m1.clear(),m2.clear(); for(int i=1;i<=cnt;i++)dfn[i]=low[i]=blk[i]=0,v[i].clear();cnt=tot=cut=bcm=0; for(int i=1,x,y;i<=c;i++)read(X[i]),read(Y[i]),m1.ins(X[i],Y[i],i); if(checkimp())return -1; for(int i=1;i<=c;i++)for(int j=-2;j<=2;j++)for(int k=-2;k<=2;k++){ int x=X[i]+j,y=Y[i]+k; if(x<1||y<1||x>n||y>m||m1.fnd(x,y)!=-1)continue; int tmp=m2.fnd(x,y); if(tmp!=-1){fir[tmp]|=(abs(j)<=1&&abs(k)<=1);continue;} m2.ins(x,y,++cnt),p[cnt]=make_pair(x,y); fir[cnt]=(abs(j)<=1&&abs(k)<=1); } for(int i=1;i<=cnt;i++)for(int j=0;j<4;j++){ int x=p[i].first+dx[j],y=p[i].second+dy[j]; int tmp=m2.fnd(x,y); if(tmp!=-1)v[i].push_back(tmp); } if(checkdisc())return 0; if(checkcut())return 1; return 2; } int main(){ // freopen("P1173_1.in","r",stdin); scanf("%d",&T); while(T--)printf("%d\n",mian()); return 0; } ``` # XXXIX.[[NOI2017] 蔬菜](https://www.luogu.com.cn/problem/P3826) 第一眼这个奇奇怪怪的限制，想到网络流。 为了处理这个“每天坏 $c_i$”个的限制，我想到的方法是，第一天的 $c_i$ 个仅能在第一天销售，就只往代表第一天的点连边；第二天的 $c_i$ 个可以在第一天和第二天销售，故往代表第一天和第二天的点连边；第三天就往前三天连边……然后发现这样边数是 $O(n^2)$ 的。 尝试消减边数。发现这里面连了很多重复的边，而且如果我们倒着建图，令源点在第 $\inf$ 天的位置，汇点在第 $0$ 天的位置，就能使得边数消减到 $O(n)$，因为这样子每天的蔬菜作用范围就是一条前缀。 然后我们来思考这张图的实际意义——从后往前推，每天突然出现 $c_i$ 单位的菜，并且这之后这些菜都能卖。 稍微思考一下这个方法，就会发现一个非常棒的地方：因为任意时刻，你手头的菜在接下来的时刻也都能卖，所以就不必担心这些菜会烂在手里之类的，直接贪心地挑最贵的菜卖即可。至于那个“第一份菜补贴”的东西，我们就把它想成，某种菜出现的第一天，其中有一颗菜是~~镀金的~~，价格高一点，但是一样可以在贪心里算。 但是这个东西的复杂度，算算是 $O(n^2m\log n)$ 的，必须优化。 ~~然后就不会了~~ 明显，这种优化的唯一可能是从后一天的答案递推到前一天。于是我们考虑先求出第 $\inf$ 天（实际上取第 $10^5$ 天即可）时的答案。我们对于每天都开一个 `vector`。对于每种菜，我们将其编号扔到它全部消失那天的 `vector` 中。接着，从后往前遍历，用一个堆维护，每当访问到一天时，就将该天 `vector` 中所有菜，按照补贴价格扔进堆。 接着，从堆弹出 $m$ 个最贵的菜卖掉。具体而言，如果最贵的是补贴菜，就卖一个补贴菜，然后将平时的价格扔进堆；如果最贵的是平价菜，则目前仓库里剩余的平价菜数量，显然可以通过记录当前已经卖了多少此种菜，与当前天数来推出。推出剩余平价菜数量后，卖出 $\min(\text{此种菜数量},\text{本日剩余卖菜名额})$ 个菜。如果发现这个菜现有的库存已经卖光了，就把它扔进一个备用数组存着，等今天的销售处理完毕后再把它扔回堆里（因为第二天还有新的菜会到货）。 于是我们现在推出了第 $\inf$ 日的答案，也就知道了最优的卖菜方法。我们尝试递推答案。当我们想从 $i+1$ 日逆推出 $i$ 日的答案时，首先先判断手头的菜数量是否不大于 $im$（即前 $i$ 日所能卖出的菜数），如果是显然就不用放弃某些菜了；否则，从现行的卖菜方法中不断扔出最便宜的菜（可以开一个小根堆维护），直到小根堆的 `size` 已经达到 $im$。 时间复杂度 $O(nm\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int LIM=1e5; int n,m,P,pro[100100],bon[100100],amt[100100],per[100100],sel[100100],tot; ll res[100100]; vector<int>v[100100],bin; priority_queue<pair<int,int> >q; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >p; int main(){ scanf("%d%d%d",&n,&m,&P); for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&pro[i],&bon[i],&amt[i],&per[i]); if(!per[i])v[LIM].push_back(i); else v[min((amt[i]-1)/per[i]+1,LIM)].push_back(i); } for(int i=LIM;i;i--){ // printf("%d:\n",i); for(auto j:v[i])q.push(make_pair(pro[j]+bon[j],j)); int lim=m; while(lim&&!q.empty()){ int x=q.top().second;q.pop(); // printf("%d,%d\n",x,lim); if(!sel[x]){lim--,sel[x]++,res[LIM]+=pro[x]+bon[x],q.push(make_pair(pro[x],x));continue;}//first sale int tmp=min(lim,amt[x]-per[x]*(i-1)-sel[x]); lim-=tmp,sel[x]+=tmp,res[LIM]+=1ll*tmp*pro[x],bin.push_back(x); } while(!bin.empty()){ if(sel[bin.back()]!=amt[bin.back()])q.push(make_pair(pro[bin.back()],bin.back())); bin.pop_back(); } tot+=m-lim; } for(int i=1;i<=n;i++){ if(!sel[i])continue; if(sel[i]==1)p.push(make_pair(pro[i]+bon[i],i)); else p.push(make_pair(pro[i],i)); } // puts("IN"); for(int i=LIM;i;i--){ // printf("%d:\n",i); res[i-1]=res[i]; if((i-1)*m>=tot)continue; int lim=tot-(i-1)*m;tot=(i-1)*m; while(lim&&!p.empty()){ int x=p.top().second;p.pop(); if(sel[x]==1){lim--,sel[x]--,res[i-1]-=pro[x]+bon[x];continue;} int tmp=min(lim,sel[x]-1); lim-=tmp,sel[x]-=tmp,res[i-1]-=1ll*tmp*pro[x]; if(sel[x]==1)p.push(make_pair(pro[x]+bon[x],x)); else if(sel[x])p.push(make_pair(pro[x],x)); } } for(int i=1,x;i<=P;i++)scanf("%d",&x),printf("%lld\n",res[x]); return 0; } ``` # XL.[[NOI2017] 整数](https://www.luogu.com.cn/problem/P3822) 首先可以想到一种用线段树维护每一位的方法：一个数 $a\times2^b$ 拆成 $\log a$ 个位置上 $+1$，执行单点 $+1$ 的时候如果出现进位就找到右方第一个非 $1$ 的位置，然后单点加，区间赋 $0$；执行减法的时候，就是找到右方第一个非 $0$ 的位置，单点减，然后区间赋 $1$。（总之就是手工高精度竖式计算之类的） 但是这样复杂度就是 $O(n\log^2n)$，对于 $10^6$ 不可能过。 然后，既然是高精度算法，那就可以压位，每 $30$ 位压一块，这样执行一次加减法都不会爆 `int`。加法时就找到右方第一个非满的位置，减法时就找到右方第一个非零的位置，都可以线段树上二分简单维护。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int LG=30; const int MD=1<<30; int n; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{ int nz,nf,tag;//none-zero position,none-full position SegTree(){nz=nf=tag=-1;} }seg[5001000]; #define LSON lson,l,mid #define RSON rson,mid+1,r #define X x,l,r void MOD(int x,int l,int r,int y){if(!y)seg[x].nf=l,seg[x].nz=-1;if(y==MD-1)seg[x].nz=l,seg[x].nf=-1;seg[x].tag=y;} void pushdown(int x,int l,int r){if(seg[x].tag!=-1)MOD(LSON,seg[x].tag),MOD(RSON,seg[x].tag),seg[x].tag=-1;} void pushup(int x){if(seg[lson].nf!=-1)seg[x].nf=seg[lson].nf;else seg[x].nf=seg[rson].nf;if(seg[lson].nz!=-1)seg[x].nz=seg[lson].nz;else seg[x].nz=seg[rson].nz;} void upd(int x,int l,int r){if(seg[x].tag)seg[x].nz=l;else seg[x].nz=-1;if(seg[x].tag!=MD-1)seg[x].nf=l;else seg[x].nf=-1;} bool ADD(int x,int l,int r,int P,int y){ if(l>P||r<P)return false; if(l==r){seg[x].tag+=y;bool ret=false;if(seg[x].tag>=MD)seg[x].tag-=MD,ret=true;upd(X);return ret;} pushdown(X);bool ret=ADD(LSON,P,y)||ADD(RSON,P,y);pushup(x);return ret; } bool SUB(int x,int l,int r,int P,int y){ if(l>P||r<P)return false; if(l==r){seg[x].tag-=y;bool ret=false;if(seg[x].tag<0)seg[x].tag+=MD,ret=true;upd(X);return ret;} pushdown(X);bool ret=SUB(LSON,P,y)||SUB(RSON,P,y);pushup(x);return ret; } bool ADD1(int x,int l,int r,int P){ if(r<=P)return false; if(l>P&&seg[x].nf==-1){MOD(X,0);return false;} if(l==r){seg[x].tag++,upd(X);return true;} pushdown(X);bool ret=ADD1(LSON,P)||ADD1(RSON,P);pushup(x);return ret; } bool SUB1(int x,int l,int r,int P){ if(r<=P)return false; if(l>P&&seg[x].nz==-1){MOD(X,MD-1);return false;} if(l==r){seg[x].tag--,upd(X);return true;} pushdown(X);bool ret=SUB1(LSON,P)||SUB1(RSON,P);pushup(x);return ret; } void build(int x,int l,int r){if(l==r)seg[x].tag=0,seg[x].nf=l;else build(LSON),build(RSON),pushup(x);} bool query(int x,int l,int r,int P,int k){if(l>P||r<P)return false;if(l==r)return (seg[x].tag>>k)&1;pushdown(X);return query(LSON,P,k)||query(RSON,P,k);} void ADD(int a,int p){if(ADD(1,0,n+10,p,a))ADD1(1,0,n+10,p);} void SUB(int a,int p){if(SUB(1,0,n+10,p,a))SUB1(1,0,n+10,p);} void modify(int a,int b){ if(!a)return; bool sub=false;if(a<0)a=-a,sub=true; int p=b/LG;b%=LG; ll A=((ll)a)<<b; // printf("%lld %d %d\n",A,p,b); if(!sub){ADD(A%MD,p);if(A>=MD)ADD(A/MD,p+1);} else{SUB(A%MD,p);if(A>=MD)SUB(A/MD,p+1);} } bool query(int p){return query(1,0,n+10,p/LG,p%LG);} int read(){ int x=0,fl=1;char c=getchar(); for(;c>'9'||c<'0';c=getchar())if(c=='-')fl=-fl; while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); return fl==1?x:-x; } void iterate(int x,int l,int r){if(l==r)printf("%d ",seg[x].tag);else pushdown(X),iterate(LSON),iterate(RSON);} int main(){ // freopen("integer3.in","r",stdin); n=read(),read(),read(),read(); build(1,0,n+10); // iterate(1,0,n+10),puts(""); for(int i=1,tp,a,b;i<=n;i++){ tp=read(),a=read(); if(tp==1)b=read(),modify(a,b); else printf("%d\n",query(a)); // iterate(1,0,n+10),puts(""); } return 0; } ``` # XLI.[[NOI2017] 蚯蚓排队](https://www.luogu.com.cn/problem/P3823) 算算数据范围，可以哈希，只需要将所有长度在 $50$ 以内的串扔进哈希表，然后询问时找到对应的串的出现次数即可。 这里的哈希表必须用双哈希，其中第一维开在数组范围内，然后第二维作为链表挂在后面，因此范围可以无限大。不过因为要在 `int` 内处理，因此我两个模数分别取了 `4999999` 和 `299999977`，底数是 `11` 和 `7`，这样就在 `int` 内了。 维护蚯蚓排队的过程可以手写链表。 比较悲催的一点是，为了卡空间，我写了链表中回收废弃节点的操作，但是却忘记用了，然后空间还开的是卡过后的大小，最后很是debug一会才找出来。 时间复杂度 $O\Big(n+mk^2+\sum |s|\Big)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,a[200100],pv1[60],pv2[60]; const int mod1=4999999,mod2=299999977,bs1=11,bs2=7,mod=998244353; struct HashTable{ int head[mod1],nxt[200100],val[200100],num[200100],cnt,bin[200100],tp; HashTable(){memset(head,-1,sizeof(head));} int newnode(){return tp?bin[tp--]:cnt++;} void ins(int x,int y,int d){ for(int *i=&head[x];*i!=-1;i=&nxt[*i]){ if(val[*i]!=y)continue; num[*i]+=d;if(!num[*i])bin[++tp]=*i,*i=nxt[*i];return; } int id=newnode(); nxt[id]=head[x],val[id]=y,num[id]=d,head[x]=id; } int ask(int x,int y){for(int i=head[x];i!=-1;i=nxt[i])if(val[i]==y)return num[i];return 0;} }ht[50]; struct List{ int las,nex; List(){las=nex=-1;} }l[200100]; int S,K; char s[10001000]; void merge(){ int x,y; scanf("%d%d",&x,&y); l[x].nex=y,l[y].las=x; for(int i=1;x!=-1&&i<50;x=l[x].las,i++){ int p=0,q=0; for(int j=x,k=0;j!=-1&&k<50;j=l[j].nex,k++){ p=(bs1*p+a[j])%mod1; q=(bs2*q+a[j])%mod2; if(k>=i)ht[k].ins(p,q,1); } } } void split(){ int t,x,y;scanf("%d",&t),x=t,y=l[x].nex; for(int i=1;x!=-1&&i<50;x=l[x].las,i++){ int p=0,q=0; for(int j=x,k=0;j!=-1&&k<50;j=l[j].nex,k++){ p=(bs1*p+a[j])%mod1; q=(bs2*q+a[j])%mod2; if(k>=i)ht[k].ins(p,q,-1); } } l[t].nex=l[y].las=-1; } int query(){ scanf("%s%d",s,&K),S=strlen(s); int p=0,q=0,res=1; for(int i=0;i<S;i++){ if(i>=K)(p+=mod1-pv1[K-1]*(s[i-K]-'0')%mod1)%=mod1,(q+=mod2-pv2[K-1]*(s[i-K]-'0')%mod2)%=mod2; // printf("%d %d\n",p,q); p=(p*bs1+(s[i]-'0'))%mod1,q=(q*bs2+(s[i]-'0'))%mod2; if(i>=K-1)res=1ll*res*ht[K-1].ask(p,q)%mod; if(!res)return 0; } return res; } int main(){ pv1[0]=pv2[0]=1;for(int i=1;i<50;i++)pv1[i]=pv1[i-1]*bs1%mod1,pv2[i]=pv2[i-1]*bs2%mod2; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),ht[0].ins(a[i],a[i],1); int qt=0; for(int i=1,tp;i<=m;i++){ scanf("%d",&tp); if(tp==1)merge(); if(tp==2)split(); if(tp==3)printf("%d\n",query()); } return 0; } ``` # XLII.[[NOI2019] 弹跳](https://www.luogu.com.cn/problem/P5471) 一眼看上去，单点向矩阵连边、最短路，这不是数据结构优化建图是什么？ 想了想二维线段树优化建图，发现可以。 于是就写了，内层线段树写的还是可以压缩空间的线段树合并。 然后MLE了。 $88$ 分代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,W,H,tot,rt[280100],id[70100],head[3001000],cnt,X[70100],Y[70100]; struct node{int to,next,val;}edge[10010000]; void ae(int u,int v,int w){edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;} vector<int>v[70100]; #define mid ((l+r)>>1) struct SegTree{int lson,rson;}seg[3001000]; void Innermodify(int &x,int fa,int l,int r,int P,int val){ if(l>P||r<P)return; if(!x){x=++tot;if(fa)ae(fa,x,0);} if(l==r)id[val]=x;else Innermodify(seg[x].lson,x,l,mid,P,val),Innermodify(seg[x].rson,x,mid+1,r,P,val); } int Innermerge(int x,int y,int l,int r){ if(!x||!y)return x+y; int z=++tot; if(l!=r){ seg[z].lson=Innermerge(seg[x].lson,seg[y].lson,l,mid),seg[z].rson=Innermerge(seg[x].rson,seg[y].rson,mid+1,r); if(seg[z].lson)ae(z,seg[z].lson,0);if(seg[z].rson)ae(z,seg[z].rson,0); }else ae(z,x,0),ae(z,y,0); return z; } void Innerae(int x,int l,int r,int L,int R,int S,int T){ if(l>R||r<L||!x)return; if(L<=l&&r<=R)ae(S,x,T);else Innerae(seg[x].lson,l,mid,L,R,S,T),Innerae(seg[x].rson,mid+1,r,L,R,S,T); } #define ls x<<1 #define rs x<<1|1 void Outerbuild(int x,int l,int r){ if(l==r)for(auto i:v[l])Innermodify(rt[x],0,1,H,Y[i],i);else Outerbuild(ls,l,mid),Outerbuild(rs,mid+1,r),rt[x]=Innermerge(rt[ls],rt[rs],1,H); } void Outerae(int x,int l,int r,int OL,int OR,int IL,int IR,int S,int T){ if(l>OR||r<OL)return; if(OL<=l&&r<=OR)Innerae(rt[x],1,H,IL,IR,S,T);else Outerae(ls,l,mid,OL,OR,IL,IR,S,T),Outerae(rs,mid+1,r,OL,OR,IL,IR,S,T); } int dis[3001000]; bool vis[3001000]; priority_queue<pair<int,int> >q; void Dijkstra(int S){ memset(dis,0x3f,sizeof(dis)),dis[S]=0,q.push(make_pair(-dis[S],S)); while(!q.empty()){ int x=q.top().second;q.pop(); if(vis[x])continue;vis[x]=true; for(int i=head[x],y;i!=-1;i=edge[i].next)if(dis[y=edge[i].to]>dis[x]+edge[i].val)dis[y]=dis[x]+edge[i].val,q.push(make_pair(-dis[y],y)); } } int main(){ // freopen("I.in","r",stdin); scanf("%d%d%d%d",&n,&m,&W,&H),memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++)scanf("%d%d",&X[i],&Y[i]),v[X[i]].push_back(i); Outerbuild(1,1,W); // printf("%d\n",tot); for(int i=1,S,T,OL,OR,IL,IR;i<=m;i++)scanf("%d%d%d%d%d%d",&S,&T,&OL,&OR,&IL,&IR),Outerae(1,1,W,OL,OR,IL,IR,tot+S,T); for(int i=1;i<=n;i++)ae(id[i],tot+i,0); Dijkstra(tot+1); for(int i=2;i<=n;i++)printf("%d\n",dis[tot+i]); return 0; } ``` 想不到怎么优化。题解上说，内层可以用 `set` 替代线段树，这样空间复杂度会压到 $O(n\log n)$。并且，边也不用真的建出来——一个点向矩阵中所有点连边，就等 `Dijkstra` 遍历到该点时，将该点的所有**矩阵**也扔进大根堆里，若堆顶是点就执行上述操作，若堆顶是矩阵就更新矩阵内点。于是便照着题解思路写了，仍然MLE。 $88$ 分代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,W,H; #define mid ((l+r)>>1) #define lson x<<1 #define rson x<<1|1 set<pair<int,int> >s[280010]; struct Matrix{ int id,l,r,d; Matrix(int I,int L,int R,int D){id=I,l=L,r=R,d=D;} friend bool operator<(const Matrix&u,const Matrix&v){return u.d>v.d;} };//record a node linked to a matrix vector<Matrix>v[70100]; void modify(int x,int l,int r,int X,int Y,int id){ if(l>X||r<X)return; s[x].insert(make_pair(Y,id)); if(l!=r)modify(lson,l,mid,X,Y,id),modify(rson,mid+1,r,X,Y,id); } void query(int x,int l,int r,int OL,int OR,int IL,int IR,int S,int T){ if(l>OR||r<OL)return; if(OL<=l&&r<=OR)v[S].emplace_back(x,IL,IR,T); else query(lson,l,mid,OL,OR,IL,IR,S,T),query(rson,mid+1,r,OL,OR,IL,IR,S,T); } int dis[70100]; bool vis[70100]; priority_queue<Matrix>q; void Dijkstra(){ memset(dis,0x3f,sizeof(dis)),dis[1]=0,q.emplace(-1,-1,-1,0); while(!q.empty()){ Matrix x=q.top();q.pop(); if(x.id>0){ auto i=s[x.id].lower_bound(make_pair(x.l,0)),j=s[x.id].upper_bound(make_pair(x.r,0x3f3f3f3f)); for(auto k=i;k!=j;k=s[x.id].erase(k))if(dis[k->second]>x.d)dis[k->second]=x.d,q.push(Matrix(-k->second,-1,-1,dis[k->second])); continue; } int X=-x.id; if(vis[X])continue;vis[X]=true; for(auto i:v[X])q.push(Matrix(i.id,i.l,i.r,i.d+dis[X])); } } int main(){ scanf("%d%d%d%d",&n,&m,&W,&H); for(int i=1,x,y;i<=n;i++)scanf("%d%d",&x,&y),modify(1,1,W,x,y,i); for(int i=1,S,T,OL,OR,IL,IR;i<=m;i++)scanf("%d%d%d%d%d%d",&S,&T,&OL,&OR,&IL,&IR),query(1,1,W,OL,OR,IL,IR,S,T); Dijkstra(); for(int i=2;i<=n;i++)printf("%d\n",dis[i]); return 0; } ``` 后来没办法，看了题解代码。原来，题解并没有像我一样预先将矩阵在线段树上拆分，而是等处理到一个矩阵时再把它扔进线段树上处理。同时，题解中大根堆里只存储了未拆分的矩阵，这部分空间复杂度就是 $O(m)$ 而非我上面的 $O(m\log n)$ 了（可能就是这边让我上面的代码挂掉了）。存储未拆分的矩阵；更新矩阵内部点时，直接将点上矩阵扔进堆中；更新完矩阵内部点就直接在整棵树上删掉这些点……就是这种精打细算的压缩空间，才没有被卡掉。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,W,H,X[70100],Y[70100]; #define mid ((l+r)>>1) #define lson x<<1 #define rson x<<1|1 set<pair<int,int> >s[280010]; struct Matrix{ int l,r,L,R,d; Matrix(int a,int b,int C,int D,int e){l=a,r=b,L=C,R=D,d=e;} friend bool operator<(const Matrix&u,const Matrix&v){return u.d>v.d;} }; vector<Matrix>v[70100]; void modify(int x,int l,int r,int id){ if(l>X[id]||r<X[id])return; s[x].insert(make_pair(Y[id],id)); if(l!=r)modify(lson,l,mid,id),modify(rson,mid+1,r,id); } void yfidom(int x,int l,int r,int id){ if(l>X[id]||r<X[id])return; s[x].erase(make_pair(Y[id],id)); if(l!=r)yfidom(lson,l,mid,id),yfidom(rson,mid+1,r,id); } int dis[70100]; bool vis[70100]; priority_queue<Matrix>q; void solve(int x,int l,int r,Matrix M){ if(l>M.r||r<M.l)return; if(M.l<=l&&r<=M.r){ auto i=s[x].lower_bound(make_pair(M.L,0)),j=s[x].upper_bound(make_pair(M.R,0x3f3f3f3f)); vector<int>tmp; for(auto k=i;k!=j;k++){ dis[k->second]=M.d,tmp.push_back(k->second); for(auto o:v[k->second])o.d+=M.d,q.push(o); } for(auto o:tmp)yfidom(1,1,W,o); }else solve(lson,l,mid,M),solve(rson,mid+1,r,M); } void Dijkstra(){ for(auto i:v[1])q.push(i); yfidom(1,1,W,1); while(!q.empty()){ auto M=q.top();q.pop(); solve(1,1,W,M); } } int main(){ scanf("%d%d%d%d",&n,&m,&W,&H); for(int i=1,x,y;i<=n;i++)scanf("%d%d",&X[i],&Y[i]),modify(1,1,W,i); for(int i=1,S,T,OL,OR,IL,IR;i<=m;i++)scanf("%d%d%d%d%d%d",&S,&T,&OL,&OR,&IL,&IR),v[S].emplace_back(OL,OR,IL,IR,T); Dijkstra(); for(int i=2;i<=n;i++)printf("%d\n",dis[i]); return 0; } ``` # XLIII.[URAL1097. Square Country 2](https://acm.timus.ru/problem.aspx?space=1&num=1097) 考虑二分，二分后转成判定性问题，然后用扫描线+线段树处理即可。时间复杂度 $O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,q; struct Land{ int x,yl,yr,imp; Land(){} Land(int X,int YL,int YR,int I){x=X,yl=YL,yr=YR,imp=I;} friend bool operator<(const Land&u,const Land&v){return u.x<v.x;} }p[210]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{int tag,mn;}seg[40100]; void ADD(int x,int y){seg[x].tag+=y,seg[x].mn+=y;} void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;} void pushup(int x){seg[x].mn=min(seg[lson].mn,seg[rson].mn);} void modify(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(L<=l&&r<=R)ADD(x,val); else pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x); } bool che(int ip){ memset(seg,0,sizeof(seg)); for(int i=1,j=1;i<=n-m+1;i++){ for(;j<=2*q&&p[j].x<=i;j++){ if(abs(p[j].imp)<=ip)continue; if(p[j].imp>0)modify(1,1,n-m+1,p[j].yl,p[j].yr,1);else modify(1,1,n-m+1,p[j].yl,p[j].yr,-1); } if(seg[1].mn==0)return true; } return false; } int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1,I,L,X,Y;i<=q;i++){ scanf("%d%d%d%d",&I,&L,&X,&Y); p[i]=Land(max(1,X-m+1),max(1,Y-m+1),min(Y+L-1,n-m+1),I); p[q+i]=Land(X+L,max(1,Y-m+1),min(Y+L-1,n-m+1),-I); } sort(p+1,p+2*q+1); // for(int i=1;i<=2*q;i++)printf("%d[%d,%d]:%d\n",p[i].x,p[i].yl,p[i].yr,p[i].imp); int l=1,r=100; while(l<r){ int md=(l+r)>>1; if(che(md))r=md; else l=md+1; } if(!che(l))puts("IMPOSSIBLE");else printf("%d\n",l); return 0; } ``` # XLIV.[CF607D Power Tree](https://www.luogu.com.cn/problem/CF607D) 考虑计算 $x$ 子树中某个节点 $y$ 对于 $f(x)$ 的贡献，发现是 $w_y\times\prod\limits_{z\in\text{path}(y,x)}deg_z$，其中 $deg_z$ 是 $z$ 节点的儿子数。 于是考虑离线，然后建一棵下标为dfs序的线段树，每个节点上记录了区间所有节点对 $1$ 的贡献。询问 $f(x)$ 时，就直接查询区间和；但是因为从 $x$ 到根路径上所有的 $deg$ 都被多算了，因此要除掉。修改时，其父亲的 $deg$ 改变了，就导致父亲子树中所有节点对根的贡献也改变了，但是改变的都是 $\dfrac{deg_x+1}{deg_x}$，于是直接区间打一个乘法标记即可。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int ksm(int x,int y=mod-2){int z=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;return z;} int n,a[200100],q,sz[200100],dfn[200100],rev[200100],tot,fa[200100],deg[200100]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{int sum,tag;SegTree(){sum=0,tag=1;}}seg[800100]; void MUL(int x,int y){seg[x].sum=1ll*seg[x].sum*y%mod,seg[x].tag=1ll*seg[x].tag*y%mod;} void pushdown(int x){MUL(lson,seg[x].tag),MUL(rson,seg[x].tag),seg[x].tag=1;} void pushup(int x){seg[x].sum=(seg[lson].sum+seg[rson].sum)%mod;} void multiply(int x,int l,int r,int L,int R,int val){ if(l>R||r<L)return; if(L<=l&&r<=R){MUL(x,val);return;} pushdown(x),multiply(lson,l,mid,L,R,val),multiply(rson,mid+1,r,L,R,val),pushup(x); } void turnon(int x,int l,int r,int P){ if(l>P||r<P)return; if(l==r){seg[x].sum=1ll*a[rev[P]]*seg[x].tag%mod;return;} pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P),pushup(x); } int querytag(int x,int l,int r,int P){ if(l>P||r<P)return 0; if(l==r)return seg[x].tag; pushdown(x);return querytag(lson,l,mid,P)+querytag(rson,mid+1,r,P); } int querysum(int x,int l,int r,int L,int R){ if(l>R||r<L)return 0; if(L<=l&&r<=R)return seg[x].sum; pushdown(x);return (querysum(lson,l,mid,L,R)+querysum(rson,mid+1,r,L,R))%mod; } vector<int>v[200100]; int tp[200100],pos[200100]; void dfs(int x){ dfn[x]=++tot,rev[tot]=x,sz[x]=1; for(auto y:v[x])fa[y]=x,dfs(y),sz[x]+=sz[y]; } int main(){ scanf("%d%d",&a[n=1],&q); for(int i=1;i<=q;i++){ scanf("%d%d",&tp[i],&pos[i]); if(tp[i]==1)scanf("%d",&a[++n]),v[pos[i]].push_back(n),pos[i]=n; } for(int i=1;i<=n;i++)deg[i]=1; dfs(1),turnon(1,1,n,1); for(int i=1,x;i<=q;i++){ if(tp[i]==1){ x=fa[pos[i]]; multiply(1,1,n,dfn[x],dfn[x]+sz[x]-1,1ll*(deg[x]+1)*ksm(deg[x])%mod),deg[x]++; turnon(1,1,n,dfn[pos[i]]); }else x=pos[i],printf("%d\n",1ll*querysum(1,1,n,dfn[x],dfn[x]+sz[x]-1)*(x==1?1:ksm(querytag(1,1,n,dfn[fa[x]])))%mod); } return 0; } ``` # XLV.[[HNOI2009] 梦幻布丁](https://www.luogu.com.cn/problem/P3201) 线段树合并是非常显然的，但是这里我们偏不用。这里我们使用的是**启发式合并**——虽然这仍然非常显然。 可以使用链表做到 $O(n\log n)$ 但是我~~太懒了~~因此直接暴力用 `set` 做了，是 $O(n\log^2n)$ 的不过一样也能过。 附：`set` 直接 `swap` 是 $O(1)$ 的哦！ 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int N=1000000; int n,m,res; set<pair<int,int> >s[1001000]; int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++){ scanf("%d",&x); int l=i,r=i; if(!s[x].empty()&&s[x].rbegin()->second==i-1)l=s[x].rbegin()->first,s[x].erase(--s[x].end()); s[x].emplace(l,r); } for(int i=1;i<=N;i++)res+=s[i].size(); for(int i=1,tp,x,y;i<=m;i++){ scanf("%d",&tp); if(tp==1){ scanf("%d%d",&x,&y); if(x==y||s[x].empty())continue; if(s[y].empty()){swap(s[x],s[y]);continue;} bool swt=true; if(s[x].size()<s[y].size())swt=false,swap(x,y); res-=s[x].size(),res-=s[y].size(); for(auto i:s[y]){ int l=i.first,r=i.second; auto it=s[x].lower_bound(i); if(it!=s[x].end()&&it->first==r+1)r=it->second,it=s[x].erase(it); if(it!=s[x].begin()&&(--it)->second==l-1)l=it->first,s[x].erase(it); s[x].emplace(l,r); } res+=s[x].size(),s[y].clear(); if(swt)swap(s[x],s[y]); }else printf("%d\n",res); } return 0; } ``` # XLVI.[CF1408G Clusterization Counting](https://www.luogu.com.cn/problem/CF1408G) 很明显，将边按照权值从小到大排序后，依次用冰茶姬合并，如果任意时刻出现了团，则这个团显然是唯一合法的可能。人脑思考可得这个团之间的关系肯定是个划分树关系（即一个大团裂成许多小团的树形关系），因此总合法团数是 $O(n)$ 级别的，可以暴力建出树然后在上面背包即可。 建树的过程只需要在冰茶姬中维护当前连通块是由哪些小团拼成的即可。当发现连通块成为大团了，就从大团向小团连边，并清空小团集合，扔入大团即可。 这要求我们在合并两个冰茶姬时同时合并它们的小团集合。使用 `vector` 合并大概也没问题，但是直接用 `list` 的 `splice` 操作 $O(1)$ 合并它不香吗？ 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int mod=998244353; int n,m,dsu[1510],vsz[1510],esz[1510],cnt,f[3010][1510],lim[1510]; struct edge{ int x,y,z; friend bool operator<(const edge&u,const edge&v){return u.z<v.z;} }e[2000000]; int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);} list<int>v[1510],u[3010]; void ae(int x,int y){ x=find(x),y=find(y); if(x==y){ esz[x]++; if(esz[x]==vsz[x]*(vsz[x]-1)/2)u[++cnt].swap(v[x]),v[x].push_back(cnt); return; } if(vsz[x]<vsz[y])swap(x,y); dsu[y]=x,vsz[x]+=vsz[y],esz[x]+=esz[y]+1,v[x].splice(v[x].begin(),v[y]); if(esz[x]==vsz[x]*(vsz[x]-1)/2)u[++cnt].swap(v[x]),v[x].push_back(cnt); } void dfs(int x){ if(x<=n){f[x][lim[x]=1]=1;return;} f[x][0]=1; for(auto y:u[x]){ dfs(y); // for(int i=0;i<=lim[x];i++)printf("%d ",f[x][i]);puts(""); // for(int i=0;i<=lim[y];i++)printf("%d ",f[y][i]);puts(""); for(int i=lim[x];i>=0;f[x][i--]=0)for(int j=lim[y];j>=0;j--)(f[x][i+j]+=1ll*f[x][i]*f[y][j]%mod)%=mod; lim[x]+=lim[y]; } f[x][0]=0,(++f[x][1])%=mod; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)for(int j=1,x;j<=n;j++){ scanf("%d",&x); if(i<j)m++,e[m].x=i,e[m].y=j,e[m].z=x; } sort(e+1,e+m+1); for(int i=1;i<=n;i++)dsu[i]=i,vsz[i]=1,v[i].push_back(i); cnt=n; // for(int i=1;i<=m;i++)printf("(%d,%d:%d)",e[i].x,e[i].y,e[i].z); for(int i=1;i<=m;i++)ae(e[i].x,e[i].y); // for(int i=1;i<=n;i++)printf("%d %d %d\n",dsu[i],vsz[i],esz[i]); dfs(cnt); for(int i=1;i<=n;i++)printf("%d ",f[cnt][i]); return 0; } ``` # XLVII.[CF1500E Subset Trick](https://www.luogu.com.cn/problem/CF1500E) 考虑对于每个集合大小 $i$，找到所有大小为 $i$ 的集合中元素和最小的一个 $l_i$ 与最大的一个 $r_i$。则，所有 $x\in[l_i,r_i)$ 均不合法。 于是我们就要求 $\Big|\bigcup\limits_{i=0}^{n}[l_i,r_i)\Big|$。 直接求不容易；但是我们可以正难则反，考虑找出那些不被包含在其中的 $x$。虽然这一 $x$ 的数量是无限的，但是发现若设所有数之和为 $s$，则所有 $x\in[s,\infty)$ 显然均不被包含，可以不考虑。于是我们仅需考虑那些 $\in[0,s)$ 且不被包含的数即可。 显然的是，$l_i$ 必然是前 $i$ 小的数之和，$r_i$ 必然是前 $i$ 大的数之和。 假如我们在平面直角坐标系中画出所有 $(i,l_i)$ 与 $(i,r_i)$ 的话，就会发现所有 $l$ 连成的折线是凹的，所有 $r$ 连成的这些是凸的，且这两条折线是中心对称的。 于是我们仅需考虑前一半中 $x$ 的数量，然后乘二就得到了全体 $x$ 的数量（当然，若 $x$ 是奇数，还要额外考虑中间的那个位置，但是随便特判一下就出来了）。 现在考虑每个不被包含在其中的 $x$ 的区间，发现其都是形如 $[r_{i-1},l_i)$ 的形式。 一个非常棒的观察是，因为 $l$ 凹 $r$ 凸且二者对称，所以在前一半中 $r$ 的增量总是不小于 $l$ 的增量，这也意味着上述区间若非空则所有这样的 $i$ 是一段前缀。于是我们可以用什么数据结构维护一下 $l$ 与 $r$，然后套个二分就能找到最大的这样的 $i$。 现在考虑用什么数据结构。平衡树显然是可行的，但是据说被卡常了。于是离散化后上线段树维护即可。 时间复杂度 $O(n\log^2n)$。那个二分不能放到线段树上实现，因为要维护的是两棵不同的线段树。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,lim,sz; ll a[200100],b[200100],sum; vector<ll>v; struct ST{ #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{int sz;ll sum,tag;}seg[1600100]; void ADD(int x,ll y){seg[x].tag+=y,seg[x].sum+=seg[x].sz*y;} void pushdown(int x){ADD(lson,seg[x].tag),ADD(rson,seg[x].tag),seg[x].tag=0;} void pushup(int x){seg[x].sum=seg[lson].sum+seg[rson].sum,seg[x].sz=seg[lson].sz+seg[rson].sz;}; void turnon(int x,int l,int r,int P){if(l>P||r<P)return;if(l==r)seg[x].sum=seg[x].tag,seg[x].sz=1;else pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P),pushup(x);} void turnoff(int x,int l,int r,int P){if(l>P||r<P)return;if(l==r)seg[x].sum=0,seg[x].sz=0;else pushdown(x),turnoff(lson,l,mid,P),turnoff(rson,mid+1,r,P),pushup(x);} void modify(int x,int l,int r,int L,int R,ll val){if(l>R||r<L)return;if(L<=l&&r<=R)ADD(x,val);else pushdown(x),modify(lson,l,mid,L,R,val),modify(rson,mid+1,r,L,R,val),pushup(x);} ll kth(int x,int l,int r,int k){if(l==r)return seg[x].sum;pushdown(x);if(seg[lson].sz>=k)return kth(lson,l,mid,k);else return kth(rson,mid+1,r,k-seg[lson].sz);} ll query(int x,int l,int r,int k){if(l==r)return seg[x].sum;pushdown(x);if(seg[lson].sz>=k)return query(lson,l,mid,k);return seg[lson].sum+query(rson,mid+1,r,k-seg[lson].sz);} void iterate(int x,int l,int r){printf("%d[%d,%d]:%d,%d\n",x,l,r,seg[x].sum,seg[x].sz);if(l!=r)pushdown(x),iterate(lson,l,mid),iterate(rson,mid+1,r);} }s1,s2;//s1 is minimum,s2 is maximum void turnon(int P){s1.turnon(1,1,lim,P),s1.modify(1,1,lim,P,lim,v[P-1]);s2.turnon(1,1,lim,lim-P+1),s2.modify(1,1,lim,lim-P+1,lim,v[P-1]);sz++,sum+=v[P-1];} void turnoff(int P){s1.turnoff(1,1,lim,P),s1.modify(1,1,lim,P,lim,-v[P-1]);s2.turnoff(1,1,lim,lim-P+1),s2.modify(1,1,lim,lim-P+1,lim,-v[P-1]);sz--,sum-=v[P-1];} ll query(){ if(sz<=1)return 0; int l=1,r=sz>>1; while(l<r){ int md=(l+r+1)>>1; if(s1.kth(1,1,lim,md)>=s2.kth(1,1,lim,md-1))l=md; else r=md-1; } ll ret=s1.query(1,1,lim,l);if(l>1)ret-=s2.query(1,1,lim,l-1); ret<<=1; if(sz&1)ret+=max(0ll,s1.kth(1,1,lim,(sz+1)>>1)-s2.kth(1,1,lim,sz>>1)); // printf("(%d,%d)\n",sum,sz); return sum-ret; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]),v.push_back(a[i]); for(int i=1,x;i<=m;i++)scanf("%d%lld",&x,&b[i]),v.push_back(b[i]),b[i]=(x==1?b[i]:-b[i]); sort(v.begin(),v.end()),v.resize(lim=unique(v.begin(),v.end())-v.begin()); for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; for(int i=1;i<=m;i++){ if(b[i]>0)b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1; else b[i]=-(lower_bound(v.begin(),v.end(),-b[i])-v.begin()+1); } for(int i=1;i<=n;i++)turnon(a[i]); printf("%lld\n",query()); for(int i=1;i<=m;i++){ if(b[i]>0)turnon(b[i]); else turnoff(-b[i]); // s1.iterate(1,1,lim),puts(""); // s2.iterate(1,1,lim),puts(""); printf("%lld\n",query()); } return 0; } ``` # XLVIII.[[SCOI2014]方伯伯的OJ](https://www.luogu.com.cn/problem/P3285) 为啥对于排名的改动仅有移到第一位与移到最后一位两种呢？这启发我们对于排名建一个数据结构，下标初始为 $(m+1)\sim(m+n)$，并令左右两个指针分别指向 $m$ 与 $m+n+1$。若把一个人调到第一位，就找到其现在的下标，删除数据结构中该下标，并在左指针处插回该数，之后左指针自减。显然，该操作的确将这个元素移到了第一位。移到最后一位的操作类似。 于是我们需要建立元素编号与数据结构中下标间的双射（因为在数据结构上二分出第 $k$ 大时，找到的仅是第 $k$ 大的下标，还要复原出元素的编号）。因为所有操作都仅会影响到 $O(1)$ 的元素，所有直接开两个 `map` 即可建立双射。 现在考虑使用什么数据结构。显然一个动态开点线段树即可。 线段树上每个节点只需维护子树大小即可。这里介绍一个非常清新的小技巧：因为初始时 $(m+1)\sim(m+n)$ 的下标默认是有数的，所以当计算一个点子树大小时，若该点存在，显然子树大小已经维护了；否则，设该点代表的区间是 $[l,r]$，显然其子树大小应为 $\Big|[l,r]\cap[m+1,m+n]\Big|$，就不用什么奇奇怪怪的 `tag` 来维护了。 时间复杂度 $O(m\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; map<int,int>s2i,i2s; int cnt,rt,n,m,Lid,Rid; #define mid ((l+r)>>1) #define X x,l,r #define LSON seg[x].lson,l,mid #define RSON seg[x].rson,mid+1,r struct SegTree{int lson,rson,sz;}seg[6001000]; int SZ(int x,int l,int r){if(x)return seg[x].sz;l=max(l,m+1),r=min(r,m+n);return max(r-l+1,0);} void pushup(int x,int l,int r){seg[x].sz=SZ(LSON)+SZ(RSON);} void setval(int&x,int l,int r,int P,int val){if(l>P||r<P)return;if(!x)x=++cnt;if(l==r){seg[x].sz=val;return;}setval(LSON,P,val),setval(RSON,P,val),pushup(X);} int queryrnk(int x,int l,int r,int P){if(l>P)return 0;if(r<=P)return SZ(X);return queryrnk(LSON,P)+queryrnk(RSON,P);} int querykth(int x,int l,int r,int k){if(l==r)return l;if(SZ(LSON)>=k)return querykth(LSON,k);else return querykth(RSON,k-SZ(LSON));} int main(){ scanf("%d%d",&n,&m),Lid=m,Rid=m+n+1; for(int i=1,las=0,tp,x,y;i<=m;i++){ scanf("%d%d",&tp,&x),x-=las; if(tp==1){ scanf("%d",&y),y-=las; if(i2s.find(x)==i2s.end())i2s[x]=m+x; s2i[i2s[y]=i2s[x]]=y; las=queryrnk(rt,1,m+n+m,i2s[y]); } if(tp==2){ if(i2s.find(x)==i2s.end())i2s[x]=m+x; las=queryrnk(rt,1,m+n+m,i2s[x]); setval(rt,1,m+n+m,i2s[x],0); setval(rt,1,m+n+m,Lid,1); s2i[i2s[x]=Lid]=x; Lid--; } if(tp==3){ if(i2s.find(x)==i2s.end())i2s[x]=m+x; las=queryrnk(rt,1,m+n+m,i2s[x]); setval(rt,1,m+n+m,i2s[x],0); setval(rt,1,m+n+m,Rid,1); s2i[i2s[x]=Rid]=x; Rid++; } if(tp==4){ las=querykth(1,1,m+n+m,x); if(s2i.find(las)!=s2i.end())las=s2i[las];else las-=m; } printf("%d\n",las); } return 0; } ``` # IL.[[Ynoi2017] 由乃的 OJ](https://www.luogu.com.cn/problem/P5354) 首先考虑按位处理。 考虑分 $6$ 种情况讨论： 1. 操作是 $\text{AND}$，这位上是 $0$。 则显然是直接将这位强行赋 $0$。 2. $\text{AND}$，$1$。 对这位没有影响。 3. $\text{OR}$，$0$。 没有影响。 4. $\text{OR}$，$1$。 强行赋 $1$。 5. $\text{XOR}$，$0$。 没有影响。 6. $\text{XOR}$，$1$。 翻转。 于是我们可以设一个二元组 $p=(mus,sur)$ 来表示某一位的值的状态：$sur$ 为 $1$，表示这位已经被强行赋值，值为 $mus$；$sur$ 为 $0$，则表示未被强行赋值——显然只有情形6会影响这种可能，于是此时的 $mus$ 表示经过的情形6的数量。 现在，考虑合并 $p=(mus,sur)$ 与 $p'=(mus',sur')$。显然，当 $sur'=1$ 时，无论 $p$ 中经历了什么，都会被 $p'$ 给强行覆盖掉，因此有 $p+p'=p'$。而，当 $sur'=0$ 时，则有 $p+p'=(mus\operatorname{xor}mus',sur)$。 树上单点修改、链查询，考虑上树剖维护。因为是在按位处理，所以要开 $\log n$ 棵线段树，总计复杂度 $O(n\log^3n)$，对于 $n=10^5$ 不大可能过。 只能考虑把所有位合在一起做。考虑将 $p=(mus,sur)$ 从一位升级为 $64$ 位。 首先，新的 $sur$ 肯定是 $sur\operatorname{or}sur'$ 就能得到。而新的 $mus$，在 $sur'$ 为 $0$ 的位置上有 $mus\operatorname{xor}mus'$，为 $1$ 的位置上就直接有 $mus'$，因此我们考虑在不必要的位置上异或两次消去 $mus$。于是就得到了 $mus\operatorname{xor}mus'\operatorname{xor}(mus\operatorname{and}sur')$。 于是我们便可以 $O(1)$ 合并两个状态。至于回答询问，就从高往低贪心即可。 时间复杂度 $O(n\log^2n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int n,m,k; int fa[100100],son[100100],sz[100100],dep[100100],dfn[100100],rev[100100],top[100100],tot; vector<int>v[100100]; void dfs1(int x){sz[x]=1;for(auto y:v[x])if(y!=fa[x]){fa[y]=x,dep[y]=dep[x]+1,dfs1(y),sz[x]+=sz[y];if(sz[y]>sz[son[x]])son[x]=y;}} void dfs2(int x){if(!top[x])top[x]=x;dfn[x]=++tot,rev[tot]=x;if(son[x])top[son[x]]=top[x],dfs2(son[x]);for(auto y:v[x])if(y!=fa[x]&&y!=son[x])dfs2(y);} ull ALL; struct dat{ ull mus,sur; dat(){mus=sur=0;} dat(ull M,ull S){mus=M,sur=S;} friend dat operator+(const dat&u,const dat&v){return dat(u.mus^v.mus^(u.mus&v.sur),u.sur|v.sur);} }a[100100]; dat read(){ int tp;ull S; scanf("%d%llu",&tp,&S); if(tp==1)return dat(0,ALL&~S); if(tp==2)return dat(S,S); if(tp==3)return dat(S,0); } #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) struct SegTree{dat lval,rval;}seg[400100]; void pushup(int x){seg[x].lval=seg[rson].lval+seg[lson].lval,seg[x].rval=seg[lson].rval+seg[rson].rval;} void modify(int x,int l,int r,int P,dat val){ if(l>P||r<P)return; if(l==r)seg[x].lval=seg[x].rval=val;else modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val),pushup(x); } dat queryL(int x,int l,int r,int L,int R){if(l>R||r<L)return dat();if(L<=l&&r<=R)return seg[x].lval;return queryL(rson,mid+1,r,L,R)+queryL(lson,l,mid,L,R);} dat queryR(int x,int l,int r,int L,int R){if(l>R||r<L)return dat();if(L<=l&&r<=R)return seg[x].rval;return queryR(lson,l,mid,L,R)+queryR(rson,mid+1,r,L,R);} void build(int x,int l,int r){if(l==r){seg[x].lval=seg[x].rval=a[rev[l]];return;}build(lson,l,mid),build(rson,mid+1,r),pushup(x);} dat query(int x,int y){ dat lval,rval; while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]])lval=lval+queryL(1,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]]; else rval=queryR(1,1,n,dfn[top[y]],dfn[y])+rval,y=fa[top[y]]; } if(dep[x]>dep[y])lval=lval+queryL(1,1,n,dfn[y],dfn[x]); else rval=queryR(1,1,n,dfn[x],dfn[y])+rval; return lval+rval; } int main(){ scanf("%d%d%d",&n,&m,&k);if(k==64)ALL=-1;else ALL=(1ull<<k)-1; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x); dfs1(1),dfs2(1),build(1,1,n); for(int i=1,tp;i<=m;i++){ int x,y;ull z; scanf("%d",&tp); if(tp==1){ scanf("%d%d%llu",&x,&y,&z); dat w=query(x,y);ull ret=0; for(int j=k-1,lim=true;j>=0;j--){ if((w.sur&(1ull<<j))||(w.mus&(1ull<<j))||(!(z&(1ull<<j))&&lim)){//want to put a zero. if(z&(1ull<<j))lim=false; ret+=w.mus&(1ull<<j); }else ret+=(1ull<<j);//want to put an one, when and only when putting an one can get 1 on the bit. } printf("%llu\n",ret); }else scanf("%d",&x),modify(1,1,n,dfn[x],read()); } return 0; } ``` # L.[CF1514D Cut and Stick](https://www.luogu.com.cn/problem/CF1514D) 首先观察到答案只与区间众数个数有关。然后再想想发现其可以直接用区间众数 $O(1)$ 计算，因为最优的方法中，如果要分成多段，肯定是每次扔掉一个区间众数单独分一段。 区间众数的经典做法是分块。但是因为太懒我直接码了发回滚莫队上去，复杂度 $O(n\sqrt n)$。光荣TLE。 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int BBB=550; int n,m,a[300100],BLK[300100],buc[300100],lp[600],mx,lim,res[300100]; struct query{ int l,r,id; query(int L,int R,int I){l=L,r=R,id=I;} friend bool operator<(const query&u,const query&v){return u.r<v.r;} }; vector<query>v[600]; int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]),a[i]--,BLK[i]=i/BBB; BLK[n]=lim=BLK[n-1]+1; for(int i=0;i<lim;i++)lp[i]=i*BBB;lp[lim]=n; for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),l--,r--,v[BLK[l]].emplace_back(l,r,i); for(int i=0;i<lim;i++){ int R=lp[i+1];mx=0; for(auto x:v[i]){ if(x.r<R){ for(int j=x.l;j<=x.r;j++)mx=max(mx,++buc[a[j]]); res[x.id]=1+max(0,mx-(x.r-x.l+1)/2); mx=0; for(int j=x.l;j<=x.r;j++)buc[a[j]]=0; }else{ while(R<x.r)mx=max(mx,++buc[a[++R]]); int tmx=mx; for(int j=x.l;j<=lp[i+1];j++)mx=max(mx,++buc[a[j]]); res[x.id]=1+max(0,mx-(x.r-x.l+1)/2); mx=tmx;for(int j=x.l;j<=lp[i+1];j++)--buc[a[j]]; } } } for(int i=1;i<=m;i++)printf("%d\n",res[i]); return 0; } ``` 于是只能思考更快的方法。简单思考发现，如果区间众数并非严格众数，则答案一定为 $1$。而求出严格众数的方法是众所周知的摩尔投票法。于是用线段树维护摩尔投票结果即可简单处理。 当然，知道众数并不意味着我们知道众数个数。但这也很简单，直接用个 `vector` 在上面二分即可随便处理。 时间复杂度 $O(n\log n)$。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,a[300100]; struct SegTree{ int val,tms; SegTree(int X=1,int Y=0){val=X,tms=Y;} friend SegTree operator+(const SegTree&u,const SegTree&v){ if(u.val==v.val)return SegTree(u.val,u.tms+v.tms); if(u.tms>=v.tms)return SegTree(u.val,u.tms-v.tms); return SegTree(v.val,v.tms-u.tms); } }seg[1200100]; #define lson x<<1 #define rson x<<1|1 #define mid ((l+r)>>1) void build(int x,int l,int r){if(l==r)seg[x]=SegTree(a[l],1);else build(lson,l,mid),build(rson,mid+1,r),seg[x]=seg[lson]+seg[rson];} SegTree query(int x,int l,int r,int L,int R){ if(l>R||r<L)return SegTree(); if(L<=l&&r<=R)return seg[x]; return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R); } vector<int>v[300100]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),v[a[i]].push_back(i); build(1,1,n); for(int i=1,l,r;i<=m;i++){ scanf("%d%d",&l,&r); int col=query(1,1,n,l,r).val; int tms=upper_bound(v[col].begin(),v[col].end(),r)-lower_bound(v[col].begin(),v[col].end(),l); int smt=(r-l+1)-tms; printf("%d\n",1+max(0,tms-(smt+1))); } return 0; } ``` 五十题结束了，请用[续集](https://www.luogu.com.cn/blog/Troverld/gao-ji-shuo-ju-jie-gou-ii)。