[数据结构与算法]【数据结构模板】FHQ-Treap | 01-Trie | 珂朵莉树

• 《由于$Splay$ 码量太大了所以转战 $Treap$ 的美好故事》
  $Treap$ 真香，感觉 $Splay$，替罪羊树和 $WBLT$ 都用 $Treap$ 替代就可以了 （？？？）

FHQ-Treap

• FHQ-Treap | by zhy137036
  又叫无旋 $Treap$
  像 $Treap$ 一样，每个点有一个随机权值，根据随机权值做大根堆 / 小根堆来保证复杂度
  又像 $Splay$ 一样，每次插入 / 删除数字都把树分裂，再合并。
  
  
• 依旧是这道模板题：【模板】普通平衡树（数据加强版）
  代码进行了修改和注释

#include<bits/stdc++.h>
#define ls (son[p][0])
#define rs (son[p][1])
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;
}
const int MAX = 2e6+50;

int key[MAX],wei[MAX],sz[MAX],son[MAX][2];
int cnt,root;

inline void push_up(int p){
    sz[p] = sz[ls] + sz[rs] + 1;
}
// 分成两个树，左边树权值的都 < k， 右边数都 >= k
// 返回值：两个树的根节点
inline pair split(int p,int k){
	if(!p) return pair(0,0);
	if(key[p] < k){
		pair t = split(rs,k);
		rs = t.a;
		push_up(p);
		return pair(p,t.b);
	}else{
		pair t = split(ls,k);
		ls = t.b;
		push_up(p);
		return pair(t.a,p);
	}
}
// 根据随机权值（小根堆），合并两棵树
// 返回合并后的根
inline int merge(int p,int v){
	if(!p || !v) return p | v;
	if(wei[p] < wei[v]){
		rs = merge(rs,v);
		push_up(p);
		return p;
	}else{
		son[v][0] = merge(p,son[v][0]);
		push_up(v);
		return v;
	}
}
// 新增一个单节点的树 z ，分裂树成 x,y，合并 x,y,z
inline void insert(int k){
	key[++cnt] = k; wei[cnt] = rand(); sz[cnt] = 1;
	pair t = split(root,k);
	root = merge(merge(t.a,cnt),t.b);
}
// 分裂树成 x,y,z ,x 权值 < k ，y 权值 = k，z 权值 > k
// 然后合并 y 的子树 ，相当于删去了根
inline void erase(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));
}
// 查询 k 的排名，分裂获得左子树大小 + 1
inline int get_rk_from_node(int k){
	int res;
	pair t = split(root,k);
	res = sz[t.a] + 1;
	root = merge(t.a,t.b);
	return res;
}
// 查询排名 k 的结点
inline int get_node_by_rk(int k){
	int p = root;
	while(p){
		if(k == sz[ls]+1) return key[p];
		if(k <= sz[ls]) p = ls;
		else { k -= sz[ls] + 1; p = rs; }
	}
}
// 找前驱 后继
int lst(int k) { return get_node_by_rk(get_rk_from_node(k)-1); }
int nxt(int k) { return get_node_by_rk(get_rk_from_node(k+1)); }
int main(){
    int n,m,last = 0,ans = 0;
	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) erase(x^last);
		if(o==3) { last=get_rk_from_node(x^last); ans^=last; }
		if(o==4) { last=get_node_by_rk(x^last); ans^=last; }
		if(o==5) { last=lst(x^last); ans^=last; }
		if(o==6) { last=nxt(x^last); ans^=last; }
	}
	printf("%d\n",ans);
	return 0;
}

01-Trie

• 原来 $01?Trie$ 也可以做这些插入删除求排名前驱后继的任务
  而且代码确实非常好调，但是内存会变成 $O(n\log n)$
  【模板】普通平衡树
  这题有负数，直接增加一个 $NUM=1e7$，让数都是非负整数，然后去插入

#include <cstdio>
#include <algorithm>
const int maxlog = 25;
const int MAXN = 100010;
using namespace std;

