与可持久化线段树重逢在了Codeforces Educational Round 80的E题，还好及时意识到了是可持久化线段树的经典操作——统计区间内不同的数字个数。
于是乎，赛后又重新复习了一下可持久化线段树，
可持久化意味着需要建立多个版本，为了节省空间，利用增量修改的想法，我们只去记录那些发生变化的部分（因此要求整个数据结构的结构不能发生变化，针对那些带旋转的平衡树），
往往要追求的目标是发生修改的部分是从根到叶子的一条链，树高是O(logN)的，因此只会新增O(logN)个节点，最后的节点总数是O(N+MlogN)。
其实这就限制了绝大部分修改都只能是单点修改。
而建立完可持久化线段树之后呢，无论是修改还是查询操作，我们在确定完在哪个版本之后，都只需要当成是在一棵线段树上考虑即可。
我觉得思考一个问题是否可以用可持久化线段树来做，关键还是思考线段树维护的是什么信息，从而能否把修改操作变成单点修改，或者查询的操作可以如愿完成。
然后有些查询操作需要满足可减性，比如最常见的区间第k大。
然后有时候会把问题搬到树上，一般是再多考虑LCA或者LCA的父亲的情况，具体的应用会非常灵活，需要具体问题具体分析。
静态区间第K大——我们建立权值线段树，每个节点代表的是权值的出现次数，非叶子节点记录的是区间内的权值的出现次数，然后从左到右往上一个版本插入新的数形成新的版本。查找第K大的时候从上到下直接根据数值关系找就行了。
不强制在线的话还可以用离线+树状数组写，常数会小很多。（关于离线处理的数据结构题，过几天会总结一下之前遇到过的几道，待更）
区间内不同的数字个数——这个我觉得非常巧妙，因为查询的是一个区间，当右端点固定的时候，肯定是越往右的数字越容易出现在区间中，因为我们把那些到目前为止最后一次出现该数字的位置设为1，其余都为0，然后在区间内查找[l,r]范围内的区间和即可。修改都是单点修改。
区间内前K小的值的总和——其实只要在第K大的基础上再维护个权值区间对应的总和就可以了。
此外，有些问题可能用二分的思想会降低思维难度，然后里面再套个可持久化线段树，但是这样复杂度有时候会多一个log，有时候可以直接在主席树上一路往下找，省掉那个log。
最后，贴一下这次E题我的做法吧，观察到一个数字出现过就变成了第一，然后就不可能往前，要么不动，要么往后移，直到下次出现。那么相邻两次出现的间隔中出现的不同的数字个数就是一个极大值，去更新最大值即可，最小值比较朴素，判断是否出现过即可。为了避免边界条件，把原数组扩充了一下，一定程度导致空间有点吃紧。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=600005; struct node{ int l,r,sum; }T[maxn*32]; int n,m,a[maxn],cnt,root[maxn],pos[maxn]; vector<int> v[maxn+5]; int mn[maxn+5],mx[maxn+5]; void update(int &now,int pre,int val,int l,int r,int pos){ T[++cnt]=T[pre],T[cnt].sum+=val,now=cnt; if(l==r) return; int mid=l+r>>1; if(pos<=mid) update(T[now].l,T[pre].l,val,l,mid,pos); else update(T[now].r,T[pre].r,val,mid+1,r,pos); } int query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return T[rt].sum; int ans=0,mid=l+r>>1; if(L<=mid) ans+=query(L,R,l,mid,T[rt].l); if(R>mid) ans+=query(L,R,mid+1,r,T[rt].r); return ans; } int main(){ scanf("%d",&n); scanf("%d",&m); for (int i=1;i<=n;i++) a[i]=n-i+1; for (int i=n+1;i<=n+m;i++) scanf("%d",&a[i]); for (int i=1;i<=n+m;i++) v[a[i]].push_back(i); for (int i=1;i<=n+m;i++){ if(pos[a[i]]){ update(root[i],root[i-1],-1,1,n+m,pos[a[i]]); update(root[i],root[i],1,1,n+m,i); }else update(root[i],root[i-1],1,1,n+m,i); pos[a[i]]=i; } for (int i=1;i<=n;i++) if (v[i][v[i].size()-1]>n) { mn[i]=1; } else mn[i]=i; for (int i=1;i<=n;i++) { for (int j=0;j<v[i].size()-1;j++) { int lef=v[i][j],rig=v[i][j+1]; mx[i]=max(mx[i],query(lef,rig,1,n+m,root[rig])); } mx[i]=max(mx[i],query(v[i][v[i].size()-1],n+m,1,n+m,root[n+m])); } for (int i=1;i<=n;i++) printf("%d %d ",mn[i],mx[i]); return 0; }