《算法竞赛进阶指南》 0x45 ~ 0x48 代码 + 杂谈

点分治

///淀粉质
链接 ： https://blog.csdn.net/qq_40831340/article/details/90234372

平衡树

theap 模板

// treap模板题
// 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
//插入x数
//删除x数(若有多个相同的数，因只删除一个)
//查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
//查询排名为x的数
//求x的前驱(前驱定义为小于x，且最大的数)
//求x的后继(后继定义为大于x，且最小的数)
const int maxn = 100000+5;
const int INF = 0x3f3f3f3f;
int siz[maxn];
int s[maxn][3];
int w[maxn],pos[maxn];
int tot;

void up(int i) {siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;}

void spin(int &i,int p) {
	int t=s[i][p];
	s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}

void ins(int x,int &i) {
	if(!i) {
		i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();
		return;
	}
	siz[i]++;
	if(x<=w[i]) {
		ins(x,s[i][0]);
		if(pos[s[i][0]]<pos[i])spin(i,0);
	} else {
		ins(x,s[i][1]);
		if(pos[s[i][1]]<pos[i])spin(i,1);
	}
}

void del(int x,int &i) {
	if(w[i]==x) {
		if(s[i][0]*s[i][1]==0) {
			i=s[i][0]+s[i][1];
			return;
		}
		if(pos[s[i][0]]>pos[s[i][1]]) {
			spin(i,1);
			del(x,s[i][0]);
		} else {
			spin(i,0);
			del(x,s[i][1]);
		}
	} else if(w[i]>x)del(x,s[i][0]);
	else del(x,s[i][1]);
	up(i);
}

int find(int x,int i) {
	if(!i)return 1;
	if(w[i]>=x)return find(x,s[i][0]);
	return find(x,s[i][1])+siz[s[i][0]]+1;
}

int ask(int x,int i) {
	if(siz[s[i][0]]==x-1)return w[i];
	if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
	return ask(x-siz[s[i][0]]-1,s[i][1]);
}

int pre(int x,int i) {
	if(!i)return -INF;
	if(w[i]<x)return max(w[i],pre(x,s[i][1]));
	else return pre(x,s[i][0]);
}
int nxt(int x,int i) {
	if(!i)return INF;
	if(w[i]>x)return min(w[i],nxt(x,s[i][0]));
	else return nxt(x,s[i][1]);
}

signed main() {
	cin>>n;
	int root=0;
	while(n--) {
		int cmd;
		cin>>cmd;
		if(cmd==1) cin>>m,ins(m,root);
		if(cmd==2) cin>>m,del(m,root);
		if(cmd==3) cin>>m,cout<<find(m,root)<<endl;
		if(cmd==4) cin>>m,cout<<ask(m,root)<<endl;
		if(cmd==5) cin>>m,cout<<pre(m,root)<<endl;
		cmd==6;
		cin>>m,cout<<nxt(m,root)<<endl;
	}
	return 0;
}

可持续化
链接 https://blog.csdn.net/qq_40831340/article/details/90733094

#include <iostream>
#include <cstdio>
using namespace std;
const signed maxn =  600000+10;
signed trie[maxn * 24][2], latest[maxn * 24];
signed s[maxn], root[maxn], n, m, tot;
inline void ins(int i, int k, int p, int q){
	if(k < 0) {
		latest[q] = i;
		return ;
	}
	int c = s[i] >> k & 1;
	if(p) trie[q][c ^ 1] = trie[p][c ^ 1];
	trie[q][c] = ++tot;
	ins(i, k-1, trie[p][c], trie[q][c]);
	latest[q] = max (latest[trie[q][0]], latest[trie[q][1]]); 
}
signed ask(int now, int val, int k, int limit) {
	if(k < 0) return s[latest[now]] ^ val;
	int c = val >> k & 1;
	if(latest[trie[now][c ^ 1]] >= limit)
		return ask(trie[now][c ^ 1], val, k - 1, limit);
	else 
		return ask(trie[now][c], val, k - 1, limit);
} 
signed main(){
	scanf("%d %d",&n,&m);
	latest[0] = -1;
	root[0] = ++tot;
	ins(0, 23, 0, root[0]);
	int x;
	for(int i = 1; i <= n ; i ++ ) {
		scanf("%d",&x);
		s[i] = x ^ s[i - 1];
		root[i] = ++ tot;
		ins(i, 23, root[i - 1], root[i]);
	}
	for(int i = 1; i <= m; i ++) {
		int l, r;
		char cmd[2];
		scanf("%s",cmd);
		if(cmd[0] == 'A') {
			scanf("%d",&x);
			root[++n] = ++ tot;
			s[n] = s[n - 1] ^ x;
			ins(n, 23, root[n - 1], root[n]);
		}else{
			scanf("%d %d %d",&l, &r,&x);
			cout << ask(root[r - 1], x ^ s[n], 23, l - 1) << endl;
		}
	}
	return 0;
}