个人acm模板整理

• 1.数学
• • 1.1.普通lucas
  • 扩展卢卡斯定理/exLucas
  • 1.2扩展中国剩余定理（EXCRT）
  • 1.3模数原根表
  • 1.4拓展欧拉定理
  • 2.5多项式启发式合并
• 2.数据结构
• • 2.1线段树合并
  • 2.2线段树分裂
  • 2.3splay&&fhq
  • 2.4线段树分治
  • 2.5可持久化线段树
  • 2.6动态开点线段树
  • 2.7虚树(Static Query on Tree)

#include
using namespace std;
typedef long long ll;
const int N=1e5+100;
ll a[N];
ll p;
ll pow(ll y,ll z,ll p){
    y%=p;ll ans=1;
    for(ll i=z;i;i>>=1,y=y*y%p) if(i&1) ans=ans*y%p;
    return ans;
}
ll C(ll n,ll m){
    if(m>n) return 0;
    return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
ll lucas(ll n,ll m){
    if(!m) return 1;
    return C(n%p,m%p)*lucas(n/p,m/p)%p;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m>>p;
        a[0]=1;
        for(int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;
        cout< 
扩展卢卡斯定理/exLucas 
#include
#define ll long long
using namespace std;
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
#ifdef Fading
#define gc getchar
#endif
void exgcd(ll a,ll b,ll &x,ll &y){
    if (!b) return (void)(x=1,y=0);
    exgcd(b,a%b,x,y);
    ll tmp=x;x=y;y=tmp-a/b*y;
}
ll gcd(ll a,ll b){
    if (b==0) return a;
    return gcd(b,a%b); 
}
inline ll INV(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
inline ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline ll mabs(ll x){
    return (x>0?x:-x);
}
inline ll fast_mul(ll a,ll b,ll p){
    ll t=0;a%=p;b%=p;
    while (b){
        if (b&1LL) t=(t+a)%p;
        b>>=1LL;a=(a+a)%p;
    }
    return t;
}
inline ll fast_pow(ll a,ll b,ll p){
    ll t=1;a%=p;
    while (b){
        if (b&1LL) t=(t*a)%p;
        b>>=1LL;a=(a*a)%p;
    }
    return t;
}
inline ll read(){
    ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while (isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
inline ll F(ll n,ll P,ll PK){
    if (n==0) return 1;
    ll rou=1;//循环节
    ll rem=1;//余项 
    for (ll i=1;i<=PK;i++){
        if (i%P) rou=rou*i%PK;
    }
    rou=fast_pow(rou,n/PK,PK);
    for (ll i=PK*(n/PK);i<=n;i++){
        if (i%P) rem=rem*(i%PK)%PK;
    }
    return F(n/P,P,PK)*rou%PK*rem%PK;
}
inline ll G(ll n,ll P){
    if (n
    ll fz=F(n,P,PK),fm1=INV(F(m,P,PK),PK),fm2=INV(F(n-m,P,PK),PK);
    ll mi=fast_pow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
    return fz*fm1%PK*fm2%PK*mi%PK;
}
ll A[1001],B[1001];
//x=B(mod A)
inline ll exLucas(ll n,ll m,ll P){
    ll ljc=P,tot=0;
    for (ll tmp=2;tmp*tmp<=P;tmp++){
        if (!(ljc%tmp)){
            ll PK=1;
            while (!(ljc%tmp)){
                PK*=tmp;ljc/=tmp;
            }
            A[++tot]=PK;B[tot]=C_PK(n,m,tmp,PK);
        }
    }
    if (ljc!=1){
        A[++tot]=ljc;B[tot]=C_PK(n,m,ljc,ljc);
    }
    ll ans=0;
    for (ll i=1;i<=tot;i++){
        ll M=P/A[i],T=INV(M,A[i]);
        ans=(ans+B[i]*M%P*T%P)%P;
    }
    return ans;
}
signed main(){
    ll n=read(),m=read(),P=read();
    printf("%lldn",exLucas(n,m,P));
    return 0;
}

 
1.2扩展中国剩余定理（EXCRT） 
#include
using namespace std;
typedef __int128 ll;
ll ext_gcd(ll a,ll b,ll &x,ll &y){
    ll t,d;
    if(b==0){x=1;y=0;return a;}
    d=ext_gcd(b,a%b,x,y);
    t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
ll Invmod(ll a,ll n){
    ll x,y;
    if(ext_gcd(a,n,x,y)!=1) return -1;
    return (x%n+n)%n;
}
bool mergef(ll b1,ll c1,ll b2,ll c2,ll &b,ll &c){
    ll tb1=b1,tb2=b2;
    c=((c2-c1)%b2+b2)%b2;
    ll g=__gcd(b1,b2);
    if(c%g) return false;
    c/=g;
    b1/=g;
    b2/=g;
    c=c*Invmod(b1,b2)%b2;
    c=c*tb1+c1;
	b=tb1*tb2/g;
    c%=b;
    return true;
}
ll merge(long long b[],long long c[],int n){
    ll bb=b[0],cc=c[0],bbb,ccc;
    ll i;
    for(i=1;i
        if(!mergef(bb,cc,b[i],c[i],bbb,ccc))
            return -1;
            bb=bbb;
            cc=ccc;
    }
    return cc;
}

const int N=1e5+10;
long long ww[N],bb[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i>ww[i]>>bb[i];
    cout<<(long long)merge(ww,bb,n);


}
 
1.3模数原根表 
模数原根表
常用素数：
P = 1004535809  ====>  pr = 3
P = 998244353  =====>  pr = 3

//（g 是mod(r*2^k+1)的原根）
 
素数  r  k  g
3   1   1   2
5   1   2   2
17  1   4   3
97  3   5   5
193 3   6   5
257 1   8   3
7681    15  9   17
12289   3   12  11
40961   5   13  3
65537   1   16  3
786433  3   18  10
5767169 11  19  3
7340033 7   20  3
23068673    11  21  3
104857601   25  22  3
167772161   5   25  3
469762049   7   26  3
1004535809  479 21  3
2013265921  15  27  31
2281701377  17  27  3
3221225473  3   30  5
75161927681 35  31  3
77309411329 9   33  7
206158430209    3   36  22
2061584302081   15  37  7
2748779069441   5   39  3
6597069766657   3   41  5
39582418599937  9   42  5
79164837199873  9   43  5
263882790666241 15  44  7
1231453023109121    35  45  3
1337006139375617    19  46  3
3799912185593857    27  47  5
4222124650659841    15  48  19
7881299347898369    7   50  6
31525197391593473   7   52  3
180143985094819841  5   55  6
1945555039024054273 27  56  5
4179340454199820289 29  57  3
 
1.4拓展欧拉定理 
 
#include
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,ll q){
    ll ans=1;
    a%=q;
    while(b){
        if(b&1) ans=(ans*a)%q;
        b>>=1;
        a=a*a%q;
    }
    return ans;
}
int euler(int n){
    int ans=1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            n/=i;
            ans*=i-1;
            while(n%i==0){
                n/=i;
                ans*=i;
            }
        }
    }
    if(n>1) ans*=n-1;
    return ans;
}
int main(){
    ll a,m,bb=0,flag=0;
    string b;
    cin>>a>>m>>b;
    ll phi=euler(m);
    for(int i=0;i
        bb*=10;
        bb+=b[i]-'0';
        if(bb>=phi){
            bb%=phi;
            flag=1;
        }
    }
    if(flag==1) bb+=phi;
    cout< 
2.5多项式启发式合并 
#include 
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int N = 1e6+7;
const int mod = 998244353;
ll fac[N];
ll invf[N];
ll qpow(ll x,ll n) {
	ll res = 1;
	while (n) {
		if (n&1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
ll C(int m,int n) {
	return fac[m]*invf[n]%mod*invf[m-n]%mod;
}
namespace Poly {
	#define ck(x) (x>=mod?x-mod:x)
	typedef vector poly;
	const int G = 3;
	const int inv_G = qpow(G,mod-2);
	int RR[N],deer[2][19][N],inv[N];
	void init(const int t) {
		for (int p=1;p<=t;p++) {
			int buf1 = qpow(G,(mod-1)/(1<
				deer[0][p][i] = 1ll*deer[0][p][i-1]*buf0%mod;
				deer[1][p][i] = 1ll*deer[1][p][i-1]*buf1%mod;
			}
		}
		inv[1] = 1;
		for (int i=2;i<=(1<
			inv[i] = 1ll*inv[mod%i]*(mod-mod/i)%mod;
		}
	}
	int NTT_init(int n) {
		int limit = 1,L = 0;
		while (limit<=n) limit<<=1,L++;
		for (int i=0;i
			RR[i] = (RR[i>>1]>>1|((i&1)<<(L-1)));
		}
		return limit;
	}
	void NTT(poly &A,int type,int limit) {
		A.resize(limit);
		for (int i=0;i
			if (i
			int len = mid>>1;
			for (int pos=0;pos
				int *wn = deer[type][j];
				for (int i=pos;i
					int tmp = 1ll*(*wn)*A[i+len]%mod;
					A[i+len] = ck(A[i]-tmp+mod);
					A[i] = ck(A[i]+tmp);
				}
			}
		}
		if (type==0) {
			for (int i=0;i
				A[i] = 1ll*A[i]*inv[limit]%mod;
			}
		}
	}
	poly poly_mul(poly A,poly B) {
		int deg = A.size()+B.size()-1;
		int limit = NTT_init(deg);
		poly C(limit);
		NTT(A,1,limit);
		NTT(B,1,limit);
		for (int i=0;i
			C[i] = 1ll*A[i]*B[i]%mod;
		}
		NTT(C,0,limit);
		C.resize(deg);
		return C;
	}
}
using namespace Poly;
poly a[N];
typedef pair pii;
int main() {
	fac[0] = 1;
	for (int i=1;i=0;i--) {
		invf[i] = invf[i+1]*(i+1)%mod;
	}
	init(18);
	int m,k;
	cin>>m>>k;
	a[0].push_back(1);
	for(int i=1,now;i<=m;i++){
		cin>>now;
		a[i].push_back(1);
		a[i].push_back(now);
	}
	priority_queue,greater> q;
	for (int i=1;i<=m;i++) {
		q.push({a[i].size(),i});
	}
	while (q.size()>1) {
		int id1 = q.top().se;
		q.pop();
		int id2 = q.top().se;
		q.pop();
		a[id1] = poly_mul(a[id1],a[id2]);
		q.push({a[id1].size(),id1});
	} 
	int id = q.top().se;
	ll tmp = a[id][k];	
	ll tmp2 = k;
	tmp2 = qpow(tmp2,k/2);
	tmp = tmp*qpow(tmp2,mod-2)%mod*qpow(C(m,k),mod-2)%mod;
	cout< 
2.数据结构 
2.1线段树合并 
#include
using namespace std;
const int N=2e5;
const int LOG=40;
vectorg[N];
int n,m,q[N],deep[N];
int t,f[N][30];
int root[N*LOG],ma[N*LOG],type[N*LOG],lc[N*LOG],rc[N*LOG],cnt;
#define mid ((l+r)>>1)
void dfs(int rt){
    int hh=0,tt=0;
    q[tt++]=rt;
    deep[rt]=1;
    while(hh!=tt){
        int x=q[hh++];
        if(hh==N) hh=0;
        for(auto y:g[x]){
            if(deep[y]) continue;
            deep[y]=deep[x]+1;
            q[tt++]=y;
            if(tt==N) tt=0;
            f[y][0]=x;
            for(int j=1;j<=t;j++) 
            f[y][j]=f[f[y][j-1]][j-1];
        }
    }
}
int lca(int x,int y){
    if(deep[x]>deep[y]) swap(x,y);
    for(int i=t;i>=0;i--)
        if(deep[f[y][i]]>=deep[x])
            y=f[y][i];
    if(x==y) return x;
    for(int i=t;i>=0;i--) 
        if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
void pushup(int node){
    ma[node]=max(ma[lc[node]],ma[rc[node]]);
    type[node]=ma[lc[node]]>=ma[rc[node]] ? type[lc[node]]:type[rc[node]];    
}
void update(int &node,int l,int r,int x,int v){
    if(node==0) node=++cnt;
    if(l==r){
        ma[node]+=v;
        type[node]=l;
        return ;
    }
    if(x<=mid) update(lc[node],l,mid,x,v);
    else update(rc[node],mid+1,r,x,v);
    pushup(node);
}
int query(int node){
    return type[node];
}
int merge(int a,int b,int l,int r){
    if(!a||!b) return a+b;
    if(l==r){
        ma[a]=ma[a]+ma[b];
        type[a]=l;
        return a;
    }
    lc[a]=merge(lc[a],lc[b],l,mid);
    rc[a]=merge(rc[a],rc[b],mid+1,r);
    pushup(a);
    return a;
}
int ans[N];
void dfs1(int x,int fa){
    for(auto son:g[x]) {
        if(son==fa) continue;
        dfs1(son,x);
    }
    for(auto son:g[x]){
        if(son==fa) continue;
        root[x]=merge(root[x],root[son],0,N);
    }
    ans[x]=query(root[x]);
}


int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=n-1;i++){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    g[n+1].push_back(1),g[1].push_back(n+1);
    t=(int)(log(n+1)/log(2))+2;
    dfs(n+1);
    for(int i=1,a,b,z;i<=m;i++){
        cin>>a>>b>>z;
        if(deep[a]>deep[b]) swap(a,b);
        int fa=lca(a,b);
        if(fa==a){
            update(root[f[fa][0]],0,N,z,-1);
            update(root[b],0,N,z,+1);
        }
        else {
            update(root[f[fa][0]],0,N,z,-1);
            update(root[fa],0,N,z,-1);
            update(root[b],0,N,z,+1);
            update(root[a],0,N,z,+1);
        }
    }
    dfs1(n+1,-1);
    for(int i=1;i<=n;i++) cout< 
2.2线段树分裂 
#include
using namespace std;
#define mid ((l+r)>>1)
#define int long long
const int MAXN=3e5;
const int LOG=30;
int root[MAXN*LOG],sum[MAXN*LOG],lc[MAXN*LOG],rc[MAXN*LOG],cnt;
const int V=3e5;
void pushup(int x){
    sum[x]=sum[lc[x]]+sum[rc[x]];
}
int query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[node];
    int ans=0;
    if(ql<=mid) ans+=query(lc[node],l,mid,ql,qr);
    if(qr>=mid+1) ans+=query(rc[node],mid+1,r,ql,qr);
    return ans;
}
int querykth(int node,int l,int r,int k){
    if(l==r) return l;
    if(sum[lc[node]]>=k) return querykth(lc[node],l,mid,k);
    else return querykth(rc[node],mid+1,r,k-sum[lc[node]]);
}
void update(int &node,int l,int r,int x,int v){
    if(!node) node=++cnt;
    if(l==r){sum[node]+=v;return ;}
    if(x<=mid) update(lc[node],l,mid,x,v);
    else update(rc[node],mid+1,r,x,v);
    pushup(node);
}
int merge(int a,int b,int l,int r){
    if(!a||!b) return a+b;
    if(l==r){
        sum[a]=sum[a]+sum[b];
        return a;
    }
    lc[a]=merge(lc[a],lc[b],l,mid);
    rc[a]=merge(rc[a],rc[b],mid+1,r);
    pushup(a);
    return a;
}
int split(int &a,int b,int ql,int qr,int l,int r){
    if(ql<=l&&r<=qr) {b=a;a=0;return b;}if(!b) b=++cnt;
    if(ql<=mid) lc[b]=split(lc[a],lc[b],ql,qr,l,mid);
    if(qr>mid) rc[b]=split(rc[a],rc[b],ql,qr,mid+1,r);
    pushup(a),pushup(b);return b;
}

int n,m;
int od=1;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int now;cin>>now;
        update(root[1],1,V,i,now);
    }
    for(int i=1;i<=m;i++){
        int opt,x,y,p,t,q,k;cin>>opt;
        if(opt==0){
            cin>>p>>x>>y;
            od++;
            root[od]=split(root[p],root[od],x,y,1,V);
        }else if(opt==1){
            cin>>p>>t;
            root[p]=merge(root[p],root[t],1,V);
        }
        else if(opt==2){
            cin>>p>>x>>q;
            update(root[p],1,V,q,x);
        }
        else if(opt==3){
            cin>>p>>x>>y;
            cout<
            cin>>p>>k;
            if(sum[root[p]] 
2.3splay&&fhq 
 
#include
#define endl 'n'
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1e5+100;
const int M=1e6+100;
template
class Balanced_Binary_Tree {
private:
    struct Point {
        T value;
        unsigned int count;
        unsigned int size;
        unsigned int daughter[2], mother;
        Point() { size = count = 0, mother = daughter[1] = daughter[0] = 0; }
        Point(T const value) {
            this->value = value,
            size = count = 1, mother = daughter[1] = daughter[0] = 0;
        }
    } tree[N + M + 1];
    unsigned int length, size, root;
    bool inline get_id(unsigned int const x) const {
        return tree[tree[x].mother].daughter[1] == x;
    }
    void const inline upto(unsigned int const x) {
        tree[x].size =
            tree[tree[x].daughter[0]].size + tree[tree[x].daughter[1]].size
            + tree[x].count;
    }
    void const inline connect
        (unsigned int const x, unsigned int const y, bool const id) {
        tree[x].mother = y, tree[y].daughter[id] = x;
    }
    void const inline rotate(unsigned int const x) {
        unsigned int const m(tree[x].mother), g(tree[m].mother);
        bool const id(get_id(x)), mid(get_id(m));
        connect(tree[x].daughter[!id], m, id), upto(m),
        connect(m, x, !id), upto(x), connect(x, g, mid);
    }
    void const inline splay(unsigned int const x, unsigned int root) {
        root = tree[root].mother;
        while (tree[x].mother not_eq root)
            if (tree[tree[x].mother].mother == root) rotate(x);
            else
                if (get_id(x) == get_id(tree[x].mother))
                    rotate(tree[x].mother), rotate(x);
                else
                    rotate(x), rotate(x);
    }
    void const inline Splay(unsigned int const x) {
        splay(x, root), root = x;
    }
public:
    Balanced_Binary_Tree() { size = length = 0; }
    void const inline Insert(T const x) {
        if (not size++) {
            tree[root = ++length] = Point(x), connect(root, 0, 0);
            return;
        }
        for (unsigned int register i(root); ++tree[i].size, true;) {
            if (tree[i].value == x)
                { ++tree[i].count, Splay(i); return; }
            else {
                bool id(tree[i].value < x);
                if (not tree[i].daughter[id]) {
                    tree[++length] = Point(x), connect(length, i , id),
                    Splay(length);
                    return;
                }
                else
                    i = tree[i].daughter[id];
            }
        }
    }
    void const inline Delete(T const x) {
        --size;
        for (
            unsigned int register i(root);
            tree[i].size--;
            i = tree[i].daughter[x > tree[i].value]
        )
            if (tree[i].value == x) {
                if (--tree[i].count) { Splay(i); return; }
                Splay(i);
                if (not tree[i].daughter[0])
                    { connect(root = tree[i].daughter[1], 0, 0); return; }
                if (not tree[i].daughter[1])
                    { connect(root = tree[i].daughter[0], 0, 0); return; }
                unsigned int j(tree[i].daughter[0]);
                while (tree[j].daughter[1]) j = tree[j].daughter[1];
                splay(j, tree[i].daughter[0]);
                connect(tree[i].daughter[1], tree[i].daughter[0], 1),
                upto(tree[i].daughter[0]),
                connect(root = tree[i].daughter[0], 0, 0);
                return;
            }
    }
    unsigned int inline Get_Ranking(T const x) {
        unsigned int r(1);
        for (unsigned int register i(root); i;)
            if (tree[i].value == x)
                { Splay(i); return tree[tree[i].daughter[0]].size + 1; }
            else
                if (tree[i].value < x)
                    r += tree[tree[i].daughter[0]].size + tree[i].count,
                    i = tree[i].daughter[1];
                else
                    i = tree[i].daughter[0];
        return r;
    }
    unsigned int inline Get_Rank(unsigned int const x) {
        unsigned int r(1);
        for (unsigned int register i(root); true;) {
            if (
                r + tree[tree[i].daughter[0]].size <= x
                and x < r + tree[tree[i].daughter[0]].size + tree[i].count
            ) { Splay(i); return tree[i].value; }
            else
                if (x < r + tree[tree[i].daughter[0]].size)
                    i = tree[i].daughter[0];
                else
                    r += tree[tree[i].daughter[0]].size + tree[i].count,
                    i = tree[i].daughter[1];
        }
    }
    T inline Get_Less(T const x) {
        T r; unsigned int register li;
        for (unsigned int register i(root); i;)
            if (tree[i].value >= x) li = i, i = tree[i].daughter[0];
            else r = tree[li = i].value, i = tree[i].daughter[1];
        Splay(li);
        return r;
    }
    T inline Get_Greater(T const x) {
        T r; unsigned int register li;
        for (unsigned int register i(root); i;)
            if (tree[i].value <= x) li = i, i = tree[i].daughter[1];
            else r = tree[li = i].value, i = tree[i].daughter[0];
        Splay(li);
        return r;
    }
};
Balanced_Binary_Tree spl;


int n,m;
int a[N];
int fin;
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        spl.Insert(a[i]);
    }
    int lastans=0;
    for(int i=1;i<=m;i++){
        int opt=read(),v=read();
        v^=lastans;
        if(opt==1){
            spl.Insert(v);
        }else if(opt==2){
            spl.Delete(v);
        }else if(opt==3){
            int tmp=spl.Get_Ranking(v);
            lastans=tmp;
            fin^=lastans;
        }else if(opt==4){
            int tmp=spl.Get_Rank(v);
            lastans=tmp;
            fin^=lastans;
        }else if(opt==5){
            int tmp=spl.Get_Less(v);
            lastans=tmp;
            fin^=lastans;
        }else if(opt==6){
            int tmp=spl.Get_Greater(v);
            lastans=tmp;
            fin^=lastans;
        }
    }
    cout< 
#include
#define maxn 1100010
struct pair{
	int a,b;
	pair(int a_=0,int b_=0) { a=a_; b=b_; }
};
int read(){
    int ans=0; char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
int key[maxn],wei[maxn],size[maxn],son[maxn][2];
int n,m,cnt,ans,seed=1,root,last;
int rand1() { return seed*=19260817; }
inline void pushup(int u)
	{ size[u]=size[son[u][0]]+size[son[u][1]]+1; }
pair split(int u,int k){
	if(!u) return pair(0,0);
	if(key[u]
		pair t=split(son[u][1],k);
		son[u][1]=t.a;
		pushup(u);
		return pair(u,t.b);
	}else{
		pair t=split(son[u][0],k);
		son[u][0]=t.b;
		pushup(u);
		return pair(t.a,u);
	}
}
int merge(int u,int v){
	if(!u||!v) return u+v;
	if(wei[u]
		son[u][1]=merge(son[u][1],v);
		pushup(u);
		return u;
	}else{
		son[v][0]=merge(u,son[v][0]);
		pushup(v);
		return v;
	}
}
void insert(int k){
	key[++cnt]=k; wei[cnt]=rand1(); size[cnt]=1;
	pair t=split(root,k);
	root=merge(merge(t.a,cnt),t.b);
}
void eraser(int k){
	pair x,y;
	x=split(root,k);
	y=split(x.b,k+1);
	y.a=merge(son[y.a][0],son[y.a][1]);
	root=merge(x.a,merge(y.a,y.b));
}
int find1(int k){
	int re;
	pair t=split(root,k);
	re=size[t.a]+1;
	root=merge(t.a,t.b);
	return re;
}
int find2(int k){
	int pos=root;
	while(pos){
		if(k==size[son[pos][0]]+1) return key[pos];
		if(k<=size[son[pos][0]]) pos=son[pos][0];
		else { k-=size[son[pos][0]]+1; pos=son[pos][1]; }
	}
}
int lst(int k) { return find2(find1(k)-1); }
int nxt(int k) { return find2(find1(k+1)); }
int main(){
	n=read(); m=read();
	for(int i=1;i<=n;i++){
		int a=read();
		insert(a);
	}
	for(int i=1;i<=m;i++){
		int o=read(),x; x=read();
		if(o==1) insert(x^last);
		if(o==2) eraser(x^last);
		if(o==3) { last=find1(x^last); ans^=last; }
		if(o==4) { last=find2(x^last); ans^=last; }
		if(o==5) { last=lst(x^last); ans^=last; }
		if(o==6) { last=nxt(x^last); ans^=last; }
	}
	printf("%dn",ans);
	return 0;
}
 
2.4线段树分治 
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int N=6e5;
#define mid ((l+r)>>1)
#define ls node<<1
#define rs node<<1|1
int n,x,y,z,sz[N],fa[N],top;
ll ans;
vectord[N],e[N<<2];
int find(int x){
    while(x^fa[x]){
        x=fa[x];
    }
    return x;
}
void update(int node,int l,int r,int ql,int qr,pii pi){
    if(ql<=l&&r<=qr){
        return e[node].push_back(pi),void();
    }
    if(ql<=mid) update(ls,l,mid,ql,qr,pi);
    if(qr>mid)  update(rs,mid+1,r,ql,qr,pi);
}
void solve(int node,int l,int r){
    vectordl;
    for(auto v:e[node]){
        int p=find(v.first),q=find(v.second);
        if(p==q) continue;
        if(sz[p]>sz[q]) swap(p,q);
        dl.push_back(p),sz[q]+=sz[p],fa[p]=q;
    }
    if(l==r){
        for(auto v:d[l])
        ans+=1ll*sz[find(v.first)]*sz[find(v.second)];
    }
    else{
        solve(node<<1,l,mid),solve(node<<1|1,mid+1,r);
    }
    reverse(dl.begin(),dl.end());
    for(auto v:dl) sz[fa[v]]-=sz[v],fa[v]=v;
}




int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i
        cin>>x>>y>>z;
        d[z].push_back({x,y});
        if(z>1) update(1,1,n,1,z-1,{x,y});
        if(zx,y});
    }
    for(int i=1;i<=n;i++) sz[fa[i]=i]=1;
    solve(1,1,n);
    // cout<<"here"< 
2.5可持久化线段树 
#include
using namespace std;
const int N=2e5+100;
const int LOG=35;
const int V=1e9+10;
int sum[N*LOG],lc[N*LOG],rc[N*LOG],root[N*LOG],cnt;
#define mid ((l+r)>>1)
void pushup(int node){
    sum[node]=sum[lc[node]]+sum[rc[node]];
}
void update(int pre,int &node,int l,int r,int x){
    node=++cnt;
    if(l==r) {sum[node]=sum[pre]+1;return ;}
    lc[node]=lc[pre],rc[node]=rc[pre];
    if(x<=mid) update(lc[pre],lc[node],l,mid,x);
    if(x>mid)  update(rc[pre],rc[node],mid+1,r,x);
    pushup(node);
}
int query(int pre,int now,int l,int r,int k){
    if(l==r) return l;
    int lcsz=sum[lc[now]]-sum[lc[pre]];
    if(k<=lcsz) return query(lc[pre],lc[now],l,mid,k);
    else  return query(rc[pre],rc[now],mid+1,r,k-lcsz);
}
int a[N],n,m;
int main(){
    cin>>n>>m;for(int i=1;i<=n;i++) {
        int now;cin>>now;
        update(root[i-1],root[i],0,V,now);
    }
    for(int i=1;i<=m;i++){
        int l,r,k;cin>>l>>r>>k;
        cout< 
2.6动态开点线段树 
#include
using namespace std;
const int N=5e5+100;
const int LOG=20;
const int V=1e9+10;
int sum[N*LOG],lc[N*LOG],rc[N*LOG];
int root,cnt;
typedef long long ll;
#define mid ((l+r)>>1)
void pushup(int node){
    sum[node]=sum[lc[node]]+sum[rc[node]];
}

void update(int &node,int l,int r,int x){
    if(node==0) node=++cnt;
    if(l==r){sum[node]++;return;}
    if(x<=mid) update(lc[node],l,mid,x);
    if(x>mid) update(rc[node],mid+1,r,x);
    pushup(node);
}
int query(int node,int l,int r,int ql,int qr){
    if((l>=ql&&r<=qr)||node==0) return sum[node];
    int ans=0;
    if(ql<=mid) ans=ans+query(lc[node],l,mid,ql,qr);
    if(qr>=mid+1) ans=ans+query(rc[node],mid+1,r,ql,qr);
    return ans;
}
ll ans;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        int now;cin>>now;
        ans+=query(root,1,V,now+1,V);
        // cout< 
2.7虚树(Static Query on Tree) 
#include
using namespace std;
// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
const int N=8e5+100;
typedef long long ll;
typedef pair pii;
int dfn[N],dep[N],fa[N][25];
int lst[N],t;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
struct EDGE{
    int to,next;
    ll val;
}edge[N<<1],edge1[N<<1];


int n,q,num,top,dfscnt=1;
int stak[N];


int head[N],cnt=1;
void add(int x,int y,int v=0){
    edge[cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].val=v;
    head[x]=cnt++;
}

int head1[N];
int cnt1=1;
void add1(int x,int y,int v=0){
    edge1[cnt1].next=head1[x];
    edge1[cnt1].to=y;
    edge1[cnt1].val=v;
    head1[x]=cnt1++;
}

void dfs(int pos){
    int k;
   for(int j=1;j<=t;j++) fa[pos][j]=fa[fa[pos][j-1]][j-1];
    dfn[pos]=dfscnt++;
    for(int i=head[pos];i;i=edge[i].next){
        int to=edge[i].to;
        if(!dfn[to]){
            dep[to]=dep[pos]+1;
            fa[to][0]=pos;
            dfs(to);
        }
    }
}
int lca(int x,int y){
    if(dep[x]>dep[y]) swap(x,y);
    // cout<=0;i--){
        if(dep[fa[y][i]]>=dep[x])
            y=fa[y][i];
    }

    if(x==y) return x;
    for(int i=t;i>=0;i--){
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i]; 
    }
    return fa[x][0];
}
int ta[N],tb[N],tc[N];
int dp[N];
int ans;
void dfs1(int x){
    for(int i=head1[x];i;i=edge1[i].next){
        int son=edge1[i].to;
        dfs1(son);
        ta[x]=ta[x]|ta[son];
        tb[x]=tb[x]|tb[son];
        if(ta[son]&&tb[son]){
            dp[x]+=dp[son]+edge1[i].val;
        }
    }
    if(tb[x]&&ta[x]) dp[x]++;
    if(tc[x]){
        ans+=dp[x];
        dp[x]=0;
    }
}
void cle(int x){
    for(int i=head1[x];i;i=edge1[i].next){
        int son=edge1[i].to;
        cle(son);
    }
    ta[x]=tb[x]=tc[x]=0;
    head1[x]=0;
    dp[x]=0;
}



int cal(int x){
    
    ans=0;
    dfs1(x);
    cle(1);
    cnt1=1;
    printf("%dn",ans);
    return 0;
}


bool cmp(int x1,int x2){
    return dfn[x1]
    
    int n,q;n=read(),q=read();
    t=(int)(log(n)/log(2))+1;
    cnt=1;
    memset(fa,0,sizeof fa);
    for(int i=1;i<=2*n;i++) dfn[i]=0,dep[i]=0,head[i]=0;
    for(int i=2,r;i<=n;i++) cin>>r,add(r,i);
    dfscnt=1,top=0;
    dep[1]=1;
    dfs(1);
    // cout<
        top=0;
        vectorv;
        int a,b,c;
        a=read(),b=read(),c=read();
        v.push_back(1);
        for(int i=1,tmp;i<=a;i++) tmp=read(),ta[tmp]=1,v.push_back(tmp);
        for(int i=1,tmp;i<=b;i++) tmp=read(),tb[tmp]=1,v.push_back(tmp);
        for(int i=1,tmp;i<=c;i++) tmp=read(),tc[tmp]=1,v.push_back(tmp);
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());int len=v.size();
        for(int i=0;i
            lst[i+1]=v[i];
        }
        sort(lst+1,lst+1+len,cmp);
        stak[top=1]=lst[1];
        for(int i=2;i<=len;i++){
            int now=lst[i];
            int lc=lca(now,stak[top]);
            while(1)
                if(dep[lc]>=dep[stak[top-1]]){
                    if(lc!=stak[top]){
                        add1(lc,stak[top],dep[stak[top]]-dep[lc]-1);
                        if(lc!=stak[top-1])
                            stak[top]=lc;
                        else top--;
                    }
                    break;
                }
                else {
                    add1(stak[top-1],stak[top],dep[stak[top]]-dep[stak[top-1]]-1);
                    top--;
                }
                stak[++top]=now;
        }
        while(--top)
            add1(stak[top],stak[top+1],dep[stak[top+1]]-dep[stak[top]]-1);
            cal(1);
    }

}

int main(){
    int t;t=read();
    while(t--){
        solve();
    }
    
}