namespace trie{
	int id = 2;
	int ch[MAXN * maxlog][2];
	int sz[MAXN * maxlog];
	int newnode(){
		ch[id][0] = ch[id][1] = sz[id] = 0;
		return id++;
	}				
	void ins(int x,int d){
		int u = 1;
		for(int i = maxlog - 1;i >= 0;i--){
			int v = (x >> i) & 1;
			if(!ch[u][v]) ch[u][v] = newnode();
			u = ch[u][v];
			sz[u] += d;
		}
	}
	int kth(int k){
		int u = 1;
		int x = 0;
		for(int i = maxlog - 1;i >= 0;i--){
			if(sz[ch[u][0]] >= k){
				u = ch[u][0];
			}
			else{
				x |= (1 << i);
				k -= sz[ch[u][0]];
				u = ch[u][1];
			}
		}
		return x;
	}
	int nlt(int x){
		int ans = 0;
		int u = 1;
		for(int i = maxlog - 1;i >= 0;i--){
			if((x >> i) & 1){
				ans += sz[ch[u][0]];
				u = ch[u][1];
			}
			else{
				u = ch[u][0];
			}
		}
		return ans;
	}	
	void clear(){
		ch[1][0] = ch[1][1] = 0;
		id = 2;
	} 
	int pre(int x){
		return kth(nlt(x));
	}
	int next(int x){
		return kth(nlt(x+1)+1);
	}
} 

const int num = 10000000; 
int main(){
	 int n;
	 scanf("%d",&n);
	 for(int i = 0;i < n;i++){
	 	int ord,t;
	 	scanf("%d%d",&ord,&t);
		switch(ord){
			case 1:trie::ins(t + num,1);break;
			case 2:trie::ins(t + num,-1);break;
			case 3:printf("%d\n",trie::nlt(t + num) + 1);break;
			case 4:printf("%d\n",trie::kth(t) - num);break;
			case 5:printf("%d\n",trie::pre(t + num) - num);break;
			case 6:printf("%d\n",trie::next(t + num) - num);break;
		}
	}
	return 0;
} 

珂朵莉树 | 老司机树（ODT）

• 【博客】我的算法不可能这么简单—珂朵莉树 | Eloik
  对于数据随机 且有 区间赋值的操作，且一般的数据结构实现不了的话，不妨尝试珂朵莉树
  【题目】Willem, Chtholly and Seniorious | CF896C
  
  这题，注意到最后一种操作，一般的数据结构都不能做，莫队会 $T$
  珂朵莉树的核心操作就是 $assign$ ，就是把连续权值相同的点收缩成一个点
  因为数据随机，所以 $set$ 里面的点的个数是 $O(\log n)$ 级别的，所以复杂度有保证
  其他的操作都是暴力操作了。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct node{
    int l,r;
    mutable ll val;
    bool operator<(const node &a)const {return l<a.l;}
    node(int L,int R,ll Val):l(L),r(R),val(Val){}
    node(int L):l(L){}
};

set<node> s;
using  si = set<node>::iterator;

si split(int pos){
    si it = s.lower_bound(node(pos));
    if(it != s.end() && it->l==pos) return it;
    --it;
    int l=it->l,r=it->r;
    ll val = it->val;
    s.erase(it);
    s.insert(node(l,pos-1,val));
    return s.insert(node(pos,r,val)).first;
}

void assign(int l,int r,ll val){
    si itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

void add(int l,int r,ll val){
    si itr=split(r+1),itl=split(l);
    for(si it=itl;it!=itr;++it)
        it->val += val;
}

ll kth(int l,int r,int k){
    si itr=split(r+1),itl=split(l);
    vector<pair<ll,int>> v;
    v.clear();
    for(si it=itl;it!=itr;++it)
        v.push_back(pair<ll,int>(it->val,it->r-it->l+1));
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();++i){
        k -= v[i].second;
        if(k<=0) return v[i].first;
    }
    return -1;
}

ll qpow(ll a,int b,ll m){
    ll t = 1ll;
    a %= m;
    while(b){
        if(b&1) t= (t*a)%m;
        a = (a*a)%m;
        b>>=1;
    }
    return t;
}

ll query(int l,int r,int x,int y){
    si itr=split(r+1),itl=split(l);
    ll res(0);
    for(si it=itl;it!=itr;++it)
        res=(res+(it->r-it->l+1)*qpow(it->val,x,y))%y;
    return res;
}

int n, m, vmax;
ll seed;
int rnd() {
    int ret = (int)seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}
int main() {
    scanf("%d%d%lld%d", &n, &m, &seed, &vmax);
    for (int i = 1; i <= n; ++i) {
        int a = rnd() % vmax + 1;
        s.insert(node(i, i, (ll)a));
    }
    s.insert(node(n + 1, n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        int l, r, x, y;
        int op = rnd() % 4 + 1;
        l = rnd() % n + 1, r = rnd() % n + 1;
        if (l > r) swap(l, r);
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmax + 1;
        if (op == 4) y = rnd() % vmax + 1;
        if (op == 1) add(l, r, (ll)x);
        else if (op == 2) assign(l, r, (ll)x);
        else if (op == 3) printf("%lld\n", kth(l, r, x));
        else if (op == 4) printf("%lld\n", query(l, r, x, (ll)y));
    }
    return 0;
}