首页 > 代码库 > BZOJ2819 Nim

BZOJ2819 Nim

2024-08-07 20:26:50   219人阅读

做法。。。就不讲了，参见hzwer的blog好了

我们发现只要维护树上点到根的xor值就可以了，于是先搞个dfs序，然后用树状数组维护即可。

反正各种调不出。。。各种WA

后来发现又是LCA的姿势不对= =，今天不是刚写过noip题嘛T T

蒟蒻还是滚去挖矿算了、、、

 

  1 /**************************************************************  2     Problem: 2819  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:10240 ms  7     Memory:76648 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 #define lowbit(x) x & -x 14 using namespace std; 15 const int N = 500005; 16   17 struct edge { 18     int next, to; 19     edge() {} 20     edge(int _n, int _t) : next(_n), to(_t) {} 21 } e[N << 1]; 22   23 struct tree_node { 24     int v, dep, st, ed; 25     int fa[19]; 26 } tr[N]; 27   28 int n; 29 int tot, first[N]; 30 int cnt_seq, BIT[N]; 31   32 inline int read() { 33     int x = 0; 34     char ch = getchar(); 35     while (ch < ‘0‘ || ‘9‘ < ch) 36         ch = getchar(); 37     while (‘0‘ <= ch && ch <= ‘9‘) { 38         x = x * 10 + ch - ‘0‘; 39         ch = getchar(); 40     } 41     return x; 42 } 43   44 void XOR(int x, int v) { 45     while (x <= n) 46         BIT[x] ^= v, x += lowbit(x); 47 } 48   49 int query(int x) { 50     int res = 0; 51     while (x) 52         res ^= BIT[x], x -= lowbit(x); 53     return res; 54 } 55   56 inline void Add_Edges(int x, int y) { 57     e[++tot] = edge(first[x], y), first[x] = tot; 58     e[++tot] = edge(first[y], x), first[y] = tot; 59 } 60   61 void dfs(int p) { 62     int x, y; 63     for (x = 1; x <= 18; ++x) 64         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1]; 65     tr[p].st = ++cnt_seq; 66     for (x = first[p]; x; x = e[x].next) 67         if ((y = e[x].to) != tr[p].fa[0]) { 68             tr[y].fa[0] = p, tr[y].dep = tr[p].dep + 1; 69             dfs(y); 70         } 71     tr[p].ed = cnt_seq; 72     XOR(tr[p].st, tr[p].v), XOR(tr[p].ed + 1, tr[p].v); 73 } 74   75 int lca(int x, int y) { 76     int i; 77     if (tr[x].dep < tr[y].dep) swap(x, y); 78     for (i = 18; ~i; --i) 79         if (tr[tr[x].fa[i]].dep >= tr[y].dep) 80             x = tr[x].fa[i]; 81     if (x == y) return x; 82     for (i = 18; ~i; --i) 83         if (tr[x].fa[i] != tr[y].fa[i]) 84             x = tr[x].fa[i], y = tr[y].fa[i]; 85     return tr[x].fa[0]; 86 } 87   88 int main() { 89     int i, x, y, LCA, Q; 90     char ch; 91     n = read(); 92     for (i = 1; i <= n; ++i) 93         tr[i].v = read(); 94     for (i = 1; i < n; ++i) 95         Add_Edges(read(), read()); 96     tr[1].dep = 1; 97     dfs(1); 98     Q = read(); 99     while (Q--) {100         ch = getchar();101         while (ch != ‘Q‘ && ch != ‘C‘) ch = getchar();102         x = read(), y = read();103         if (ch == ‘Q‘)104             puts(query(tr[x].st) ^ query(tr[y].st) ^ tr[lca(x, y)].v ? "Yes" : "No");105         else {106             XOR(tr[x].st, tr[x].v), XOR(tr[x].ed + 1, tr[x].v);107             tr[x].v = y;108             XOR(tr[x].st, tr[x].v), XOR(tr[x].ed + 1, tr[x].v);109         }110     }111     return 0;112 }
View Code

 

BZOJ2819 Nim


联系
我们