主席树,开坑POJ2104,EOJ3335&hdu6162,hdu5919

Posted by Cww97 on 2017-08-29

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77659475
# 一些废话

去年自己一知半解写的blog

blog1

blog2

blog3

还没看的blog

n个树,其实是有n个线段树

每个线段树记录前n个数插入的状态,是把整个序列排序之后插入自己该在的位置(类似于树状数组求逆序对的那种插入姿势)

每次新建一个线段树大部分节点都是从前一棵树上掰下来的,公用的,所以每次增加nlogn个节点

poj2104

拿去年的板子改的,去年的代码好丑,换成舒服的风格

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
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int arr[N]; //arr[] 原数组的数在rank[]中的位置;
int Rank[N]; //rank[] 原数组离散化

struct ChairTree{
#define sum(x) tree[x].w
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc, w;
node(){}
} tree[N * 20];
int root[N], cnt;
void build(){
root[0] = cnt = 0;
memset(tree, 0, sizeof(tree));
}

void add(int pos, int val, int &rt, int rt1, int l, int r){
tree[rt = ++cnt] = tree[rt1];
tree[rt].w += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}

int query(int k, int rt, int rt1, int l, int r){
if (l == r) return l;
int lsize = sum(tree[rt1].lc) - sum(tree[rt].lc);
int m = (l + r) >> 1;
if (lsize >= k) return query(k, lson);
else return query(k - lsize, rson);
}
} T;

int main(){
//freopen("in.txt","r",stdin);
int _, l, r, k, n, q;
for (; ~scanf("%d%d", &n, &q);){
T.build();
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
Rank[i] = arr[i];
}
sort(Rank + 1, Rank + n+1);//Rank存储原值
int m = unique(Rank + 1, Rank + n +1) - (Rank + 1);
for (int i = 1; i <= n; i++) {//离散化后的数组,仅仅用来更新
arr[i] = lower_bound(Rank + 1, Rank + n+1, arr[i]) - Rank;
}
for (int i = 1; i <= n; i++){
T.add(arr[i], 1, T.root[i], T.root[i-1], 1, n);
}
for (; q--;){
scanf("%d%d%d", &l, &r, &k);
int pos = T.query(k, T.root[l-1], T.root[r], 1, n);
printf("%d\n", Rank[pos]);
}
}
return 0;
}

EOJ3335&&hdu6162

多校第九场02

本题花式A法可以看这里

树上套个主席树

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
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
LL gift[N], Rank[N];//节点权值和离散化

struct ChairTree{
#define sum(x) tree[x].sum
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc;
LL sum;
} tree[N * 30];
int n, root[N], cnt;

inline void build(int _n){
n = _n; cnt = 0;
}

void add(int pos, LL val, int &rt, int rt1, int l, int r){
tree[rt = ++cnt] = tree[rt1];
tree[rt].sum += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}

LL query(int L, int R, int rt, int rt1, int l, int r){
if (L <= l && r <= R) return sum(rt1) - sum(rt);
if (sum(rt1) == 0) return 0;
if (sum(rt1) == sum(rt)) return 0;
LL ans = 0;
int m = (l + r) >> 1;
if (L <= m) ans += query(L, R, lson);
if (m < R) ans += query(L, R, rson);
return ans;
}
#undef sum(x)
#undef lson
#undef rson
} T;

struct graph{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):from(u), to(v), nxt(n){}
} edges[N * 2];
static const int LCADEP = 17;
int n, E, head[N];
int top, dep[N], fa[N][LCADEP + 1];

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
this -> n = n ; E = -1; top = 0; dep[0] = 0;
for (int i = 0; i <= n; i++) head[i] = -1;
memset(fa, 0, sizeof(fa));
}

void dfs(int u, int pre){
T.add(gift[u], Rank[gift[u]], T.root[u], T.root[pre], 1, T.n);
fa[u][0] = pre;
dep[u] = dep[pre] + 1;
for (int i = 1; i <= LCADEP; i++){
if (dep[u] < (1<<i)) break;
fa[u][i] = fa[fa[u][i-1]][i-1];
}
for (int i = head[u]; i != -1; i = edges[i].nxt){
if (edges[i].to != pre) dfs(edges[i].to, u);
}
}

int lca(int x, int y){
if (dep[x] < dep[y]) swap(x,y);
int t = dep[x] - dep[y];
for (int i = 0; i <= LCADEP; i++) if ((1<<i) & t) x = fa[x][i];
for (int i = LCADEP; i >= 0; i--) if (fa[x][i] != fa[y][i]){
x = fa[x][i]; y = fa[y][i];
}
return x==y ? x : fa[x][0];
}

