BZOJ 4333: JSOI2012 智者的考验

Description

公元1371年，太祖下令在北极阁上大建庙宇，短短几年，鸡笼山上便建成了帝王庙、关公庙、真武庙、功臣庙、蒋王庙、都城隍庙、卞壶庙、忠烈庙、刘越王庙、曹武惠王庙共十座庙宇，统称为“十庙”。

后来，为了方便人们来鸡笼山进香礼佛，太祖下令疏通了鸡笼山下已淤塞多年的潮沟。于是，便有了“进香河”。

然而并不是所有人都可以来鸡笼山的，太祖在进香河上修建了一座石桥，中间悬挂了一块高Rx宽Ry的机关格图（如下图所示）。所有格子都是活动可翻转的，一面是白色，一面是黑色，这里我们用0表示白色，用1表示黑色。初始情况下，所有格子都是白色面朝前的。有Rx+Ry个机关按钮，对应Rx行和Ry列。一个按钮一旦触发，就会引发对应的一行或一列的格子同时翻转。

同时，善于识天象的谋臣刘基给出了一种黑白状态，称之为“厄运星”。每一位过往前去鸡笼山的人都需要触发且只触发一个按钮，触发后，如果来访者呈“厄运星”形状，则不允许通过。

每一天要来鸡笼山的人数N是事先就知道的，同时天朝神威浩荡，每一位来者一开始总是有很大概率触发编号为1的按钮，我们不妨用数列A1,A2,…,AN来表示，问题保证了初始时候的A数列全为1。同时在整个问题中，Ai满足1<=Ai<=Rx+Ry。太祖很关心那些不允许去鸡笼山的人数。于是他时不时就会询问关于“某一段时间内会有多少人不能通过“厄运星”的考验”。然而那些前来鸡笼山的文人墨客并不愿意如此单一的操作。来访者有可能会突然决定修改自己的触发按钮。更麻烦的情况，结伴而来的连续若干人会突然决定修改触发按钮并且都去触发同一个按钮。

现在这麻烦的问题交给了你。

后记：

等到了乾隆时期，一位人称纪昀的才子来访此地，告诉了人们一套方法，从此再也没有人会不被允许通过了。久而久之，鸡笼山烟火依旧，然这机关格图的故事便渐渐失传了。直到今天才再一次被世人所了解。

Input

输入文件第一行有2个数字Rx和Ry表示机关格图的高和宽（如图所示）。之后Rx行每一行Ry个数字，描述了“厄运星”形状，每一个数字都满足非0即1.

之后一行有两个数字，分别为N和M，表示人数和询问修改的次数。

之后M行，对应M次询问或修改。每一行先有一个数字t：

若t为0：之后有2个数字d和x，表明将Ad修改为x。

若t为1：之后有2个数字l和r，表明询问第l个人到第r个人中有多少人触发按钮后会出现“厄运星”形状，从而无法通过。

若t为2：之后有3个数字l,r和x，表面将Al,Al+1,…,Ar-1,Ar都修改为x。

Output

对于每一次询问(即t为1的情况)，输出单独一行，一个整数描述了在区间[l,r]中满足要求的人数。

Sample Input

Sample Output

HINT

对于100%的数据，N<=1000000，M<=120000，Rx<=2，Ry<=3。

应上传者要求，此题不公开，如有异议，请提出.

Source

JSOI 2012

Solution

线段树+状态压缩

这道题考场上GG的原因是没有想到好的方法处理修改操作对后面的影响。

其实对于一段区间我们只需要知道只做这一段之后的答案是多少然后考虑左边区间对这个区间贡献即可。

线段树维护3个标记：right、fill、cnt[64]表示做完这一段之后的状态，这一段的覆盖标记和每种状态出现次数。

显然这样会炸掉。。

考虑到合法的0/1矩阵是有限的，算一算只有16种，于是cnt数组可以缩小4倍

然而这样还是卡不过去内存，我们不用位移寻找左右儿子，而是另开数组记录就好了，空间减少了一倍，非常优美。

复杂度\( O(2^{Rx+Ry-1} M \log N) \)

其实这道题分块也能拿不少分的，看怎么写了。。。

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000002;
int rt, n, m, R, Q, w, b[4][4], qres, cnt[maxn*2][16], id[64], tag[maxn*2], ri[maxn*2], ty[7], tot, iid[16], lc[maxn*2], rc[maxn*2], tol;
inline int getint() {
    register int r = 0; register bool b = true; register char c = getchar();
    while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
    while ('0' <= c && c <= '9') {r = (r<<3)+(r<<1)+(c - '0'); c = getchar();}
    if (b) return r;
    return -r;
}

void build(int &now, int l, int r) {
    now = ++tol;
    if (l < r) {
        int mid = (l + r) >> 1;
        build(lc[now], l, mid);
        build(rc[now], mid+1, r);
    }
}

inline void Fill(int now, int t, int len) {
    tag[now] = t;
    for (int i = 0; i < tot; ++i) cnt[now][i] = 0;
    if (len & 1) {
        cnt[now][id[ty[t]]] = (len+1)/2;
        cnt[now][id[0]] = len/2;
        ri[now] = ty[t];
    } else {
        cnt[now][id[ty[t]]] = cnt[now][id[0]] = len/2;
        ri[now] = 0;
    }
}

inline void pushdown(int now, int l, int mid, int r) {
    Fill(lc[now], tag[now], mid-l+1);
    Fill(rc[now], tag[now], r-mid);
    tag[now] = 0;
}

inline void pushup(int now) {
    for (int i = 0; i < tot; ++i) cnt[now][i] = cnt[lc[now]][i] + cnt[rc[now]][id[iid[i]^ri[lc[now]]]];
    ri[now] = ri[lc[now]] ^ ri[rc[now]];
}

void change(int now, int l, int r, int ll, int rr, int t) {
    if (ll <= l && r <= rr) Fill(now, t, r-l+1);
    else {
        int mid = (l + r) >> 1;
        if (tag[now] != 0) pushdown(now, l, mid, r);
        if (ll <= mid) change(lc[now], l, mid, ll, rr, t);
        if (rr > mid) change(rc[now], mid+1, r, ll, rr, t);
        pushup(now);
    }
}

void query(int now, int l, int r, int ll, int rr, int S) {
    if (ll <= l && r <= rr) qres += cnt[now][id[S]];
    else {
        int mid = (l + r) >> 1;
        if (tag[now] != 0) pushdown(now, l, mid, r);
        if (ll <= mid) query(lc[now], l, mid, ll, rr, S);
        if (rr > mid) query(rc[now], mid+1, r, ll, rr, S^ri[lc[now]]);
    }
}

int main() {
    n = getint(); m = getint();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            w = w^(getint()<<(i*m+j));
    int tmp;
    for (int i = 0; i < n; ++i) {
        tmp = 0;
        for (int j = 0; j < n; ++j) for (int k = 0; k < m; ++k) b[j][k] = 0;
        for (int j = 0; j < m; ++j) b[i][j] = 1;
        for (int j = 0; j < n; ++j) for (int k = 0; k < m; ++k) tmp = tmp^(b[j][k]<<(j*m+k));
        ty[i] = tmp;
    }
    for (int i = 0; i < m; ++i) {
        tmp = 0;
        for (int j = 0; j < n; ++j) for (int k = 0; k < m; ++k) b[j][k] = 0;
        for (int j = 0; j < n; ++j) b[j][i] = 1;
        for (int j = 0; j < n; ++j) for (int k = 0; k < m; ++k) tmp = tmp^(b[j][k]<<(j*m+k));
        ty[i+n] = tmp;
    }
    int mx = 1<<(n+m), sta;
    for (int i = 0; i < mx; ++i) {
        sta = 0;
        for (int j = 0; j < n+m; ++j) if (i&(1<<j)) sta ^= ty[j];
        if (id[sta] == 0) id[sta] = ++tot;
    }
    R = getint(); Q = getint();
    for (int i = n+m; i >= 1; --i) ty[i] = ty[i-1];
    for (int i = 0; i < 64; ++i) {
        --id[i];
        if (id[i] != -1) iid[id[i]] = i;
    }
    build(rt, 1, R);
    Fill(rt, 1, R);
    int op, x, y;
    while (Q--) {
        op = getint(); x = getint(); y = getint();
        if (op == 0) change(rt, 1, R, x, x, y);
        else if (op == 1) { qres = 0; query(rt, 1, R, x, y, w); printf("%d\n", qres); }
        else change(rt, 1, R, x, y, getint());
    }
}