相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5571
数据生成器:http://paste.ubuntu.com/23672970/
中文题面:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=651&pid=1004
官方题解:http://oi.cyo.ng/?attachment_id=2084
解题报告
看到位运算,首先想到的就是一位一位独立来搞
酱紫的话,这题就非常简单了
直接上点分树,什么数据结构都不用套,记录零一就可以了
值得注意的是,拆二进制最好拆在最外层
因为拆在里面的话,数组会多一维,寻址的时间消耗大大增加
否则会T到死,不要问我是怎么知道的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 30000+9; const int M = N << 1; const int L = 16; const int INF = 1e9; int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N]; int val[N],dep[N],dis[N],fa[N][L],P[N],V[N]; LL ans[N]; inline void Add_Edge(int u, int v, int w) { to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w; to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w; } inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } void DFS(int w, int f) { dep[w] = dep[f] + 1; fa[w][0] = f; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { dis[to[i]] = dis[w] + cost[i]; DFS(to[i], w); } } } inline int LCA(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int i=L-1;~i;i--) { if (dep[fa[u][i]] >= dep[v]) { u = fa[u][i]; } } if (u == v) return u; for (int i=L-1;~i;i--) { if (fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } } return fa[u][0]; } inline int DIS(int u, int v) { int lca = LCA(u, v); return dis[u] + dis[v] - dis[lca] * 2; } class Node_Based_Divide_and_Conquer{ int area_sz,cur_ans,root,rod[N][L],sum[N]; int anc[N][L],len[N],tos[2][N],tot[2][N]; bool vis[N]; LL f[2][N],sub[2][N]; public: inline void init() { memset(vis,0,sizeof(vis)); cur_ans = INF; area_sz = n; Get_Root(1, 1); len[root] = 1; Build(root, n); } inline void prework() { memset(f, 0 ,sizeof(f)); memset(sub, 0, sizeof(sub)); memset(tot, 0, sizeof(tot)); memset(tos, 0, sizeof(tos)); } inline void modify(int w, int t, int p) { for (int i=0,pre,cur;i<len[w];i++) { cur = anc[w][i]; f[t][cur] += rod[w][i] * p; tot[t][cur] += p; if (i) { pre = anc[w][i-1]; sub[t][pre] += rod[w][i] * p; tos[t][pre] += p; } } } inline LL query(int w, int t, int k) { LL ret = 0,s,d; t ^= 1; ret += f[t][w] << k; for (int i=1,cur,pre;i<len[w];i++) { cur = anc[w][i]; pre = anc[w][i-1]; d = f[t][cur] - sub[t][pre]; s = tot[t][cur] - tos[t][pre]; ret += d + s * rod[w][i] << k; } return ret; } private: void Get_Root(int w, int F) { sum[w] = 1; int mx = 0; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]] && to[i] != F) { Get_Root(to[i], w); mx = max(sum[to[i]], mx); sum[w] += sum[to[i]]; } } mx = max(mx, area_sz - sum[w]); if (mx < cur_ans) { cur_ans = mx; root = w; } } void Build(int w, int sz) { vis[w] = 1; anc[w][0] = w; for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { area_sz = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w]; cur_ans = INF; Get_Root(to[i], w); len[root] = len[w] + 1; memcpy(anc[root]+1, anc[w], sizeof(int)*len[w]); Build(root, area_sz); } } for (int i=0;i<len[w];i++) rod[w][i] = DIS(w, anc[w][i]); } }NDC; int main() { for (LL vout=0;~scanf("%d",&n);vout=T=0) { memset(head,0,sizeof(head)); memset(ans,0,sizeof(ans)); for (int i=1;i<=n;i++) ori[i] = read(); for (int i=1,u,v,w;i<n;i++) { u = read(); v = read(); w = read(); Add_Edge(u, v, w); } DFS(1, 1); for (int j=1;j<L;j++) { for (int i=1;i<=n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; } } NDC.init(); m = read(); for (int i=1;i<=m;i++) { P[i] = read(); V[i] = read(); } for (int j=0;j<L;j++,vout=0) { memcpy(val,ori,sizeof(ori)); NDC.prework(); for (int i=1;i<=n;i++) { val[i] >>= j; val[i] &= 1; NDC.modify(i, val[i], 1); vout += NDC.query(i, val[i], j); } for (int i=1,p,v;i<=m;i++) { p = P[i]; v = (V[i] >> j) & 1; vout -= NDC.query(p, val[p], j); NDC.modify(p, val[p], -1); NDC.modify(p, v, 1); vout += NDC.query(p, val[p] = v, j); ans[i] += vout; } } for (int i=1;i<=m;i++) printf("%I64d\n",ans[i]); } return 0; }