标签：return int 有关 tr 数据结构 root void 模板 size
FHQ-Treap
#include <bits/stdc++.h>
#define ls tr[u].l
#define rs tr[u].r
using namespace std;
const int N = 3e5+10;
struct Node
{
int l,r;
int key,v;
int size;
}tr[N];
int root,idx;
int n,m;
void pushup(int u)
{
tr[u].size = tr[ls].size + tr[rs].size + 1;
}
int add(int v)
{
tr[++idx].key = rand();
tr[idx].v = v;
tr[idx].size = 1;
return idx;
}
void split(int u,int val,int &x,int &y)
{
if(!u) return x = y = 0,void();
if(tr[u].v <= val)
{
x = u;
split(rs,val,rs,y);
}
else
{
y = u;
split(ls,val,x,ls);
}
pushup(u);
}
int merge(int x,int y)
{
if(!x || !y) return x + y;
if(tr[x].key > tr[y].key)
{
tr[x].r = merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
tr[y].l = merge(x,tr[y].l);
pushup(y);
return y;
}
}
void insert(int v)
{
int x,y;
split(root,v,x,y);
root = merge(x,merge(add(v),y));
}
void remove(int v)
{
int x,y,z;
split(root,v,x,z);
split(x,v-1,x,y);
y = merge(tr[y].l,tr[y].r);
root = merge(merge(x,y),z);
}
int get_rank_by_val(int v)
{
int x,y;
split(root,v-1,x,y);
int res = tr[x].size + 1;
root = merge(x,y);
return res;
}
int get_val_by_rank(int k)
{
int u = root;
while(u)
{
if(tr[ls].size + 1 == k) return tr[u].v;
else if(tr[ls].size >= k) u = ls;
else k-=tr[ls].size + 1,u = rs;
}
return -1;
}
int get_prev(int v)
{
int x,y;
split(root,v-1,x,y);
int u = x;
while(rs) u = rs;
int res = tr[u].v;
root = merge(x,y);
return res;
}
int get_next(int v)
{
int x,y;
split(root,v,x,y);
int u = y;
while(ls) u = ls;
int res = tr[u].v;
root = merge(x,y);
return res;
}
int main()
{
scanf("%d", &n);
while (n -- )
{
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1) insert(x);
else if (opt == 2) remove(x);
else if (opt == 3) printf("%d\n", get_rank_by_val(x));
else if (opt == 4) printf("%d\n", get_val_by_rank(x));
else if (opt == 5) printf("%d\n", get_prev(x));
else printf("%d\n", get_next(x));
}
return 0;
}
Splay
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct Node
{
int s[2],p,v;
int size,flag;
void init(int _p,int _v)
{
p = _p;
v = _v;
size = 1;
}
}tr[N];
int root,idx;
int n,m;
void pushup(int x)
{
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void pushdown(int x)
{
if(tr[x].flag)
{
swap(tr[x].s[0],tr[x].s[1]);
tr[tr[x].s[0]].flag ^= 1;
tr[tr[x].s[1]].flag ^= 1;
tr[x].flag = 0;
}
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k^1], tr[tr[x].s[k^1]].p = y;
tr[x].s[k^1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z!=k)
{
if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
void insert(int v)
{
int u = root,p = 0;
while(u) p = u,u = tr[u].s[v > tr[u].v];
u = ++idx;
if(p) tr[p].s[v > tr[p].v] = u;
tr[u].init(p,v);
splay(u,0);
}
int get_k(int k)
{
int u = root;
while(true)
{
pushdown(u);
if(tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].size + 1 == k) return u;
else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
pushup(u);
}
return -1;
}
void output(int u)
{
pushdown(u);
if(tr[u].s[0]) output(tr[u].s[0]);
if(tr[u].v >= 1 && tr[u].v <= n) printf("%d ",tr[u].v);
if(tr[u].s[1]) output(tr[u].s[1]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 0;i<=n+1;i++) insert(i);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
l = get_k(l),r = get_k(r+2);
splay(l,0),splay(r,l);
tr[tr[r].s[0]].flag ^= 1;
}
output(root);
return 0;
}
可持久化线段树（主席树）
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct Node
{
int l,r;
int cnt;
}tr[4*N + 17*N];
int root[N],idx,a[N];
int n,m;
vector<int> v;
int find(int x)
{
return lower_bound(v.begin(),v.end(),x) - v.begin();
}
int build(int l,int r)
{
int p = ++idx;
if(l==r) return p;
int mid = l + r >> 1;
tr[p].l = build(l,mid),tr[p].r = build(mid+1,r);
return p;
}
int insert(int p,int l,int r,int x)
{
int q = ++idx;
tr[q] = tr[p];
if(l==r)
{
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
if(x<=mid) tr[q].l = insert(tr[p].l,l,mid,x);
else tr[q].r = insert(tr[p].r,mid+1,r,x);
tr[q].cnt= tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int q,int p,int l,int r,int k)
{
if(l==r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if(cnt>=k) return query(tr[q].l,tr[p].l,l,mid,k);
else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
root[0] = build(0,v.size()-1);
for(int i = 1;i<=n;i++)
{
root[i] = insert(root[i-1],0,v.size()-1,find(a[i]));
}
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",v[query(root[r],root[l-1],0,v.size()-1,k)]);
}
return 0;
}
AC自动机
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10,M = 2e6+10;
int tr[N][26],id[N],ne[N],tot,Size[N],cnt[N];
int q[N];
char str[M];
int h[N],e[N],Ne[N],n,idx;
void add(int a,int b)
{
e[idx] = b,Ne[idx] = h[a],h[a] = idx++;
}
void insert(int x)
{
int p = 0;
for(int i = 0;str[i];i++)
{
int t = str[i] - 'a';
if(!tr[p][t]) tr[p][t] = ++tot;
p = tr[p][t];
}
id[x] = p;
}
void build()
{
int tt = -1,hh = 0;
for(int i = 0;i<26;i++) if(tr[0][i]) q[++tt] = tr[0][i];
while(tt>=hh)
{
int t = q[hh++];
for(int i = 0;i<26;i++)
{
int &p = tr[t][i];
if(!p) p = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[++tt] = p;
}
}
}
}
void dfs(int u)
{
for(int i = h[u];~i;i=Ne[i])
{
int j = e[i];
dfs(j);
Size[u] += Size[j];
}
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d",&n);
for(int i = 0;i<n;i++) scanf("%s",str),insert(i);
build();
scanf("%s",str);
for(int i = 0,j = 0;str[i];i++)
{
int t = str[i] - 'a';
j = tr[j][t];
Size[j]++;
}
for(int i = 1;i<=tot;i++) add(ne[i],i);
dfs(0);
for(int i = 0;i<n;i++) printf("%d\n",Size[id[i]]);
return 0;
}
标签：return,
int,
有关,
tr,
数据结构,
root,
void,
模板,
size
From： https://www.cnblogs.com/howardsblog/p/18009027