颓文化课作业到很晚写篇博客清醒一下
首先我们仔细阅读并猜测了题意之后，就会想到一个暴力的线段树套可持久化0/1Trie的做法，但是它显然是过不去的
由于最近再做线段树分治的题，我们可以想到用线段树分治来解决这个问题
考虑对于每一次询问，我们都可以找出它连续询问的一段时间区间，然后把它扔进线段树的每个节点里
考虑怎么加点，如果暴力插入修改那就和暴力没什么区别了，我们还要考虑进一步优化
还是一个老套路，由于线段树分治是一种离线算法，因此插入修改的顺序完全可以由我们自己决定
那么再此利用分治的思想，每次插入点时一个区间一个区间的加入，查询的话就用二分+可持久化0/1Trie来资瓷就好了
这样总体复杂度就到了可以接受的\(O(n\log^2 n)\)，足以通过此题
#include<cstdio>
#include<cctype>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=100005,R=17;
struct event
{
int s,v,t;
friend inline bool operator < (const event& A,const event& B)
{
return A.s<B.s;
}
}et[N]; int cnt_et;
struct ques
{
int l,r,tl,tr,v;
}q[N]; int cnt_q;
int n,m,opt,x,ans[N];
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=0)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[15];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x)
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc('\n');
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
class Zero_One_Trie
{
private:
struct segment
{
int ch[2],sum;
inline segment(CI Ls=0,CI Rs=0,CI Sum=0)
{
ch[0]=Ls; ch[1]=Rs; sum=Sum;
}
}node[N*R<<2]; int tot,num,rt[N];
#define S(x) node[x].sum
inline void _insert(CI lst,int& now,CI val,CI d=R)
{
now=++tot; node[now]=node[lst]; ++S(now); if (!~d) return;
bool c=(val>>d)&1; _insert(node[lst].ch[c],node[now].ch[c],val,d-1);
}
inline int _query(CI lst,CI now,CI val,CI d=R)
{
if (!~d) return 0; bool c=(val>>d)&1; return S(node[now].ch[c^1])-S(node[lst].ch[c^1])?
_query(node[lst].ch[c^1],node[now].ch[c^1],val,d-1)+(1<<d):_query(node[lst].ch[c],node[now].ch[c],val,d-1);
}
#undef S
public:
inline void insert(CI val)
{
++num; _insert(rt[num-1],rt[num],val);
}
inline int query(CI l,CI r,CI val)
{
if (l>r) return 0; _query(rt[l-1],rt[r],val);
}
inline void clear(void)
{
RI i; for (i=1;i<=tot;++i) node[i]=segment();
for (i=1;i<=num;++i) rt[i]=0; tot=num=0;
}
}T;
class Segment_Tree
{
private:
vector <int> pv[N<<2]; event ls[N],rs[N]; int stk[N],top;
#define TN CI now=1,CI l=1,CI r=cnt_et
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void calc(CI now,CI l,CI r)
{
T.clear(); top=0; for (RI i=l;i<=r;++i) stk[++top]=et[i].s,T.insert(et[i].v);
for (vector <int>::iterator it=pv[now].begin();it!=pv[now].end();++it)
{
int ql=upper_bound(stk+1,stk+top+1,q[*it].l-1)-stk;
int qr=upper_bound(stk+1,stk+top+1,q[*it].r)-stk-1;
ans[*it]=max(ans[*it],T.query(ql,qr,q[*it].v));
}
}
public:
inline void insert(CI beg,CI end,CI pos,TN)
{
if (beg>end) return; if (beg<=l&&r<=end) return (void)(pv[now].push_back(pos));
int mid=l+r>>1; if (beg<=mid) insert(beg,end,pos,LS); if (end>mid) insert(beg,end,pos,RS);
}
inline void solve(CI st=1,CI ed=cnt_et,TN)
{
if (st>ed) return; calc(now,st,ed); if (l==r) return; int mid=l+r>>1,lct=0,rct=0;
RI i; for (i=st;i<=ed;++i) if (et[i].t<=mid) ls[++lct]=et[i]; else rs[++rct]=et[i];
for (i=1;i<=lct;++i) et[st+i-1]=ls[i]; for (i=1;i<=rct;++i) et[st+lct+i-1]=rs[i];
solve(st,st+lct-1,LS); solve(st+lct,ed,RS);
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (F.read(n),F.read(m),i=1;i<=n;++i) F.read(x),T.insert(x);
for (i=1;i<=m;++i)
{
F.read(opt); if (!opt) F.read(et[++cnt_et].s),F.read(et[cnt_et].v),et[cnt_et].t=cnt_et;
else F.read(q[++cnt_q].l),F.read(q[cnt_q].r),F.read(q[cnt_q].v),
F.read(x),q[cnt_q].tl=max(1,cnt_et-x+1),q[cnt_q].tr=cnt_et;
}
for (i=1;i<=cnt_q;++i) ans[i]=T.query(q[i].l,q[i].r,q[i].v),SEG.insert(q[i].tl,q[i].tr,i);
for (sort(et+1,et+cnt_et+1),SEG.solve(),i=1;i<=cnt_q;++i) F.write(ans[i]);
return F.flush(),0;
}