重新写一年前抄题解的那题，当时我啥都不会只是Ctrl+C，Ctrl+V写过的题，今天重新写一遍。
题解：
不会线段树分治，还是学一下这东西吧，这是我的第一道线段树分治。
首先对于特殊商品，可以直接可持久化Trie记录答案。首先考虑对每个线段树开一个vector，把询问的时间区间看成一段一段的塞到线段树里，修改实际上是相当于一个后缀。然后把修改按位置排序，然后仿照线段树的形式按时间分治，mid前的修改扔到左边数组里递归，反之扔到右边，这样能够排除这一维的限制。然后空间上用可持久化Trie，前缀和相减即可。最开始的修改，要按照商店顺序排序，这样可以把中间的商店忽略，一个修改挨着一个修改建主席树，复杂度得以保证。
#include<bits/stdc++.h> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int N=1e5+7; struct guest{int l,r,L,R,x;}p[N]; struct buy{int s,v,t;}q[N],t1[N],t2[N]; int n,m,n1,n2,tot,top,rt[N],ans[N],st[N],ch[N*19][2],sz[N*19]; vector<int>a[N]; bool cmp(buy x,buy y){return x.s<y.s;} void build(int&x,int u,int S) { x=++tot; int now=x; for(int i=17;~i;i--) { bool d=S>>i&1; ch[now][d^1]=ch[u][d^1],ch[now][d]=++tot; now=ch[now][d],u=ch[u][d],sz[now]=sz[u]+1; } } int query(int l,int r,int S) { int ret=0; for(int i=17;~i;i--) { bool d=S>>i&1; if(sz[ch[r][d^1]]-sz[ch[l][d^1]]>0)l=ch[l][d^1],r=ch[r][d^1],ret+=1<<i; else l=ch[l][d],r=ch[r][d]; } return ret; } void update(int L,int R,int x,int l,int r,int rt) { if(L>R)return; if(L<=l&&r<=R){a[rt].push_back(x);return;} int mid=l+r>>1; if(L<=mid)update(L,R,x,lson); if(R>mid)update(L,R,x,rson); } void calc(int x,int L,int R) { top=tot=0; for(int i=L;i<=R;i++)st[++top]=q[i].s,build(rt[top],rt[top-1],q[i].v); for(int i=0,k,l,r;i<a[x].size();i++) { k=a[x][i]; l=upper_bound(st+1,st+top+1,p[k].l-1)-st-1,r=upper_bound(st+1,st+1+top,p[k].r)-st-1; ans[k]=max(ans[k],query(rt[l],rt[r],p[k].x)); } } void divide(int l,int r,int rt,int L,int R) { if(L>R)return; int mid=l+r>>1,cnt1=0,cnt2=0; calc(rt,L,R); if(l==r)return; for(int i=L;i<=R;i++)if(q[i].t<=mid)t1[++cnt1]=q[i];else t2[++cnt2]=q[i]; for(int i=1;i<=cnt1;i++)q[i+L-1]=t1[i]; for(int i=1;i<=cnt2;i++)q[i+L-1+cnt1]=t2[i]; divide(lson,L,L+cnt1-1); divide(rson,L+cnt1,R); } int main() { scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++)scanf("%d",&x),build(rt[i],rt[i-1],x); for(int i=1,op,l,r,x,d;i<=m;i++) { scanf("%d%d%d",&op,&l,&r); if(!op)q[++n1]=(buy){l,r,n1}; else{ scanf("%d%d",&x,&d); ans[++n2]=query(rt[l-1],rt[r],x); p[n2]=(guest){l,r,max(1,n1-d+1),n1,x}; } } for(int i=1;i<=n2;i++)update(p[i].L,p[i].R,i,1,n1,1); sort(q+1,q+n1+1,cmp); divide(1,n1,1,1,n1); for(int i=1;i<=n2;i++)printf("%d ",ans[i]); }