主席树模板

应用场景

静态: 查询区间第K大

动态: 带修改的查询区间第K大

静态

P3834【模板】可持久化线段树 1(主席树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=a;i>=n;i--)
#define ll long long
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 2e5+20;
int a[N],b[N],T[N],L[N*20],R[N*20],sum[N*20];
int tot = 0,n,q,x,y,z,m;

int Build(int l,int r)
{
int rt = ++tot;
int mid = (l+r)>>1;
if(l < r)
{
L[rt] = Build(l,mid);
R[rt] = Build(mid+1,r);
}
return rt;
}

int update(int pre,int l,int r,int x)
{
int rt = ++tot;
int mid = (l+r)>>1;
L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;
if(l < r)
{
if(x <= mid)
L[rt] = update(L[pre],l,mid,x);
else
R[rt] = update(R[pre],mid+1,r,x);
}
return rt;
}

int query(int u,int v,int l,int r,int k)
{
if(l == r)
return l;
int mid = (l+r)>>1;
int x = sum[L[v]]-sum[L[u]];
if(x >= k)
return query(L[u],L[v],l,mid,k);
else
return query(R[u],R[v],mid+1,r,k-x);
}

int main()
{
tot = 0;
clr(T,0); clr(sum,0); clr(L,0); clr(R,0); clr(a,0); clr(b,0);
scanf("%d %d",&n,&q);
rep(i,1,n)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(b+1,b+1+n);
m = unique(b+1,b+1+n)-b-1;
T[0] = Build(1,m);
rep(i,1,n)
{
a[i] = lower_bound(b+1,b+1+m,a[i])-b;
T[i] = update(T[i-1],1,m,a[i]);
}
rep(i,1,q)
{
scanf("%d %d %d",&x,&y,&z);
int p = query(T[x-1],T[y],1,m,z);
printf("%d\n",b[p]);
}
return 0;
}

动态

P2617 Dynamic Rankings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define ll long long
#define lowbit(a) a&(-a)
const int N = 200050;

int cnt,siz,dot,idx;
// 内存分配的下标,不同数值点的个数,总共的点数,修改操作的下标
int root[N],cpy[N],data[N];
// 静态主席树的根节点,离散化后的数据,原始数据
int vir[N],use[N];
// 树状数组的节点,计算前缀和时向前走的节点

// 因为主席树必须离线,所以将指令存下来
struct order
{
bool typ; // biaoji查询还是修改
int from,to,k;
}command[N];

struct node
{int son[2],sum;}tree[N*250];
// 内存一定要开的足够大,因为在这里静态主席树和树状数组共用这个数组内的点

int build(int l,int r) // 建立空树 类似线段树
{
int now = cnt++;
tree[cnt].sum = 0;
if(l != r)
{
int mid = (l+r)>>1;
tree[now].son[0] = build(l,mid);
tree[now].son[1] = build(mid+1,r);
}
return now;
}

int updata(int last,int pos,int val) // 更新虚拟节点或者插入静态主席树的函数
// 为了方便删除,传入val代表修改的量
{
int now = cnt++,tmp = now,mid;
int l = 0,r = siz-1; // 保存的是离散化后的对应的值的编号
tree[now].sum = tree[last].sum+val;
while(l < r)
{
mid = (l+r)>>1;
if(pos <= mid) // 待插入节点在左子树
{
tree[now].son[1] = tree[last].son[1];
// 那么当前节点的右子树节点和之前的那棵权值线段树共用节点
tree[now].son[0] = cnt++; // 向左新开一个节点
now = tree[now].son[0];
last = tree[last].son[0];
r = mid;
}
else // 待插入节点在右子树
{
tree[now].son[0] = tree[last].son[0];
tree[now].son[1] = cnt++;
now = tree[now].son[1];
last = tree[last].son[1];
l = mid+1;
}
tree[now].sum = tree[last].sum+val;
}
return tmp;
}

void add(int now,int pos,int val)
{
while(now <= dot)
{
vir[now] = updata(vir[now],pos,val);
now += lowbit(now);
}
}

int getsum(int now) // 查询当前点更改值的左子树的大小
{
int ret = 0;
while(now > 0)
{
ret += tree[tree[use[now]].son[0]].sum;
now -= lowbit(now);
}
return ret;
}

int query(int l,int r,int kth)
{
int left_root = root[l-1]; // 静态主席树的两个相减的根节点
int right_root = root[r];
int lef = 0,rig = siz-1; // 查询时左右范围
for(int i = l-1;i;i -= lowbit(i)) use[i] = vir[i];
// 初始化更改值的路径
for(int i = r;i;i -= lowbit(i)) use[i] = vir[i];
while(lef < rig)
{
int mid = (lef+rig)>>1;
int now_sum = getsum(r)-getsum(l-1)+tree[tree[right_root].son[0]].sum-tree[tree[left_root].son[0]].sum;
// 查询当前点的左儿子是否满足达到了k个
// 在静态主席树和树状数组上一起算
if(now_sum >= kth) // 达到了
{
rig = mid;
for(int i = l-1;i;i -= lowbit(i)) use[i] = tree[use[i]].son[0];
// 将查询范围缩小至左子树内
for(int i = r;i;i -= lowbit(i)) use[i] = tree[use[i]].son[0];
left_root = tree[left_root].son[0]; // 同时静态主席树也要如此
right_root = tree[right_root].son[0];
}
else // 没达到就在右子树范围内继续查找
{
lef = mid+1;
kth -= now_sum; // 因为有了左子树的一部分点,所以要减去
for(int i = l-1;i;i -= lowbit(i)) use[i] = tree[use[i]].son[1];
for(int i = r;i;i -= lowbit(i)) use[i] = tree[use[i]].son[1];
left_root = tree[left_root].son[1];
right_root = tree[right_root].son[1];
}
}
return lef; // 返回是第几个离散出来的数据
}

int id(int now)
{
return lower_bound(cpy,cpy+siz,now)-cpy;
}

int main()
{
int num;
scanf("%d %d",&dot,&num);
idx = dot;
for(int i = 1;i <= dot;i++)
{
scanf("%d",&data[i]);
cpy[i-1] = data[i]; // cpy从0开始存方便unique和sort
}
char c[10];
for(int i = 1;i <= num;i++)
{
scanf("%s",c);
if(c[0] == 'Q')
{
command[i].typ = false;
scanf("%d %d %d",&command[i].from,&command[i].to,&command[i].k);
}
else
{
command[i].typ = true;
scanf("%d %d",&command[i].from,&command[i].k);
cpy[idx++] = command[i].k; // 如果是修改的话存入cpy中
}
}
sort(cpy,cpy+idx);
siz = unique(cpy,cpy+idx)-cpy;
root[0] = build(0,siz-1); // 建立空静态主席树
for(int i = 1;i <= dot;i++)
root[i] = updata(root[i-1],id(data[i]),1); // 建立满的静态主席树
for(int i = 1;i <= dot;++i)
vir[i] = root[0]; // 初始化树状数组
for(int i = 1;i <= num;i++) // 处理指令
{
if(!command[i].typ)
printf("%d\n",cpy[query(command[i].from,command[i].to,command[i].k)]);
else
{
add(command[i].from,id(data[command[i].from]),-1);
add(command[i].from,id(command[i].k),1);
data[command[i].from] = command[i].k; // 将原数据修改至新数据
}
}
return 0;
}