bzoj3217 ALOEXT
Description
给定一个序列，有以下 4 种操作：
- I x y 插入 y 到第 x 个之前。
- D x 删除第 x 个元素。
- C x y 修改第 x 个元素为 y。
- F l r 询问区间 [l,r] 的次大值与区间一个数的异或最大值。
强制在线，1leq N,M leq 10^5。
Solution
这道题显然可以用替罪羊树套 Trie 解决，但是对于不会替罪羊树的选手（比如我）就可以选择块状链表 Trie。
区间次大值直接用 Multiset 维护即可，异或最大值直接在 Trie 上跑一下即可。
注意块大小因为套了个 Trie 所以要适量调大。
然后本人调了一整天，祝你好运~
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=2e5 10,S=5000,M=N/S 2,P=1048576;
I int RC(){char c=gc();W(c^'I'&&c^'D'&&c^'C'&&c^'F') c=gc();return c=='I'?1:c=='D'?2:c=='C'?3:4;}
int n,m,tot;
vector<int> b[M];
multiset<int> s[M];
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
class TrieTree{
private:
int p[S*100][2],cnt,w[S*100];
#define nw ((v>>i)&1)
public:
I void clear(){cnt=1;memset(p,0,sizeof(p));memset(w,0,sizeof(w));}
I void A(CI v){RI i,u=1;for(i=20;~i;i--) !p[u][nw]&&(p[u][nw]= cnt),w[p[u][nw]] ,u=p[u][nw];}
I void K(CI v){RI i,u=1,t;for(i=20;~i;i--) w[p[u][nw]]--,u=p[u][nw];}
I int Q(CI v){RI i,u=1,X=0;for(i=20;~i;i--) (p[u][nw^1]&&w[p[u][nw^1]])?X =(1<<i),u=p[u][nw^1]:u=p[u][nw];return X;}
}T[M];
I void H(PA& X,CI v){v>X.fi?X.se=X.fi,X.fi=v:X.se=max(X.se,v);}
I PA G(CI l,CI x,CI y){PA o=MP(0,0);for(auto i=b[l].begin() x;i!=b[l].begin() y 1;i ) H(o,*i);return o;}
I int F(CI l,CI x,CI y,CI v){RI mx=0;for(auto i=b[l].begin() x;i!=b[l].begin() y 1;i ) mx=max(mx,(*i)^v);return mx;}
I int Z(CI L,CI R,CI v){RI i,mx=0;for(i=L;i<=R;i ) mx=max(mx,T[i].Q(v));return mx;}
I void O(PA& o,PA v){H(o,v.fi),H(o,v.se);}
I PA E(CI L,CI R){PA o=MP(0,0);RI i;for(i=L;i<=R;i ){auto it=s[i].rbegin();if(it!=s[i].rend()){H(o,*it); it;if(it!=s[i].rend()) H(o,*it);}}return o;}
I int Q(RI l,RI r){
PA o=MP(0,0);RI bL=1,bR=1;W(l>=b[bL].size()) l-=b[bL ].size();W(r>=b[bR].size()) r-=b[bR ].size();if(bL==bR) return O(o,G(bL,l,r)),F(bL,l,r,o.se);
else return O(o,G(bL,l,b[bL].size()-1)),O(o,G(bR,0,r)),O(o,E(bL 1,bR-1)),max(Z(bL 1,bR-1,o.se),max(F(bL,l,b[bL].size()-1,o.se),F(bR,0,r,o.se)));
}
I void C(CI i,CI v){s[i].erase(s[i].find(v)),T[i].K(v);}
I void J(CI i,CI v){s[i].insert(v),T[i].A(v);}
I void U(RI x,CI v){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL ].size();t=b[bL][x],C(bL,t);b[bL][x]=v,J(bL,v);}
I void A(RI x,CI v){
RI i,t,bL=1;W(x>=b[bL].size()) x-=b[bL ].size();b[bL].insert(b[bL].begin() x,v),J(bL,v);for(i=bL 1;i<=tot;i ) if(b[i-1].size()<=S) break ;
else t=b[i-1].back(),C(i-1,t),b[i-1].pop_back(),b[i].insert(b[i].begin(),t),J(i,t);if(b[tot].size()>S) tot,T[tot].clear(); n;
}
I void K(RI x){RI i,bL=1,t;W(x>=b[bL].size()) x-=b[bL ].size();t=b[bL][x];b[bL].erase(b[bL].begin() x),C(bL,t);--n;}
int main(){
// freopen("I.in","r",stdin);freopen("I.out","w",stdout);
RI i,x,l,r,p=0;for(read(n,m),tot=n/S 1,i=1;i<=tot;i ) T[i].clear();for(i=0;i<n;i ) read(x),b[i/S 1].push_back(x),s[i/S 1].insert(x),T[i/S 1].A(x);
W(m--) if((x=RC())==1) read(l,r),l=(l p)%n,r=(r p)%P,A(l,r);else if(x==2) read(l),l=(l p)%n,K(l);
else if(x==3) read(l,r),l=(l p)%n,r=(r p)%P,U(l,r);else if(x==4) read(l,r),l=(l p)%n,r=(r p)%n,l>r&&(swap(l,r),0),writeln(p=Q(l,r));return 0;
}