LL query(int u, int v, int L, int R){
int f = lca(u, v);
LL ans = 0;
ans += T.query(L, R, T.root[f], T.root[u], 1, T.n);
ans += T.query(L, R, T.root[fa[f][0]], T.root[v], 1, T.n);
return ans;
}
} g ;

int main () {
//freopen("in.txt", "r", stdin);
int n, q, u, v;
for (LL a, b; ~scanf("%d%d", &n, &q);) {
for(int i = 1; i <= n; i++) {
scanf("%lld", &gift[i]);
Rank[i] = gift[i];
}
sort(Rank + 1, Rank + n+1);
int un = unique(Rank + 1, Rank + n+1) - (Rank+1);
for (int i = 1; i <= n; i++){
gift[i] = lower_bound(Rank + 1, Rank + un+1, gift[i]) - Rank;
}

g.Init(n);
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
g.AddEdge(v, u);
}
T.build(un);
g.dfs(1, 0);

for (; q--;){
scanf("%d%d%lld%lld", &u, &v, &a, &b);
int aa = lower_bound(Rank+1, Rank + un+1, a) - Rank;
if (Rank[aa] < a) aa++;
int bb = lower_bound(Rank+1, Rank + un+1, b) - Rank;
if (bb > un || Rank[bb] > b) bb--;
printf("%lld", g.query(u, v, aa, bb));
putchar(q==0 ? '\n' : ' ');
}
}
return 0;
}

hdu5919

看了这个题解写的

题意

有长度为n的序列,强制在线询问[l,r] 这段区间中所有不同数出现的第一个位置,按照位置从小到大排完序以后的中间(向上取整)的那个位置是多少?

真-语文题

没有对原来数据的离散化操作,每棵线段树就是原数组的位置

每个数字只有一次,每次+1,前面有了就吧前面的-1

for的时候最坏要update 2n次,所以要开40n的大小

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
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
# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 2e5 + 7;
int n, arr[N], last[N];

struct ChairTree{
#define lson tree[rt].lc, tree[rt1].lc, l, m
#define rson tree[rt].rc, tree[rt1].rc, m+1, r
struct node{
int lc, rc, w;
node(){}
} tree[N * 40];
int root[N], cnt;

inline void build(){
root[0] = root[n+1] = cnt = 0;
memset(tree, 0, sizeof(tree));
memset(root, 0, sizeof(root));
}

void add(int pos, int val, int &rt, int rt1, int l, int r){
int tmp = rt;
tree[rt = ++cnt] = tmp ? tree[tmp] : tree[rt1];
tree[rt].w += val;
if (l == r) return;
int m = (l + r) >> 1;
if (pos <= m) add(pos, val, lson);
else add(pos, val, rson);
}

//下面两个函数, rt==rt1, 带两个仅仅是为了凑个lson和rson的参数

int sum(int L, int R, int rt, int rt1, int l, int r){
if (L <= l && r <= R) return tree[rt].w;
int ans = 0;
int m = (l + r) >> 1;
if (L <= m) ans += sum(L, R, lson);
if (m < R) ans += sum(L, R, rson);
return ans;
}

int query(int k, int rt, int rt1, int l, int r){
if (l == r) return l;
int lsize = tree[tree[rt].lc].w;
int m = (l + r) >> 1;
if (lsize >= k) return query(k, lson);
else return query(k - lsize, rson);
}
} T;

int main(){
//freopen("in.txt","r",stdin);
int _, __, l, r, q;
scanf("%d", &__);
for (int _ = 1; _ <= __; _++){
printf("Case #%d:", _);
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
T.build();
memset(last, 0, sizeof(last));
for (int i = n; i >= 1; i--){
T.add(i, 1, T.root[i], T.root[i+1], 1, n);
if (last[arr[i]]) T.add(last[arr[i]], -1, T.root[i], T.root[i], 1, n);
last[arr[i]] = i;
}
int ans = 0;
for (; q--;){
scanf("%d%d", &l, &r);
l = (l + ans) % n + 1;
r = (r + ans) % n + 1;
if (l > r) swap(l, r);
int sum = T.sum(l, r, T.root[l], T.root[l], 1, n);
ans = T.query((sum+1)/2, T.root[l], T.root[l], 1, n);
printf(" %d", ans);
}
puts("");
}
return 0;
}