@NOI模拟2017.06.30

NOI模拟2017.06.30"/>

@NOI模拟2017.06.30

目录

• @description@
• @solution@
  • @part - 1@
  • @part - 2@
• @accepted code@
• @details@

@description@

JOHNKRAM 和 C_SUNSHINE 在玩一个游戏。

游戏规则如下：有若干堆石子，游戏前选定一个正整数 p，JOHNKRAM 先手，两个人轮流操作。定义一次操作是选择某一堆石子，然后拿出其中的 p^k(k∈N) 个石子扔掉，不能操作者输。

C_SUNSHINE 表示判定谁能赢太简单了，于是他放了 n 堆石子，编号为 1∼n。
他每次把编号在某个区间内的石子堆加上若干个石子，或者询问以编号在某个区间内的石子堆进行游戏，是谁胜利。

JOHNKRAM 表示他不会做，于是他来向你求助。

input
第一行三个数 n, q, p，n 表示序列的长度，q 表示接下来操作的次数，p 的意义如题目描述中所说。
接下来一行 n 个数，第 i 个数表示初始时第 i 堆石子的石子数量。
接下来 q 行每行第一个数t表示操作类型，t=0 表示修改，t=1 表示询问。
对于一个修改操作，该行还会有三个数 l, r, x，表示把 [l…r] 的所有石子堆加上 x 个石子（博主注：x 为正数且属于 int 范围）。
对于一个询问操作，该行还会有两个数 l, r，表示询问以 [l…r] 的所有石子堆进行游戏是谁胜。

保证 1 <= n, q, p, 每堆石子的初始数量 <= 10^5。

output
对于每一个询问，如果 JOHNKRAM 胜利输出 1，否则输出 0。

sample input
10 9 3
2 6 2 5 8 7 4 3 4 1
1 1 10
0 5 7 15
1 1 3
0 3 9 11
1 3 7
0 4 5 53
0 1 2 26
1 6 10
1 4
sample output
0
0
0
1
0

@solution@

@part - 1@

通过 对sg函数打表 简单推导可得：

（1）当 p 为奇数时，sg函数循环节长度为 2，循环节为 01。即：
当 x % 2 == 0 时，sg[x] = 0。
当 x % 2 == 1 时，sg[x] = 1。

（2）当 p 为偶数时，sg函数循环节长度为 (p+1)，循环节为 010101……01012。即：
当 x % (p+1) == p 时，sg[x] = 2。
当 (x % (p+1)) % 2 == 1 时，sg[x] = 1。
当 x % (p+1) != p 且 (x % (p+1)) % 2 == 0 时，sg[x] = 0。

简要（感性地）证明一下吧：
首先我们可以发现，当 x < p 时，只能从 sg[x-1] 到 sg[x]，故一定形如 010101……
当 p 为奇数时，p^k 肯定也为奇数，即我们总是只能从偶数转移到奇数，奇数转移到偶数，故只能是 010101……
当 p 为偶数时，可以发现 p^k = (-1)^k (mod p+1)，于是我们可以在 mod p+1 的意义下从 x+1 与 x-1 转移到 x。故当 x % (p+1) == p 时，sg[x] 只能等于 2。
于是可以得证。

@part - 2@

根据 sg 函数应用于博弈论的结论，我们必须在询问时求出区间 [l, r] 中 sg 函数的异或和才能判定胜负。
奇数很好办，写一个支持区间反转，统计区间中 1 的个数的线段树即可。

考虑偶数。我们需要在支持模意义下区间加操作时，至少可以询问一个区间内值等于 p 的个数（即 sg[x] = 2 的个数）。
我不知道线段树能不能搞。这显然是分块来搞。修改时整块加法标记，散块暴力重构；查询时整块通过加法标记寻找，散块暴力遍历。
再考虑求出一个区间内值为奇数的个数（即 sg[x] = 1 的个数）。考虑重构时储存值为奇数与值为偶数的两个有序数列，这样整块在加法标记下，新奇数序列必然是原奇数序列的某后缀接上原偶数序列的某前缀，或反过来原偶数序列的某后缀接上原奇数序列的某前缀。新偶数序列同理。
于是我们根据加法标记二分查找一下，就可以求出 sg[x] = 1 的个数了。

显然奇数也可以分块来搞，所以我们就可以不用写线段树了。

总复杂度 O(nsqrt(n)log n)，有些卡但开了O2大概3s能过。

标算给出了一个 O(nsqrt(nlog n)) 的算法，不过太难写了。
大概就是在重构时充分利用原奇偶序列的有序性，归并两个有序数列可以在线性时间内完成，于是可以线性时间完成重构。然后再重新调整块的大小使询问与修改的复杂度平衡。
这个常数说不定还不如上面那个算法……

@accepted code@

#include<cstdio>
#include<algorithm>
using namespace std;
#define lb lower_bound
const int BLOCK = 320;
const int MAXN = 100000;
int le[MAXN/BLOCK + 5], ri[MAXN/BLOCK + 5], add[MAXN/BLOCK + 5], num[MAXN + 5];
int arr[2][MAXN/BLOCK + 5][BLOCK + 5], siz[2][MAXN/BLOCK + 5];
int n, q, p, bcnt;
int a[MAXN + 5];
void rebuild(int x) {siz[0][x] = siz[1][x] = 0;for(int i=le[x];i<=ri[x];i++)arr[a[i]&1][x][++siz[a[i]&1][x]] = a[i];sort(arr[0][x] + 1, arr[0][x] + siz[0][x] + 1);sort(arr[1][x] + 1, arr[1][x] + siz[1][x] + 1);
}
void build() {bcnt = (n-1)/BLOCK + 1;for(int i=0;i<n;i++) {if( i % BLOCK == 0 )le[i/BLOCK+1] = ri[i/BLOCK+1] = i;else ri[i/BLOCK+1]++;num[i] = i/BLOCK+1;}for(int i=1;i<=bcnt;i++)rebuild(i);
}
void pushdown(int x) {for(int i=le[x];i<=ri[x];i++)a[i] = (a[i] + add[x])%(p+1);add[x] = 0;
}
int fun(int x) {if( x == p ) return 2;else return (x&1);
}
int main() {freopen("right.in", "r", stdin);freopen("right.out", "w", stdout);scanf("%d%d%d", &n, &q, &p);if( p % 2 == 1 ) p = 1;for(int i=0;i<n;i++)scanf("%d", &a[i]), a[i] %= (p+1);build();for(int i=1;i<=q;i++) {int tp; scanf("%d", &tp);if( tp == 0 ) {int l, r, x; scanf("%d%d%d", &l, &r, &x), l--, r--, x %= (p+1);if( num[l] == num[r] ) {pushdown(num[l]);for(int i=l;i<=r;i++)a[i] = (a[i] + x)%(p+1);rebuild(num[l]);}else {for(int i=num[l]+1;i<=num[r]-1;i++)add[i] = (add[i] + x)%(p+1);pushdown(num[l]);for(int i=l;i<=ri[num[l]];i++)a[i] = (a[i] + x)%(p+1);rebuild(num[l]);pushdown(num[r]);for(int i=le[num[r]];i<=r;i++)a[i] = (a[i] + x)%(p+1);rebuild(num[r]);}}else {int l, r, ans = 0; scanf("%d%d", &l, &r), l--, r--;if( num[l] == num[r] ) {for(int i=l;i<=r;i++)ans ^= fun((a[i] + add[num[i]])%(p+1));}else {for(int i=l;i<=ri[num[l]];i++)ans ^= fun((a[i] + add[num[i]])%(p+1));for(int i=le[num[r]];i<=r;i++)ans ^= fun((a[i] + add[num[i]])%(p+1));for(int i=num[l]+1;i<=num[r]-1;i++) {int t1 = p-add[i];int x = upper_bound(arr[t1&1][i]+1, arr[t1&1][i]+siz[t1&1][i]+1, t1) - arr[t1&1][i];int y = lower_bound(arr[t1&1][i]+1, arr[t1&1][i]+siz[t1&1][i]+1, t1) - arr[t1&1][i];int z = upper_bound(arr[t1&1^1][i]+1, arr[t1&1^1][i]+siz[t1&1^1][i]+1, t1) - arr[t1&1^1][i];if( (x-y) & 1 ) ans ^= 2;if( p != 1 && ((z-1+siz[t1&1][i]-x+1) & 1) ) ans ^= 1;}}puts(ans ? "1" : "0");}}
}
/*
以下是打表用程序：
#include<cstdio>
const int MAXN = 100;
int sg[MAXN + 5];
bool tag[MAXN + 5];
int main() {int p; scanf("%d",Q &p);sg[0] = 0;for(int i=1;i<=MAXN;i++) {for(int j=0;j<=MAXN;j++)tag[j] = false;tag[sg[i-1]] = true;if( p != 1 ) {int x = p;while( x <= i ) {tag[sg[i-x]] = true;x *= p;}}for(int j=0;;j++)if( !tag[j] ) {sg[i] = j;break;}}for(int i=0;i<=MAXN;i++)printf("%d : %d\n", i, sg[i]);
}
*/

@details@

康复计划 - 9。

当我对博弈论一筹莫展时，旁边的 zxb 大佬小声地提醒我说：“打表”。突然就幡然醒悟了。
这场比赛的 T2 我还没写，因为我还没有理解随机状况下标算时间复杂度怎么来的。以后慢慢填坑（咕咕咕）。

转载于:.html