一道块状链表题

给一个序列，初始时为空，要求支持两种操作：

1. 在某个位置之前插入一个数；
2. 求某个区间中的数异或 x 的最大值。

这题如果平衡树的话会涉及到 Trie 的合并，复杂度$O(n\log_2^3n)$。于是可以勇一波块链上去。在经过精细调参之后成功比暴力快了。加了快读后就更快了。

这次是采用动态分配内存的方式实现的，似乎常数挺大。

以后写分块算法的题要留一些时间调参。

#include<algorithm>/*{{{*/
#include<cctype>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
namespace RA{
    int r(int p){return 1ll*rand()*rand()%p;}
    int r(int L,int R){return r(R-L+1)+L;}
}/*}}}*/
/******************heading******************/
char nc(){
    static char bf[100000],*p1=bf,*p2=bf;
    return p1==p2&&(p2=(p1=bf)+ fread(bf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd(){
    int res=0; char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res;
}
int tmp[20],lt;
char OBF[100000],*OBP=OBF;
void flush(){
    fwrite(OBF,1,OBP-OBF,stdout),OBP=OBF;
}
void wrch(char x){
    if(OBP==OBF+99999)flush();
    *OBP=x,++OBP;
}
void wr(int x){
    lt=0;
    while(x)tmp[++lt]=x%10,x/=10;
    while(lt > 0) wrch(tmp[lt]+'0'), --lt;
}
void wr(long long x){
    lt=0;
    while(x)tmp[++lt]=x%10,x/=10;
    while(lt > 0) wrch(tmp[lt]+'0'), --lt;
}
void wr(const char * s){ while(*s)wrch(*s),++s; }
void wr(char x){ wrch(x); }
int max(int x,int y){ return x>y?x:y; }
typedef vector<int> Vi;
struct list{
    list * nex, * pre; Vi v;
    struct trnode{
        bool e;
        trnode *g[2];
        trnode(){ g[0]=g[1]=NULL, e=0; }
    } * tr;
    void trie_insert(const int& x){
        trnode * u=tr;
        ROF(j,20,0){
            int c=x>>j&1;
            if(u->g[c]==NULL)u->g[c]=new trnode;
            u=u->g[c];
        }
        u->e=1;
    }
    int query(const int& k){
        int res=0;
        trnode * u=tr;
        ROF(j,20,0){
            int c=k>>j&1;
            if(u->g[!c]!=NULL)u=u->g[!c],res|=1<<j;
            else u=u->g[c];
        }
        return res;
    }
    list(){ tr=new trnode;nex=pre=NULL;}
    Vi::iterator insert(Vi::iterator it,const int &x){
        trie_insert(x);
        return v.insert(it,x);
    }
    Vi::iterator insert(int pos,const int &x){ return insert(v.begin()+pos,x); }
    int & operator[](int x){ return v[x]; }
    int size(){ return v.size(); }
    void split(){
        int sz=size(),mid=sz/2;
        if(sz==1)return;
        list * u = new list;
        u->pre=this,u->nex=this->nex,this->nex=u;
        FOR(i,mid,sz-1)u->insert(i-mid,v[i]);
        v.erase(v.begin()+mid,v.end());
        tr->g[0]=tr->g[1]=NULL;
        for(int i:v)trie_insert(i);
    }
}*L;

int T,Lim,typ,lans;
void insert(int pos,const int& x){
    list * cur=L;
    while(cur->size()<=pos&&cur->nex!=NULL)pos-=cur->size(),cur=cur->nex;
    cur->insert(pos,x);
    if(cur->size()>=Lim*2)cur->split();
}
int query(int l,int r,const int& k){
    int res=0;
    for(list * cur=L;cur!=NULL;cur=cur->nex){
        int sz=cur->size();
        if(r<0)break;
        if(l<=0&&sz-1<=r)res=max(res,cur->query(k));
        else {
            int X=max(l,0),Y=min(r,sz-1);
            FOR(i,X,Y) res=max(res,cur->v[i]^k);
        }
        l-=sz,r-=sz;
    }
    return res;
}
int main(){
    L=new list;
    T=rd(),typ=rd();
    Lim=sqrt(T)*8;
    FOR(i,1,T){
        int op,x,y,z;
        op=rd();
        if(op==0){
            x=rd(),y=rd();
            if(typ)x^=lans,y^=lans;
            insert(x-1,y);
        }else{
            x=rd(),y=rd(),z=rd();
            if(typ)x^=lans,y^=lans,z^=lans;
            int ans=query(x-1,y-1,z);
            wr(ans),wr('\n');
            lans=ans;
        }
    }
    flush();
    return 0;
}