重温主席树（附7题）
主席树的话，其实理解比那些啥AC自动机，后缀数组的啥好理解得多。
这几天复习了下主席树，顺便趁热打铁刷了几题。
1. POJ2104
主席树入门题，不多说。
# include <vector>
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2000010;
const int N = 100010;
int n, a[N], m;
int ch[M][2], sz=0, rt[M], s[M];
vector<int> ps;
int fps[N], mx;
inline void add(int &root, int oldrt, int l, int r, int t) {
root=++sz;
ch[root][0] = ch[root][1] = 0;
s[root]=s[oldrt]+1;
if(l == r) return;
int mid=l+r>>1;
if(t>mid) add(ch[root][1], ch[oldrt][1], mid+1, r, t), ch[root][0] = ch[oldrt][0];
else add(ch[root][0], ch[oldrt][0], l, mid, t), ch[root][1] = ch[oldrt][1];
}
inline int query(int rtl, int rtr, int l, int r, int k) {
if(l == r) return l;
int t = s[ch[rtr][0]] - s[ch[rtl][0]];
int mid = l+r>>1;
if(k <= t) return query(ch[rtl][0], ch[rtr][0], l, mid, k);
else return query(ch[rtl][1], ch[rtr][1], mid+1, r, k-t);
}
int main() {
while(~scanf("%d%d", &n, &m)) {
ps.clear(); sz=0;
memset(ch, 0, sizeof(ch));
memset(rt, 0, sizeof(rt));
memset(s, 0, sizeof(s));
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
ps.push_back(a[i]);
}
sort(ps.begin(), ps.end());
vector<int>::iterator it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
mx = -1;
for (int i=1; i<=n; ++i) {
int t = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
fps[t] = a[i];
a[i] = t;
mx = max(mx, t);
}
for (int i=1; i<=n; ++i)
add(rt[i], rt[i-1], 1, mx, a[i]);
while(m--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", fps[query(rt[l-1], rt[r], 1, mx, k)]);
}
}
return 0;
}
2. HDU2665
也差不多是裸题
# include <vector>
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2000010;
const int N = 100010;
int n, a[N], m;
int ch[M][2], sz=0, rt[N], s[M];
vector<int> ps;
vector<int>::iterator it;
int fps[N], mx;
inline void add(int &root, int oldrt, int l, int r, int t) {
root=++sz;
ch[root][0] = ch[root][1] = 0;
s[root]=s[oldrt]+1;
if(l == r) return;
int mid=l+r>>1;
if(t>mid) add(ch[root][1], ch[oldrt][1], mid+1, r, t), ch[root][0] = ch[oldrt][0];
else add(ch[root][0], ch[oldrt][0], l, mid, t), ch[root][1] = ch[oldrt][1];
}
inline int query(int rtl, int rtr, int l, int r, int k) {
if(l == r) return l;
int t = s[ch[rtr][0]] - s[ch[rtl][0]];
int mid = l+r>>1;
if(k <= t) return query(ch[rtl][0], ch[rtr][0], l, mid, k);
else return query(ch[rtl][1], ch[rtr][1], mid+1, r, k-t);
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
ps.clear(); sz=0;
memset(ch, 0, sizeof(ch));
memset(rt, 0, sizeof(rt));
memset(s, 0, sizeof(s));
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
ps.push_back(a[i]);
}
sort(ps.begin(), ps.end());
it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
mx = -1;
for (int i=1; i<=n; ++i) {
int t = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
fps[t] = a[i];
a[i] = t;
mx = max(mx, t);
}
for (int i=1; i<=n; ++i)
add(rt[i], rt[i-1], 1, mx, a[i]);
while(m--) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", fps[query(rt[l-1], rt[r], 1, mx, k)]);
}
}
return 0;
}
3. BZOJ 2809
DFS序+主席树维护即可。
# include <vector>
# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5000010, N = 100010;
int n, m, master;
int c[N], L[N], tc[N], fys[N];
vector<int> ps;
# define next NEXT
int head[N], next[N<<1], to[N<<1], tot=0;
inline void add(int u, int v) {
++tot;
next[tot]=head[u];
head[u]=tot;
to[tot]=v;
}
inline void adde(int u, int v) {
add(u, v); add(v, u);
}
int beg[N], end[N], DFN=0, dfn[N];
inline void dfs(int x, int fa) {
beg[x] = ++DFN;
dfn[DFN] = x;
for (int i=head[x]; i; i=next[i]) {
if(to[i] == fa) continue;
dfs(to[i], x);
}
end[x] = DFN;
}
int rt[N], ch[M][2], sz=0;
ll s[M], s2[M];
inline void insert(int &root, int oldrt, int l, int r, int t, ll del) {
root=++sz;
ch[root][0] = ch[root][1] = 0;
if(l == r) {
s[root] = s[oldrt] + del;
s2[root] = s2[oldrt] + 1;
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s1 = %lld, s2 = %lld\n", root, l, r, ch[root][0], ch[root][1], s[root], s2[root]);
return ;
}
int mid = l+r>>1;
if(t<=mid) ch[root][1] = ch[oldrt][1], insert(ch[root][0], ch[oldrt][0], l, mid, t, del);
else ch[root][0] = ch[oldrt][0], insert(ch[root][1], ch[oldrt][1], mid+1, r, t, del);
s[root] = s[ch[root][0]] + s[ch[root][1]];
s2[root] = s2[ch[root][0]] + s2[ch[root][1]];
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s1 = %lld, s2 = %lld\n", root, l, r, ch[root][0], ch[root][1], s[root], s2[root]);
}
inline ll query(int rtl, int rtr, int l, int r, int k) {
// printf("%d %d %d %d %d\n", rtl, rtr, l, r, k);
if(k<l) return 0;
if(s[rtr]-s[rtl] <= k) return s2[rtr]-s2[rtl];
if(l == r) return min(s2[rtr]-s2[rtl], (ll)k/fys[l]);
int mid=l+r>>1;
if(s[ch[rtr][0]]-s[ch[rtl][0]] <= k)
return s2[ch[rtr][0]] - s2[ch[rtl][0]] + query(ch[rtl][1], ch[rtr][1], mid+1, r, k-s[ch[rtr][0]]+s[ch[rtl][0]]);
else return query(ch[rtl][0], ch[rtr][0], l, mid, k);
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1, t; i<=n; ++i) {
scanf("%d%d%d", &t, &c[i], &L[i]);
ps.push_back(c[i]);
if(t == 0) master = i;
adde(i, t);
}
sort(ps.begin(), ps.end());
vector<int>::iterator it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
int mx = -1;
for (int i=1; i<=n; ++i) {
tc[i] = lower_bound(ps.begin(), ps.end(), c[i]) - ps.begin() + 1;
mx = max(mx, tc[i]);
fys[tc[i]] = c[i];
}
dfs(master, 0);
for (int i=1; i<=n; ++i)
insert(rt[i], rt[i-1], 1, mx, tc[dfn[i]], c[dfn[i]]);
ll ans = 0;
for (int i=1; i<=n; ++i) {
// printf("=====i=%d=====\n", i);
// printf("begin %d end %d\n", beg[i], end[i]);
// printf("%d %lld\n", L[i], query(rt[beg[i]-1], rt[end[i]], 1, mx, m));
ll cur = (ll)L[i] * query(rt[beg[i]-1], rt[end[i]], 1, mx, m);
ans = max(ans, cur);
}
printf("%lld\n", ans);
return 0;
}
4. BZOJ 1803
DFS序+主席树
题目有错？应该是第k小？
# include <vector>
# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 100010;
const int M = 2000010;
int n, m, a[N], fys[N];
vector<int> ps;
int ch[M][2], s[M], sz, rt[N];
# define next NEXT
int head[N], next[N<<1], to[N<<1], tot;
inline void add(int u, int v) {
++tot; next[tot]=head[u];
head[u]=tot; to[tot]=v;
}
inline void adde(int u, int v) {
add(u, v);
add(v, u);
}
int beg[N], end[N], DFN=0, dfn[N];
inline void dfs(int x, int fa=0) {
beg[x] = ++DFN;
dfn[DFN] = x;
for (int i=head[x]; i; i=next[i]) {
if(to[i] == fa) continue;
dfs(to[i], x);
}
end[x] = DFN;
}
inline void insert(int &root, int oldrt, int l, int r, int x) {
root=++sz;
ch[root][0]=ch[root][1]=0;
s[root]=s[oldrt]+1;
if(l==r) {
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s = %d\n", root, l, r, ch[root][0], ch[root][1], s[root]);
return;
}
int mid=l+r>>1;
if(x<=mid) insert(ch[root][0], ch[oldrt][0], l, mid, x), ch[root][1] = ch[oldrt][1];
else insert(ch[root][1], ch[oldrt][1], mid+1, r, x), ch[root][0] = ch[oldrt][0];
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s = %d\n", root, l, r, ch[root][0], ch[root][1], s[root]);
}
inline int query(int rtl, int rtr, int l, int r, int k) {
if(l == r) return l;
int sl = s[ch[rtr][0]] - s[ch[rtl][0]];
int mid = l+r>>1;
if(sl>=k) return query(ch[rtl][0], ch[rtr][0], l, mid, k);
else return query(ch[rtl][1], ch[rtr][1], mid+1, r, k-sl);
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
ps.push_back(a[i]);
}
sort(ps.begin(), ps.end());
vector<int>::iterator it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
int mx=-1;
for (int i=1; i<=n; ++i) {
int t = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
fys[t] = i;
a[i] = t;
mx = max(mx, t);
}
for (int i=1, u, v; i<n; ++i) {
scanf("%d%d", &u, &v);
adde(u, v);
}
dfs(1);
// for (int i=1; i<=n; ++i) printf("%d ", dfn[i]);
// puts("");
for (int i=1; i<=n; ++i) insert(rt[i], rt[i-1], 1, mx, a[dfn[i]]);
scanf("%d", &m);
while(m--) {
int x, k;
scanf("%d%d", &x, &k);
printf("%d\n", fys[query(rt[beg[x]-1], rt[end[x]], 1, mx, k)]);
}
return 0;
}
5. bzoj3932
拆分事件然后（特殊的主席树）来统计。
（特殊在不要减l，具体见代码）
# include <vector>
# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 300010, M = 4000010;
int m, n;
vector<int> ps;
int fys[N];
struct oper {int t, p, flg;} o[N];
int on = 0;
inline int cmp(oper a, oper b) {
return a.t < b.t;
}
int rt[N], ch[M][2];
int rte[N], rtn;
int s2[M], sz=0;
ll s[M];
inline void insert(int &root, int oldrt, int l, int r, int pos, ll x, int x2) {
root=++sz;
ch[root][0] = ch[root][1] = 0;
s[root] = s[oldrt]+x;
s2[root] = s2[oldrt]+x2;
if(l == r) {
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s1 = %lld, s2 = %d\n", root, l, r, ch[root][0], ch[root][1], s[root], s2[root]);
return;
}
int mid = l+r >> 1;
if(pos <= mid) ch[root][1] = ch[oldrt][1], insert(ch[root][0], ch[oldrt][0], l, mid, pos, x, x2);
else ch[root][0] = ch[oldrt][0], insert(ch[root][1], ch[oldrt][1], mid+1, r, pos, x, x2);
// printf("cur = %d [%d,%d] ls = %d, rs = %d, s1 = %lld, s2 = %d\n", root, l, r, ch[root][0], ch[root][1], s[root], s2[root]);
}
inline ll query(int rtl, int rtr, int l, int r, int k) {
// printf("%d %d %d %d\n", rtl, rtr, l, r);
if(s2[rtr] <= k) return s[rtr];
if(l == r) return min(s2[rtr], k)*fys[l];
int sl = s2[ch[rtr][0]];
int mid = l+r>>1;
if(sl >= k) return query(ch[rtl][0], ch[rtr][0], l, mid, k);
else return s[ch[rtr][0]] + query(ch[rtl][1], ch[rtr][1], mid+1, r, k-sl);
}
int main() {
scanf("%d%d", &m, &n);
for (int i=1, S, E, P; i<=m; ++i) {
scanf("%d%d%d", &S, &E, &P);
o[++on] = (oper){S, P, 1};
o[++on] = (oper){E+1, P, -1};
ps.push_back(P);
}
sort(o+1, o+on+1, cmp);
sort(ps.begin(), ps.end());
vector<int>::iterator it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
int mx = -1;
for (int i=1; i<=on; ++i) {
int t = lower_bound(ps.begin(), ps.end(), o[i].p) - ps.begin() + 1;
fys[t] = o[i].p;
o[i].p = t;
mx = max(mx, t);
}
int cur=1;
rtn = 0;
for (int i=1; i<=n; ++i) {
if(o[cur].t != i) {
rte[i] = rtn;
continue;
}
while(o[cur].t == i) {
// printf("%d %d %d\n", o[cur].p, fys[o[cur].p], o[cur].flg);
++rtn;
insert(rt[rtn], rt[rtn-1], 1, mx, o[cur].p, o[cur].flg*fys[o[cur].p], o[cur].flg);
++cur;
}
rte[i] = rtn;
}
// printf("rtn = %d\n", rtn);
ll ans = 1;
int NN = n;
while(NN--) {
int X;
ll A, B, C;
scanf("%d%lld%lld%lld", &X, &A, &B, &C);
ans %= C;
int k = (ans*A + B) % C + 1;
// printf("ask %d %d\n", X, k);
// printf("%d\n", rte[X-1]);
printf("%lld\n", ans = query(rt[rte[X-1]], rt[rte[X]], 1, mx, k));
}
return 0;
}
6. bzoj3524
直接写主席树就行啦！
# include <vector>
# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 8000010, N = 500010;
int rt[N], ch[M][2], s[M], sz=0;
int fys[N], n, m, a[N];
vector<int> ps;
inline void insert(int &root, int oldrt, int l, int r, int x) {
root=++sz;
ch[root][0] = ch[root][1] = 0;
s[root] = s[oldrt] + 1;
if(l == r) return;
int mid=l+r>>1;
if(x>mid) ch[root][0]=ch[oldrt][0], insert(ch[root][1], ch[oldrt][1], mid+1, r, x);
else ch[root][1]=ch[oldrt][1], insert(ch[root][0], ch[oldrt][0], l, mid, x);
}
inline int query(int rtl, int rtr, int l, int r, int k) {
if(l == r) return l;
int sl = s[ch[rtr][0]] - s[ch[rtl][0]], sr = s[ch[rtr][1]] - s[ch[rtl][1]];
if(sl < k && sr < k) return 0;
int a1 = -1, a2 = -1;
int mid = l+r>>1;
if(sl >= k) a1 = query(ch[rtl][0], ch[rtr][0], l, mid, k);
if(sr >= k) a2 = query(ch[rtl][1], ch[rtr][1], mid+1, r, k);
if(a1 == -1 && a2 == -1) return 0;
if(a1 != -1) return a1;
else return a2;
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
ps.push_back(a[i]);
}
sort(ps.begin(), ps.end());
vector<int>::iterator it = unique(ps.begin(), ps.end());
ps.erase(it, ps.end());
int mx = -1;
for (int i=1; i<=n; ++i) {
int t = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + 1;
fys[t] = a[i];
a[i] = t;
mx = max(mx, t);
}
for (int i=1; i<=n; ++i)
insert(rt[i], rt[i-1], 1, mx, a[i]);
while(m--) {
int l, r;
scanf("%d%d", &l, &r);
int times = (r-l+1)/2;
printf("%d\n", fys[query(rt[l-1], rt[r], 1, mx, times+1)]);
}
return 0;
}
7. HDU 4348
主席树区修区查
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int M = 100010, MM = 4000010;
int n, m;
int ch[MM][2], sz=0, root[MM];
ll w[MM], tag[MM];
inline void build(int &x, int l, int r) {
x = ++sz;
ch[x][0] = ch[x][1] = w[x] = tag[x] = 0;
if(l == r) {
scanf("%I64d", &w[x]);
return ;
}
int mid = l+r>>1;
build(ch[x][0], l, mid);
build(ch[x][1], mid+1, r);
w[x] = w[ch[x][0]] + w[ch[x][1]];
}
inline void insert(int &rt, int oldrt, int l, int r, int L, int R, ll del) {
rt = ++sz;
ch[rt][0] = ch[rt][1] = 0;
w[rt] = w[oldrt], tag[rt] = tag[oldrt];
ch[rt][0] = ch[oldrt][0], ch[rt][1] = ch[oldrt][1];
if(L <= l && r <= R) {
tag[rt] += del;
w[rt] += (ll)(r-l+1)*del;
return ;
}
int mid = l+r>>1;
if(R > mid) insert(ch[rt][1], ch[oldrt][1], mid+1, r, L, R, del);
if(L <= mid) insert(ch[rt][0], ch[oldrt][0], l, mid, L, R, del);
w[rt] = w[ch[rt][0]] + w[ch[rt][1]] + tag[rt]*(r-l+1);
}
inline ll query(int rt, int l, int r, int L, int R) {
if(L <= l && r <= R) return w[rt];
ll ret = 0;
if(l <= L && R <= r) ret += tag[rt]*(R-L+1);
else if(L < l && R <= r) ret += tag[rt]*(R-l+1);
else ret += tag[rt]*(r-L+1);
int mid = l+r>>1;
if(L <= mid) ret += query(ch[rt][0], l, mid, L, R);
if(R > mid) ret += query(ch[rt][1], mid+1, r, L, R);
return ret;
}
void sol() {
char ss[5];
sz=0;
build(root[1], 1, n);
int curt = 1;
int l, r, t;
// t must ++
while(m--) {
scanf("%s", ss);
if(ss[0] == 'Q') {
scanf("%d%d", &l, &r);
printf("%I64d\n", query(root[curt], 1, n, l, r));
}
if(ss[0] == 'C') {
ll del;
scanf("%d%d%lld", &l, &r, &del);
++curt;
insert(root[curt], root[curt-1], 1, n, l, r, del);
}
if(ss[0] == 'H') {
scanf("%d%d%d", &l, &r, &t);
++t;
printf("%I64d\n", query(root[t], 1, n, l, r));
}
if(ss[0] == 'B') {
scanf("%d", &curt);
++curt;
}
}
}
int main() {
while(~scanf("%d%d", &n, &m)) sol();
return 0;
}
【说明】
以上各题时间复杂度都是$O(nlogn)$。
关于主席树更深的应用，待续（下一篇文章）
2022年8月04日 01:43
NCVT stands for National Council for Vocational Training, an advisory body set up by Government of India. This council established with responsibilities of prescribing curriculum and standards for craftsmen training and bringing notice to the Government of India. NCVT stands for National Council for Vocational Training, an advisory body set up by Government of India. NCVT MIS Result This council established with responsibilities of prescribing curriculum and standards for craftsmen training and bringing notice to the Government of India. The NCVT runs under skill development and entrepreneurship by Government of India. The curriculum is specific to various pieces of training like national trade, craftsmen and respective certificates issued by the Government.
2022年9月06日 18:15
Bihar Board Model Paper 2023 Class 4 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Bihar Board 4th Class Model Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.