目录
- 题意
- 思路
- AC_Code
@(hdu 6610)
题意
大概说一下我理解的题意。。。
链接：here
你有\(n\)堆石子，每堆石子有\(a_i\)个石子。游戏规则：\(Alice\)先选择一个大范围\([L,R]\)区间内的石子，\(Bob\)选择一个子区间\([l,r]\)内的石子最终进行游戏。每次至少取走某一堆的一个石子，至多全部取走，无法移动石子者输。\(Alice\)先手，双方足够聪明。问对\(Alice\)的每次选择\([L_i,R_i]\)，\(Bob\)有多少种选择能让\(Alice\)必胜。
还有修改操作，即交换相邻的两堆石子。
思路
Nim博弈，区间异或和，带修改莫队
- \(nim\)博弈结论，区间异或和为\(0\)，则先手必败。
- 问题转换为维护区间异或和为\(0\)的对数，对序列做前缀异或和，莫队维护前缀异或和出现的次数，基本操作。
- 带修改？交换相邻两堆石子，只会对左堆石子的前缀异或和造成影响，即单点修改。
- 参考bzoj_2120数颜色，加一个修改时间戳标记，每次询问前回到当时修改时间戳即可。
- 带修改莫队的块的大小为\(n^{\frac 23}\)较优。
写了很多\(bug\)，嘤嘤嘤，太久没写过莫队， 代码里面一堆\(debug\)操作。。。汗
AC_Code
const int MXN = 1e5 + 5;
const int MXE = 3e6 + 6;
int n, m;
LL ANS[MXN], ans;
int bel[MXN];
struct lp {int l, r, id, tim;
}cw[MXN];
struct lh {int x, oldx, newx;
}tim[MXN];
int vis[MXE], ar[MXN], res[MXN], ret[MXN];
LL L, R;
bool cmp(const lp&a, const lp&b) {if(bel[a.l] != bel[b.l]) return a.l < b.l;if(bel[a.r] != bel[b.r]) {if(bel[a.l] & 1) return a.r < b.r;return a.r > b.r;}return a.tim < b.tim;
}
inline void up(int p) {++ vis[res[p]];ans += vis[res[p]] - 1;
}
inline void down(int p) {-- vis[res[p]];ans -= vis[res[p]];
}
inline void upT(int t) {res[tim[t].x] = tim[t].newx;if(L <= tim[t].x && tim[t].x <= R) {++ vis[tim[t].newx];
// debug(tim[t].oldx, tim[t].newx)ans += vis[tim[t].newx] - 1;-- vis[tim[t].oldx];ans -= vis[tim[t].oldx];}
}
inline void downT(int t) {res[tim[t].x] = tim[t].oldx;if(L <= tim[t].x && tim[t].x <= R) {-- vis[tim[t].newx];ans -= vis[tim[t].newx];++ vis[tim[t].oldx];ans += vis[tim[t].oldx] - 1;}
}
int main() {
#ifndef ONLINE_JUDGEfreopen("/home/cwolf9/CLionProjects/ccc/in.txt", "r", stdin);//freopen("/home/cwolf9/CLionProjects/ccc/out.txt", "w", stdout);
#endif
// int Tim = read();while(~scanf("%d%d", &n, &m)) {int block = (int)pow(n, 2. / 3);//标程和10取了max，不知道为啥int Max = 0;for(int i = 1; i <= n; ++i) {ar[i] = read();bel[i] = (i-1)/block + 1;res[i] = res[i-1] ^ ar[i];ret[i] = res[i];Max = big(Max, ar[i], res[i]);}int change = 0, cnt1 = 1, cnt2 = 0;for(int i = 1, a; i <= m; ++i) {a = read();if(a == 1) {cw[cnt1].l = read(), cw[cnt1].r = read();cw[cnt1].tim = change;cw[cnt1].id = cnt1;++ cnt1;}else {tim[cnt2].x = read();tim[cnt2].oldx = res[tim[cnt2].x];tim[cnt2].newx = (res[tim[cnt2].x + 1] ^ ar[tim[cnt2].x]);res[tim[cnt2].x] = tim[cnt2].newx;Max = big(Max, tim[cnt2].newx);swap(ar[tim[cnt2].x], ar[tim[cnt2].x + 1]);
// debug(cnt2, tim[cnt2].oldx, tim[cnt2].newx)++ change; ++ cnt2;}}for(int i = 0; i <= Max; ++i) vis[i] = 0;sort(cw + 1, cw + cnt1, cmp);L = R = ans = 0;up(0);for(int i = 0; i <= n; ++i) res[i] = ret[i];for(int i = 1, t = 0, f = 1; i < cnt1; ++i) {while(R < cw[i].r) up(++ R);while(R > cw[i].r) down(R --);while(L < cw[i].l - 1) down(L ++);while(L >= cw[i].l) up(-- L);
// for(int j = 0; j <= 7; ++j) printf("%d ", res[j]); printf("\n");
// for(int j = 0; j <= 16; ++j) printf("%d ", vis[j]); printf("\n");for(;t < cw[i].tim; ++ t) upT(t);for(;t > cw[i].tim; -- t) downT(t-1);
// for(int j = 0; j <= 7; ++j) printf("%d ", res[j]); printf("\n");
// for(int j = 0; j <= 16; ++j) printf("%d ", vis[j]); printf("\n");
// printf("*%lld %d %d %d\n", ans, L, R, cw[i].tim);ANS[cw[i].id] = (R - L + 1)*(R - L)/2 - ans;}for(int i = 1; i < cnt1; ++i) write(ANS[i]);}
#ifndef ONLINE_JUDGEcout << "time cost:" << 1.0*clock()/CLOCKS_PER_SEC << "ms" << endl;
#endifreturn 0;
}
