重温主席树(附7题)

tonyfang posted @ 2016年12月22日 20:23 in 随笔 with tags OI c++ , 302 阅读

主席树的话,其实理解比那些啥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)$。

关于主席树更深的应用,待续(下一篇文章)

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter