Description
Solution
考虑Dp，设Dp[i] 表示当我们从前面跳跃到i时，他是必胜还是必败。
那么(Dp[i] = Min(Dp[j], !(Dp[i + 1] = 1~ &&~(a[i] - 1)~mod~2 =0))， j in [i + 1, i + m])
表示如果能跳的地方是必败态， 那么我们就跳跃过去，这样对方执子时一定是必败的
如果后面全都是必胜态，那么我们只有当A[i] 为奇数时， 才能强迫对方走到必胜态。这是O(n)的
考虑维护一个区间上的函数，函数F(x)表示一个状态(用0表示败，1表示胜，那么这个状态就有m位， 这个函数其实是数学中的映射）经过了这一个区间后会变成什么样子， 那么我们建立线段树来维护这个映射。当两个区间pushup的时候就直接枚举所有的状态X, 那么Front_F(Back_F(x)) 就是x所对应的状态。
考虑修改， 如果是偶数， 我们直接跳过，因为它不会影响区间任何一个数的奇偶性。那么加一个奇数就是把这个区间整体奇偶性改变。 那么我们只要维护一个新的线段树。 其上的区间与当前区间一一对应，代表当前区间整体改变了奇偶性的值，那么只需要在修改之后交换就可以了。
整体复杂度(O(2^m(n + q) log n))
Inspiration
在作博弈题目时，由于每个点都是必胜或者必败, 可以考虑把跳跃看成转移,状态就直接设跳跃到哪一步, 然后当前节点的特有的值是多少, 因为是轮流取数, 我们可以考虑奇偶性进行转移。
因为要对一个区间进行维护，而且状态数特别少((2 ^ m)), 所以可以直接枚举每个Dp状态,建立一个函数,然后利用函数嵌套快速转移, 类似这种嵌套转移的东西还有矩阵快速幂。
其实奇偶性的情况特别少, 像这样的"特别少"的情况还有二进制中的(0,1), 三进制中的(0, 1, 2)，以及后5位的状态等，对于这种状态特别少的情况，我们可以算出每个状况改变之后对应的状态。然后在修改时直接转移。
Update 20181202: 其实这样很像动态DP。
坑： 听说有(O(m(n + q)log n))的做法？
Code
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
char ch = getchar();
int x = 0, flag = 1;
for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
typedef std :: vector<int> seq;
const int Maxn = 2e5 + 9, Maxm = 6, MaxLen = 1 << Maxm;
static int n, m, q, a[Maxn], allMask;
seq inital(int val) {
seq res(1 << m);
rep (i, 0, (1 << m) - 1) {
if (i != (1 << m) - 1 || !(val & 1)) res[i] = (i >> 1) + (1 << (m - 1));
else res[i] = i >> 1;
}
return res;
}
seq produce(seq input, seq func) {
seq res(1 << m);
rep (i, 0, (1 << m) - 1) res[i] = func[input[i]];
return res;
}
namespace SGMTtree {
seq tree[Maxn << 2], xorBak[Maxn << 2]; int add[Maxn << 2];
#define lc(rt) ((rt) << 1)
#define rc(rt) ((rt) << 1 | 1)
#define ls rt << 1, l, mid
#define rs rt << 1 | 1, mid + 1, r
void pushup(int rt) {
tree[rt] = produce(tree[rc(rt)], tree[lc(rt)]);
xorBak[rt] = produce(xorBak[rc(rt)], xorBak[lc(rt)]);
}
void pushdown(int rt) {
if (add[rt]) {
add[lc(rt)] ^= 1; std :: swap(xorBak[lc(rt)], tree[lc(rt)]);
add[rc(rt)] ^= 1; std :: swap(xorBak[rc(rt)], tree[rc(rt)]);
add[rt] = 0;
}
}
void build(int rt, int l, int r) {
if (l == r) {
tree[rt] = inital(a[l]), xorBak[rt] = inital(a[l] ^ 1);
return ;
}
int mid = (l + r) >> 1;
build(ls), build(rs);
pushup(rt);
}
void modify(int rt, int l, int r, int p, int q) {
if (p <= l && r <= q) {
add[rt] ^= 1; std :: swap(tree[rt], xorBak[rt]);
return ;
}
int mid = (l + r) >> 1; pushdown(rt);
if (q <= mid) modify(ls, p, q);
else if (p >= mid + 1) modify(rs, p, q);
else modify(ls, p, q), modify(rs, p, q);
pushup(rt);
}
seq query(int rt, int l, int r, int p, int q) {
if (p <= l && r <= q) return tree[rt];
int mid = (l + r) >> 1; pushdown(rt);
if (q <= mid) return query(ls, p, q);
else if (p >= mid + 1) return query(rs, p, q);
else return produce(query(rs, p, q), query(ls, p, q));
}
#undef lc
#undef rc
#undef ls
#undef rs
}
void init() {
n = read(), m = read(), q = read();
rep (i, 1, n) a[i] = read();
allMask = (1 << m) - 1, SGMTtree :: build(1, 1, n);
}
void solve() {
rep (i, 1, q) {
int opt = read();
if (opt == 1) {
int l = read(), r = read(), v = read();
if (v & 1) SGMTtree :: modify(1, 1, n, l, r);
}
if (opt == 2) {
int l = read(), r = read();
seq ans = SGMTtree :: query(1, 1, n, l, r);
printf("%d
", 1 + (((ans[(1 << m) - 1] >> (m - 1)) & 1) ^ 1));
}
}
}
int main() {
init();
solve();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return 0;
}