| 数据结构 | 线段树 | poj2528,poj2828,poj2777,poj2886,poj2750, poj2892(区间更新) |
| 静态二叉检索树,平衡树treap,splay | poj2482, poj3468 | |
| 树状树组 | poj1195,poj3321, poj2352 | |
| RMQ | poj3264,poj3368 | |
| 并查集的高级应用 | poj1703, poj2492 | |
| KMP算法 | poj1961,poj2406 |
线段树
poj 2528
以前做过多次，思路很明显，线段数分区间染色，最后统计颜色的个数。我犯了一个极度二百五的错误，导致这题提交5次！！！col的初始化是-1，更新时我当成0了。T_T
View Code #include#include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1using namespace std;const int N = 20010;struct node { int l, r; int col;} seg[N<<2];int num1[N];int num[N];int n;int x[N], y[N];bool cnt[N<<2];int find(int x) { int l, r, mid; l = 0; r = n; while(l <= r) { mid = (l + r) >> 1; if(num[mid] == x) return mid; else if(num[mid] > x) r = mid - 1; else l = mid + 1; } return -1;}void creat(int t, int l, int r) { seg[t].l = l; seg[t].r = r; seg[t].col = -1; if(r == l) return ; int mid = MID(l, r); creat(L(t), l, mid); creat(R(t), mid + 1, r);}void updata(int t, int l, int r, int col) { if(seg[t].l >= l && seg[t].r <= r) { seg[t].col = col; return ; } if(seg[t].col == col) return ; if(seg[t].col >= 0) { seg[L(t)].col = seg[t].col; seg[R(t)].col = seg[t].col; seg[t].col = -1; } int mid = MID(seg[t].l, seg[t].r); if(l > mid) updata(R(t), l, r, col); else if(r <= mid) updata(L(t), l, r, col); else { updata(L(t), l, mid, col); updata(R(t), mid + 1, r, col); }}void query(int t, int l, int r) { if(seg[t].col >= 0) { //printf("%d %d %d\n", l, r, seg[t].col); cnt[seg[t].col] = true; return ; } if(seg[t].l == seg[t].r) return ; int mid = MID(seg[t].l, seg[t].r); query(L(t), l, mid); query(R(t), mid + 1, r);}int main() { //freopen("data.in", "r", stdin); int t, i, j, m; int f, u, v, ans; scanf("%d", &t); while(t--) { scanf("%d", &m); CL(num, 0); REP(i, m) { scanf("%d%d", &x[i], &y[i]); num1[i*2] = x[i]; num1[i*2+1] = y[i]; } n = m*2; i = j = 0; sort(num1, num1 + n); while(i < n) { f = num1[i]; while(num1[i] == f && i < n) i++; num[j++] = f; } n = j; creat(1, 0, n); REP(i, m) { u = find(x[i]); v = find(y[i]); //printf("%d %d %d\n", u, v, i); updata(1, u, v, i); } CL(cnt, 0); ans = 0; query(1, 0, n); REP(i, m) if(cnt[i]) ans++; printf("%d\n", ans); } return 0;}
poj 2828
题意：插队，第i个人插在pos[i]位置的后边，输出最后位置的val[i]顺序。思路：以前做过，又忘了。。。
View Code #include#include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1using namespace std;const int N = 200010;struct node { int l, r; int num;} seg[N<<2];int ans[N];int pos[N];int num[N];bool vis[N];int p;void creat(int t, int l, int r) { seg[t].l = l; seg[t].r = r; seg[t].num = r - l + 1; if(l == r) return ; int mid = MID(l, r); creat(L(t), l, mid); creat(R(t), mid + 1, r);}void updata(int t, int x) { if(p != -1) return ; --seg[t].num; if(seg[t].num == 0 && !vis[seg[t].l]) {p = seg[t].l; vis[p] = true; return ;} if(x <= seg[L(t)].num) updata(L(t), x); else updata(R(t), x - seg[L(t)].num);}int main() { //freopen("data.in", "r", stdin); int n, i; while(~scanf("%d", &n)) { REP(i, n) scanf("%d%d", &pos[i], &num[i]); creat(1, 1, n); CL(vis, false); FORD(i, n - 1, 0) { p = -1; updata(1, pos[i] + 1); ans[p] = num[i]; } printf("%d", ans[1]); FOR(i, 2, n) printf(" %d", ans[i]); cout << endl; } return 0;}
poj 2777
很简单的线段树染色问题，开始着色为1，然后根据输入染色，根据query统计线段上有多少种颜色，幸好颜色最多30种，随便搞一下就好了。。。把统计颜色的数组开的太大了，TLE一次。。。
View Code #include#include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1using namespace std;const int N = 100010;struct node { int l, r; int col;} seg[N<<2];bool col[33], ans;void creat(int t, int l, int r) { seg[t].l = l; seg[t].r = r; seg[t].col = 1; if(l == r) return ; int mid = MID(l, r); creat(L(t), l, mid); creat(R(t), mid + 1, r);}void updata(int t, int l, int r, int col) { if(seg[t].l >= l && seg[t].r <= r) { seg[t].col = col; return ; } if(seg[t].col == col) return ; if(seg[t].col >= 0) { seg[L(t)].col = seg[t].col; seg[R(t)].col = seg[t].col; seg[t].col = -1; } int mid = MID(seg[t].l, seg[t].r); if(l > mid) updata(R(t), l, r, col); else if(r <= mid) updata(L(t), l, r, col); else { updata(L(t), l, mid, col); updata(R(t), mid + 1, r, col); }}void query(int t, int l, int r) { if(seg[t].col >= 0) { col[seg[t].col] = true; return ; } if(seg[t].l == seg[t].r) return ; int mid = MID(seg[t].l, seg[t].r); if(l > mid) query(R(t), l, r); else if(r <= mid) query(L(t), l, r); else { query(L(t), l, mid); query(R(t), mid + 1, r); }}int main() { //freopen("data.in", "r", stdin); int l, t, o, i; int a, b, c, ans; char s[10]; scanf("%d%d%d", &l, &t, &o); creat(1, 1, l); while(o--) { scanf("%s%d%d", s, &a, &b); if(s[0] == 'C') { scanf("%d", &c); updata(1, a, b, c); } else { CL(col, 0); ans = 0; query(1, a, b); FOR(i, 1, t) if(col[i]) ans++; printf("%d\n", ans); } } return 0;}
poj 2750
题意读的很费解，说的是一个N个元素拼成一个环，每个元素有一个value值，value在整数范围内。有k次更新，每更新一个求一次环中连续子串的和最大值。
思路：没思路，开始连题意都没怎么看懂。后来看到很多人转载出题人的解题报告。有人称之为线段树+dp，扯淡！线段树有最优子结构吗？！线段树有后效性吗？！线段树有重叠子问题吗？！线段树归根结底说就是dp的思想！不吐槽了，想起以前看到的一句话，"真的很想直接抄抄他们的代码，假装理解，就这样过去了。"
把原来的环看成 1...N的数组，这样环中的最大值可能有两种情况取到：Case 1、在1...N之间的某个区间；Case 2、[b, N] + [1, a];
第一种情况很容易考虑，计一个xmax值，表示根节点所对应的区间上连续子串的和最大值，线段树在线更新就可以。第二种情况可以这样考虑：记一个sum值，表示根节点所对应的区间所有元素的总和，记xmin表示这段区间上最小连续子串。sum - xmin就是第二种情况的值，因为 [a, b]肯定是最小连续子串，才能保证[b, N] , [1, a]是最大连续子串。
关于xmax, xmin这两个值，可以跟线段树区间更新一样，加lmax, lmin, rmax, rmin。分别表示在一个区间上从左边第一个开始数的最大连续子串，最小连续子串；从右边第一个开始数的最大连续子串，最小连续子串。跟新过程画个区间推一下就可以。
seg[t].sum = seg[L(t)].sum + seg[R(t)].sum;seg[t].xmax = max(max(seg[L(t)].xmax, seg[R(t)].xmax), seg[L(t)].rmax + seg[R(t)].lmax);seg[t].xmin = min(min(seg[L(t)].xmin, seg[R(t)].xmin), seg[L(t)].rmin + seg[R(t)].lmin);seg[t].lmax = max(seg[L(t)].lmax, seg[L(t)].sum + seg[R(t)].lmax);seg[t].rmax = max(seg[R(t)].rmax, seg[R(t)].sum + seg[L(t)].rmax);seg[t].lmin = min(seg[L(t)].lmin, seg[L(t)].sum + seg[R(t)].lmin);seg[t].rmin = min(seg[R(t)].rmin, seg[R(t)].sum + seg[L(t)].rmin);
ps：题目有一个限制，不能把所有的元素都包括。所以如果出现seg[1].xmax == seg[1].sum时(全是正数)，直接输出seg[1].sum - seg[1].xmin，就可以，其他情况则取max(Case 1, Case2);
poj 2892
题意很意思，地道战，Eight Route Army。。。这翻译太有喜感了，哈！
思路：更新到点，query时找的是区间。比Hotel那道题简单，写着写着发现根本就不需要sum这个值，以需要开一个flag标记这一段是否有被搞掉的点，一个lmax表示这段区间从左边开始数最大连续有多少个点，rmax表示这段区间从右边开始数最大连续有多少个点。。。然后，乱搞一下就ok了。表示很无语的一道题，妹的昨晚写完代码有点晚了，以为有问题就保存一下关电脑走人了，今天来了加上数据一看没问题。。。提交一下1Y了。。。悲剧的人生啊！
View Code #include#include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1typedef long long LL;using namespace std;const int N = 50010;struct node { int l, r; bool flag; int lmax, rmax; int mid() { return (l + r) >> 1; }} seg[N<<2];void creat(int t, int l, int r) { seg[t].l = l; seg[t].r = r; seg[t].flag = 0; seg[t].lmax = seg[t].rmax = r - l + 1; if(l == r) return ; int mid = MID(l, r); creat(L(t), l, mid); creat(R(t), mid + 1, r);}void updata(int t, int d) { if(seg[t].l == seg[t].r) { //更新到点 seg[t].flag ^= 1; seg[t].lmax ^= 1; seg[t].rmax ^= 1; return ; } int mid = MID(seg[t].l, seg[t].r); if(d <= mid) updata(L(t), d); else updata(R(t), d); seg[t].lmax = seg[L(t)].lmax + (seg[L(t)].flag == 0 ? seg[R(t)].lmax : 0); seg[t].rmax = seg[R(t)].rmax + (seg[R(t)].flag == 0 ? seg[L(t)].rmax : 0); seg[t].flag = (seg[L(t)].flag == 0 && seg[R(t)].flag == 0) ? 0 : 1;}int query(int t, int d) { if(seg[t].l == seg[t].r) { return seg[t].flag == 0; } int mid = seg[t].mid(); if(d <= mid) { if(d >= mid - seg[L(t)].rmax + 1) return seg[L(t)].rmax + seg[R(t)].lmax; else return query(L(t), d); } else { if(d <= mid + seg[R(t)].lmax) return seg[R(t)].lmax + seg[L(t)].rmax; else return query(R(t), d); }}int st[N];int vis[N];int main() { //freopen("data.in", "r", stdin); int n, t, x, top = 0; char s[10]; scanf("%d%d", &n, &t); creat(1, 1, n); CL(st, 0); CL(vis, 0); while(t--) { scanf("%s", s); if(s[0] == 'D') { scanf("%d", &x); st[top++] = x; if(vis[x] == 0) updata(1, x); vis[x]++; } else if(s[0] == 'Q') { scanf("%d", &x); printf("%d\n", query(1, x)); } else { x = st[--top]; vis[x]--; if(!vis[x]) updata(1, x); } } return 0;}
POJ 2886 详见：
树状数组
poj 1195，注意的几点，instruction = 2时输入l b r t, l <= x <= r, b <= y <= t
ans = sum(r + 1, t + 1) + sum(l, b) - sum(r + 1, b) - sum(l, t + 1);
poj 3321
题意：苹果常在叉上，某些叉有边相连，Q i表示求以i根的树上有多少苹果。C i表示i节点如果有苹果则摘掉，如果没有则加一个。
思路：dfs整棵树，low[i]表示进入以i为根的子树的开始时间，high[i]表示从i出来是的时间，这样[low[i], high[i]]就能包括以i为根的子树。
用low[], high[]编好号以后就可以用树状数组维护了。。。很经典的问题。Mark！
View Code #include#include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1typedef long long LL;using namespace std;const int N = 100010;struct node { int to; int next;} g[N << 2];int head[N], t, ind;int low[N], high[N];int c[N], n;bool vis[N];void init() { CL(head, -1); CL(vis, false); CL(c, 0); t = ind = 0;}void add(int u, int v) { g[t].to = v; g[t].next = head[u]; head[u] = t++;}void dfs(int t) { vis[t] = true; low[t] = ++ind; int i; for(i = head[t]; i != -1; i = g[i].next) if(!vis[g[i].to]) dfs(g[i].to); high[t] = ind;}int lowbit(int i) { return i&(-i);}void Modify(int x, int d) { while(x <= n) { c[x] += d; x += lowbit(x); }}int sum(int x) { int res = 0; while(x > 0) { res += c[x]; x -= lowbit(x); } return res;}int main() { //freopen("data.in", "r", stdin); int u, v, i; char s[10]; init(); scanf("%d", &n); REP(i, n - 1) { scanf("%d%d", &u, &v); add(u, v); } dfs(1); FOR(i, 1, n) Modify(low[i], 1); scanf("%d", &u); while(u--) { scanf("%s%d", s, &v); if(s[0] == 'Q') { printf("%d\n", sum(high[v]) - sum(low[v] - 1)); } else { if(vis[v]) { Modify(low[v], -1); vis[v] = false; } else { Modify(low[v], 1); vis[v] = true; } } } return 0;}
poj 2352
经典树状数组应用，做过好几遍了。。。有一个地方想错了，wa了3次。。。
void Modify(int x, int k) { while(x < M) { //这里不能写成x < n，因为是按x的值插入的。M = 32010； c[x] += k; x += lowbit(x); }}
RMQ
poj 3264
以前用线段树写的，今天用RMQ写了一下，发现RMQ还是很猛的，时间是线段树的一半（也可能是我的线段树些搓了。。。）
详见：http://www.cnblogs.com/vongang/archive/2012/05/03/2481196.html
poj 3368
题意很简单，求给一个序列，Q次询问，每次求 [a, b]区间里的重复数字最多重多少次。
思路：对一个序列tnum[]
-1 -1 1 1 1 1 3 10 10 10 把它处理成num[]
1 2 1 2 3 4 1 1 2 3
按num[]进行RMQ，然后[a, b]区间的两端做单独统计 x表示跟tnum[a]相同的有多少个，y表示跟tnum[b]相同的有多少个（都是相邻的）。中间的用rmq求。（可以标记每一个tnum[i]的起始位置be[i], ed[i]）
ps：开始拍搓了，没考虑a == b的情况，wa掉两次后一测数据。。。偶滴神啊！这么明显的错误。。。
View Code #include#include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for(i = 0; i < n; ++i)#define FOR(i, l, h) for(i = l; i <= h; ++i)#define FORD(i, h, l) for(i = h; i >= l; --i)#define L(x) x << 1#define R(x) x << 1 | 1#define MID(l, r) (l + r) >> 1typedef long long LL;using namespace std;const int N = 200010;const int M = 100010;const int fix = 100000; //修正值，因为有负数int Max[M][20];int num[M], tnum[M];int be[N], ed[N];int n;void init() { int i, j, m; FOR(i, 1, n) { Max[i][0] = num[i]; //Min[i][0] = num[i]; } m = int(log(double(n))/log(2.0)); FOR(j, 1, m){ FOR(i, 1, n - (1<
并查集的高级应用
poj 1703
题意：一个城市有两个流氓团，D a b表示a b不再同一个同一个流氓团里边。A a b表示询问a b是否在一个流氓团里边。根据情况输出 "In the same gang.", "In different gangs." and "Not sure yet."
思路：好吧是我想复杂了。。。昨晚有点困，然后一直在纠结。。。其实相当于二分图2-SAT问题。a b矛盾则连接 a -> b' a' -> b。query时判断a ,b是否在同一集合里，是则输出“In the same”，如果a , b'在同一集合里则表示ab不再同一集合里。否则就不能确定a, b的关系。
poj 2492
跟上题差不多，水题。这题是分两个性别，输入a b表示a和b可以交配，问是否出现同性恋。
合并 a -> b' a' -> b；判断 find(a) == find(b)表示出现同性恋。。。
KMP算法
poj 1916 && poj 2406 解法：