|
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 137 138 139 140 141 142 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; #define MAXN 262145 int tree[MAXN]; int lazy[MAXN]; int mark[MAXN]; int M = 1,H = 0; void tree_init(unsigned int num){ memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); memset(mark, 0, sizeof(mark)); M = 1; for (; M < num+2; M <<= 1) H++; M--; for (int i = 1; i <= num; i++) { mark[i+1+M] = 1; } for (int i = M; i >= 1; i--) { mark[i] = mark[(i << 1) + 1] + mark[i << 1]; } } void lazy_down(int pos){ if (lazy[pos]) { lazy[pos] = 0; lazy[pos*2] = lazy[pos*2]?0:1; tree[pos*2] = mark[pos*2] - tree[pos*2]; lazy[pos*2+1] = lazy[pos*2+1]?0:1; tree[pos*2+1] = mark[pos*2+1] - tree[pos*2+1]; } } void tree_negate(int from,int to,int l,int r,int pos){ //default pos = 1 l = 1 r = n if (r < from || l > to){ //out of range return; }else if (l >= from && r <= to) { //fully inclusive lazy[pos] = lazy[pos]?0:1; tree[pos] = mark[pos] - tree[pos]; }else{ //partially inclusive lazy_down(pos); tree_negate(from, to, l, l+mark[pos*2]-1, pos*2); tree_negate(from, to, l+mark[pos*2], r, pos*2+1); if (l < r) { tree[pos] = tree[pos*2] + tree[pos*2+1]; } } } int res; void tree_query(int from,int to,int l,int r,int pos){ //default pos = 1 l = 1 r = n if (r < from || l > to){ //out of range return; }else if (l >= from && r <= to) { //fully inclusive res += tree[pos]; }else{ //partially inclusive lazy_down(pos); tree_query(from, to, l, l+mark[pos*2]-1, pos*2); tree_query(from, to, l+mark[pos*2], r, pos*2+1); } } int n = 0,m = 0; vector<int> child[MAXN]; vector<int> linear; int str[MAXN],ter[MAXN]; bool vis[MAXN]; void dfs(int cur){ linear.push_back(cur); str[cur] = (int)linear.size(); vis[cur] = true; for (int i = 0; i < child[cur].size(); i++) { if (!vis[child[cur][i]]) { dfs(child[cur][i]); } } ter[cur] = (int)linear.size(); } int main(){ while (scanf(" %d %d",&n,&m) != EOF) { tree_init(n); for (int i = 1; i <= n; i++) { child[i].clear(); } for (int i = 2; i <= n; i++) { int parent; scanf(" %d",&parent); child[parent].push_back(i); } memset(vis, false, sizeof(vis)); linear.clear(); dfs(1); for (int i = 1; i <= m; i++) { char arg1; int arg2; scanf(" %c %d",&arg1,&arg2); if (arg1 == 'o') { tree_negate(str[arg2], ter[arg2], 1, n, 1); }else{ res = 0; tree_query(str[arg2], ter[arg2], 1, n, 1); printf("%d\n",res); } } printf("n"); } return 0; } |
被这道题玩得相当惨。。。这道题是一个DFS＋线段树的题。
首先这个题是在一棵传统树上面进行大规模的区间读写操作，这是线段树的玩法，但是怎么玩呢？
这个时候DFS就派上用场了，我们通过DFS得到DLR遍历，把dfs时进入一个节点是时间记下来，出去一个节点的时间记下来，就可以得到这个节点的子树在DLR遍历中的区间的开始与结束标号，这样就相当于把2维的树降到一维了。
之后得到了一个一维的数组，就可以开线段树，这里涉及区间更新，还要加开懒惰标记。
这种把树压成线然后再搞是一种很常用很好的姿势！
其实这道题卡死我的就是懒惰标记这里。我原来一直在用zkw线段树，但是因为是自下向上操作没有递归，所以我就根本不知道怎么下手写懒惰标记了，鼓捣2天未果，orz各路大神的适配zkw线段树的懒惰标记是给rmq准备的，不适合这个题，没办法研究递归版本了。
递归版本的话，实现懒惰标记的思路就是：
1.更新时，如果发生了目标区间与当前区间相交的情况，首先把当前节点的懒惰标记下传给下一层，然后再去更新下一层，更新完下一层后，用更新好的下一层更新自身。如果目标区间完全包括当前区间，这个时候就不用往下走了，首先更新自己的值，然后更新自己位置的懒惰标记。
2.查询时，如果目标区间和当前区间相交，这时候需要下传当前节点的懒惰标记，然后进入下一层接着查询，如果目标区间完全包括当前区间，直接更新答案。
3.下传时，我们只操作当前节点的子节点，不可以操作当前节点（否则就重复操作啦），注意我们只下传了一层，所以不仅要操作下面一层的值，还要操作下面一层的懒惰标记，同时清空当前节点的懒惰标记。
August 25, 2015
[…] 懒惰标记的工作原理可以参照：ZOJ 3686 A Simple Tree Problem。 […]