可持久化数据结构题目泛做。

个人理解：

每个新的线段树的一个结点保存的是1...位置 i中的数字在相应的区间上有几个。

然后我们用r-(l-1)得到的就是l...r上的中字在相应的区间中出现了几个。

题目1 POJ2104

题目大意：静态查询区间第K小值。

裸的可持久化线段树。

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 
 7 using namespace std;
 8 const int N = 100000 + 5;
 9 
10 struct SegTree {
11   int l, r, size;
12 }Node[N * 30];
13 
14 struct data {
15   int v, pos;
16   bool operator < (const data &k) const {
17     return v < k.v;
18   }
19 }a[N];
20 
21 int n, m, rank[N], l, r, k, root[N], tot;
22 
23 void build(int &o, int l, int r) {
24   o = ++ tot;
25   Node[o].l = Node[o].r = Node[o].size = 0;
26   if(l >= r) return;
27   int mid = (l + r) >> 1;
28   build(Node[o].l, l, mid);
29   build(Node[o].r, mid + 1, r);
30 }
31 
32 void update(int pre, int &o, int l, int r, int kth) {
33   o = ++ tot;
34   Node[o] = Node[pre];
35   Node[o].size ++;
36   if(l >= r) return;
37   int mid = (l + r) >> 1;
38   if(kth <= mid)
39     update(Node[pre].l, Node[o].l, l, mid, kth);
40   else
41     update(Node[pre].r, Node[o].r, mid + 1, r, kth);
42 }
43 
44 int query(int r1, int r2, int l, int r, int kth) {
45   if(l >= r) return l;
46   int lc = Node[Node[r2].l].size - Node[Node[r1].l].size;
47   int mid = (l + r) >> 1;
48   if(lc >= kth)
49     return query(Node[r1].l, Node[r2].l, l, mid, kth);
50   else
51     return query(Node[r1].r, Node[r2].r, mid + 1, r, kth - lc);
52 }
53 
54 int main() {
55   scanf("%d%d", &n, &m);
56   for(int i = 1; i <= n; ++ i) {
57     scanf("%d", &a[i].v);
58     a[i].pos = i;
59   }
60   sort(a + 1, a + n + 1);
61   for(int i = 1; i <= n; ++ i)
62     rank[a[i].pos] = i;
63   build(root[0], 1, n);
64   for(int i = 1; i <= n; ++ i)
65     update(root[i - 1], root[i], 1, n, rank[i]);
66   for(int i = 1; i <= m; ++ i) {
67     scanf("%d%d%d", &l, &r, &k);
68     printf("%d
", a[query(root[l - 1], root[r], 1, n, k)].v);
69   }
70   return 0;
71 }

2104

题目2 SPOJ Count On a Tree 1

题目大意：

给一个树，求路径(u,v)上的第k小值。

算法讨论：可持久化线段树。

我们考虑序列的做法是一个元素在前一个元素上建立新的线段树。那么对于一个树来说，就是在父亲的基础上建立一棵新的线段树。

所有我们有如下的做法：先搞出每个点的权值的rank，然后对树DFS，求出DFS序，则每个点就以各自的DFS序为一个新根，建立在FA的DFS序上。

在查询的时候，用U和V的线段树权值减去LCA和FA(LCA)的线段树权值即可。

坑点：一定要注意去重。然后再搞RANK。

代码：

  1 #include <cstdlib>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cstdio>
  6 
  7 using namespace std;
  8 const int N = 100000 + 5;
  9 inline int read() {
 10   int x = 0;
 11   char c = getchar();
 12   while(!isdigit(c)) c = getchar();
 13   while(isdigit(c)) {
 14     x = x * 10 + c - '0';
 15     c = getchar();
 16   }
 17   return x;
 18 }
 19 
 20 int n, m, tail, tot, cnt, tim;
 21 int v[N], seq[N], num[N], seg[N], fa[N];
 22 int f[N][20], head[N], depth[N], rank[N], root[N];
 23 
 24 struct Edge {
 25   int from, to, next;
 26 }edges[N << 1];
 27 
 28 struct SegTree {
 29   int l, r, size;
 30 }Node[N * 40];
 31 
 32 void insert(int from, int to) {
 33   ++ cnt;
 34   edges[cnt].from = from; edges[cnt].to = to;
 35   edges[cnt].next = head[from]; head[from] = cnt;
 36 }
 37 
 38 void dfs(int u, int ff) {
 39   fa[u] = ff;
 40   ++ tim; num[u] = tim; seg[tim] = u;
 41   for(int i = head[u]; i; i = edges[i].next) {
 42     int v = edges[i].to;
 43     if(v != ff) {
 44       depth[v] = depth[u] + 1;
 45       dfs(v, u);
 46     }
 47   }
 48 }
 49 
 50 void prepare() {
 51   memset(f, -1, sizeof f);
 52   for(int i = 1; i <= n; ++ i) f[i][0] = fa[i];
 53   for(int j = 1; (1 << j) <= n; ++ j) {
 54     for(int i = 1; i <= n; ++ i) {
 55       if(f[i][j - 1] != -1) {
 56         f[i][j] = f[f[i][j - 1]][j - 1];
 57       }
 58     }
 59   }
 60 }
 61 
 62 int lca(int a, int b) {
 63   int i;
 64   if(depth[a] < depth[b]) swap(a, b);
 65   for(i = 0; (1 << i) <= depth[a]; ++ i);
 66   -- i;
 67   for(int j = i; j >= 0; -- j)
 68     if(depth[a] - depth[b] >= (1 << j))
 69       a = f[a][j];
 70   if(a == b) return a;
 71   for(int j = i; j >= 0; -- j) {
 72     if(f[a][j] != -1 && f[a][j] != f[b][j]) {
 73       a = f[a][j]; b = f[b][j];
 74     }
 75   }
 76   return f[a][0];
 77 }
 78 
 79 void build(int &o, int l, int r) {
 80   o = ++ tot;
 81   Node[o].l = Node[o].r = Node[o].size = 0;
 82   if(l >= r) return;
 83   int mid = (l + r) >> 1;
 84   build(Node[o].l, l, mid);
 85   build(Node[o].r, mid + 1, r);
 86 }
 87 
 88 void update(int pre, int &o, int l, int r, int kth) {
 89   o = ++ tot;
 90   Node[o] = Node[pre];
 91   Node[o].size ++;
 92   if(l >= r) return;
 93   int mid = (l + r) >> 1;
 94   if(kth <= mid)
 95     update(Node[pre].l, Node[o].l, l, mid, kth);
 96   else
 97     update(Node[pre].r, Node[o].r, mid + 1, r, kth);
 98 }
 99 
100 int query(int r1, int r2, int r3, int r4, int l, int r, int kth) {
101   if(l >= r) return l;
102   int lc = Node[Node[r1].l].size + Node[Node[r2].l].size - Node[Node[r3].l].size - Node[Node[r4].l].size;
103   int mid = (l + r) >> 1;
104   if(lc >= kth)
105     return query(Node[r1].l, Node[r2].l, Node[r3].l, Node[r4].l, l, mid, kth);
106   else return query(Node[r1].r, Node[r2].r, Node[r3].r, Node[r4].r, mid + 1, r, kth - lc);
107 }
108 
109 int Q(int x, int y, int z) {
110   int Lca = lca(x, y);
111   return seq[query(root[num[x]], root[num[y]], root[num[Lca]], root[num[fa[Lca]]], 1, tail, z)];
112 }
113 
114 int main() {
115   //int __size__ = 64 << 20; // 64MB
116   //char *__p__ = (char*)malloc(__size__) + __size__;
117   //__asm__("movl %0, %%esp
" :: "r"(__p__));
118   int x, y, z;
119   n = read(); m = read();
120   for(int i = 1; i <= n; ++ i) {
121     v[i] = read();
122     seq[i] = v[i];
123   }
124   sort(seq + 1, seq + n + 1);
125   tail = unique(seq + 1, seq + n + 1) - seq - 1;
126   for(int i = 1; i <= n; ++ i)
127     rank[i] = lower_bound(seq + 1, seq + tail + 1, v[i]) - seq;
128   for(int i = 1; i < n; ++ i) {
129     x = read(); y = read();
130     insert(x, y); insert(y, x);
131   }
132   depth[1] = 1; num[0] = 0; seg[0] = 0;
133   dfs(1, 0); prepare();
134   build(root[0], 1, tail);
135   for(int i = 1; i <= n; ++ i) {
136     int t = seg[i];
137     update(root[num[fa[t]]], root[i], 1, tail, rank[t]);
138   }
139   bool flag = false;
140   for(int i = 1; i <= m; ++ i) {
141     x = read(); y = read(); z = read();
142     //x ^= lastans;
143     if(flag)
144       printf("
%d", Q(x, y, z));
145     else {
146       printf("%d", Q(x, y, z));
147       flag = true;
148     }
149   }
150   return 0;
151 }

COT

题目3 SPOJ Count On a Tree II (还没写呢)

题目大意：

给一个树，每个点都有一个权值。求(u,v)路径上有多少本质不同的权值。

n <= 4W, m <= 10W

算法讨论：

首先感觉这个题可以树上莫队搞掉。哪天开心了写一发，今天先贴可持久化的做法。

题目4 HDU4417 SuperMario

题目大意：

给定一个数列，求区间L_R内小于等于H的数有多少。

算法讨论：

分块？别想了你，32M内存，卡掉你不在话下。而且多组数据，O(Nsqrt(N)*T)估计险过吧。还是来YY正解。

可持久化线段树。首先把序列离散化建立可持久化线段树。

然后对于每个要查询的数，先查询出其在原序列中的Rank，由于是小于等于它的数有多少，所以 upper_bound。

否则就Lower_boud。接着我们在权值线段树上走。如果这个数比当前区间的mid大，就加上左子树的size差然后去右边查询。

否则就去左边查询。自己还傻傻的每次都去叶子结点查询。

自己要注意的几个地方：

首先自己离散化之后的数组大小和权值线段树的右边界老不改，如果还用N，就是这题14遍的TLE。

还就是如果当前要查询的数是整个序列中最小的，那么返回值是-1，则要记得判断为0.

鸣谢SMZ大神指导。

  1 #include <cstdlib>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <iostream>
  6 
  7 using namespace std;
  8 
  9 const int N = 100000 + 5;
 10 inline int read() {
 11   int x = 0;
 12   char c = getchar();
 13   while(!isdigit(c)) c = getchar();
 14   while(isdigit(c)) {
 15     x = x * 10 + c - '0';
 16     c = getchar();
 17   }
 18   return x;
 19 }
 20 
 21 struct data {
 22   int v, pos;
 23   bool operator < (const data &k) const {
 24     return v < k.v;
 25   }
 26 }a[N];
 27 
 28 struct SegTree {
 29   int size, l, r;
 30 }Node[N * 19];
 31 
 32 int n, m, tot, ans, tail;
 33 int rk[N], root[N], v[N], seq[N];
 34 
 35 void build(int &o, int l, int r) {
 36   o = ++ tot;
 37   Node[o].l = Node[o].r = Node[o].size = 0;
 38   if(l >= r) return;
 39   int mid = (l + r) >> 1;
 40   build(Node[o].l, l, mid);
 41   build(Node[o].r, mid + 1, r);
 42 }
 43 
 44 void update(int pre, int &o, int l, int r, int kth) {
 45   o = ++ tot;
 46   Node[o] = Node[pre];
 47   Node[o].size ++;
 48   if(l >= r) return;
 49   int mid = (l + r) >> 1;
 50   if(kth <= mid)
 51     update(Node[pre].l, Node[o].l, l, mid, kth);
 52   else
 53     update(Node[pre].r, Node[o].r, mid + 1, r, kth);
 54 }
 55 
 56 int query(int r1, int r2, int l, int r, int kth) {
 57   if(l > r) return 0;
 58   if(l == r)
 59     return Node[r2].size - Node[r1].size;
 60   int mid = (l + r) >> 1;
 61   if(kth > mid) {
 62     return (Node[Node[r2].l].size - Node[Node[r1].l].size) + query(Node[r1].r, Node[r2].r, mid + 1, r, kth);
 63   }
 64   else {
 65     return query(Node[r1].l, Node[r2].l, l, mid, kth);
 66   }
 67 }
 68 
 69 void Q(int x, int y, int z, int kth) {
 70   ans = query(root[x - 1], root[y], 1, tail, kth);
 71 }
 72 
 73 int main() {
 74   int t, x, y, z, tt = 0, zk;
 75   t = read();
 76   while(t --) {
 77     for(int i = 1; i <= tot; ++ i)
 78       Node[i].size = Node[i].l = Node[i].r = 0;
 79     tot = 0;
 80     ++ tt;
 81     printf("Case %d:
", tt);
 82     n = read(); m = read();
 83     for(int i = 1; i <= n; ++ i) {
 84       v[i] = read();
 85       seq[i] = v[i];
 86     }
 87     sort(seq + 1, seq + n + 1);
 88     tail = unique(seq + 1, seq + n + 1) - seq - 1;
 89     for(int i = 1; i <= n; ++ i)
 90       rk[i] = lower_bound(seq + 1, seq + tail + 1, v[i]) - seq;
 91     build(root[0], 1, tail);
 92     for(int i = 1; i <= n; ++ i)
 93       update(root[i - 1], root[i], 1, tail, rk[i]);
 94     for(int i = 1; i <= m; ++ i) {
 95       x = read(); y = read(); z = read();
 96       x ++; y ++;
 97       zk = upper_bound(seq + 1, seq + tail + 1, z) - seq - 1;
 98       if(zk > 0)
 99         Q(x, y, z, zk);
100       else ans = 0;
101       printf("%d
", ans);
102     }
103   }
104   return 0;
105 }

4417

题目5 51nod 1175 区间第K大。

裸题啊。

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 50000 + 5;

int n, tail, cnt, m;
int a[N], que[N], rank[N], root[N];

struct SegMent {
	int l, r, size;
}Node[N * 20];

void build(int &o, int l, int r) {
	o = ++ cnt;
	Node[o].l = Node[o].r = Node[o].size = 0;
	if(l >= r) return;
	int mid = (l + r) >> 1;
	build(Node[o].l, l, mid);
	build(Node[o].r, mid + 1, r);
}

void update(int o, int &p, int l, int r, int kth) {
	p = ++ cnt;
	Node[p] = Node[o];
	Node[p].size ++;
	if(l >= r) return;
	int mid = (l + r) >> 1;
	if(kth <= mid)
	  update(Node[o].l, Node[p].l, l, mid, kth);
	else
	  update(Node[o].r, Node[p].r, mid + 1, r, kth);
}

int query(int r1, int r2, int l, int r, int kth) {
	if(l >= r) return l;
	int lc = Node[Node[r2].l].size - Node[Node[r1].l].size;
	int mid = (l + r) >> 1;
	if(lc >= kth)
	  return query(Node[r1].l, Node[r2].l, l, mid, kth);
	else
	  return query(Node[r1].r, Node[r2].r, mid + 1, r, kth - lc);
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		que[++ tail] = a[i];
	}
	sort(que + 1, que + tail + 1);
	tail = unique(que + 1, que + tail + 1) - que - 1;
	for(int i = 1; i <= n; ++ i) rank[i] = lower_bound(que + 1, que + tail + 1, a[i]) - que;
	build(root[0], 1, tail);
	for(int i = 1; i <= n; ++ i)
	  update(root[i - 1], root[i], 1, tail, rank[i]);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++ i) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		l ++; r ++;
		printf("%d
", que[query(root[l - 1], root[r], 1, tail, (r - l + 1) - k + 1)]);
	}
	system("pause");
	return 0;
}