颓文化课作业到很晚写篇博客清醒一下

首先我们仔细阅读并猜测了题意之后，就会想到一个暴力的线段树套可持久化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;
}