Matrix 【POJ - 2155】【二维线段树+永久化标记】

题目链接

  挺好的一道题，一开始用lazy标记往下推，总是推不出样例的正解，然后就去看了相关博客，发现却确实如此，在这里是无法用lazy标记来层层推的，并且还会出现超内存的情况，所以，便改用了永久化标记来解这道题。

  还有一件是，关于discuss里的讨论区有一块这样的讨论：

1
2 10
C 2 1 2 2
Q 2 3
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

相信很多人是过不了上面的数据的吧！——但是你们就没发现数据本身就错了吗。。。它开的N*N的空间不对啊，怎能询问空间外的点呢？应改为：

正确样例

1
3 10
C 2 1 2 2
Q 2 3
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

那么，我相信大家就都能过了吧。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define efs 1e-6
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1005;
int N, Q;
short int tree[maxN<<2][maxN<<2];
void pushup(int rt, int X0)
{
    tree[X0][rt] = tree[X0][rt<<1] + tree[X0][rt<<1|1];
}
void update_In(int rt, int X0, int l, int r, int ql, int qr)
{
    if(ql == l && qr == r)
    {
        tree[X0][rt]^=1;
        return;
    }
    int mid = (l + r)>>1;
    if(ql>mid) update_In(rt<<1|1, X0, mid+1, r, ql, qr);
    else if(qr<=mid) update_In(rt<<1, X0, l, mid, ql, qr);
    else
    {
        update_In(rt<<1, X0, l, mid, ql, mid);
        update_In(rt<<1|1, X0, mid+1, r, mid+1, qr);
    }
}
void update_Out(int rt, int l, int r, int qlx, int qly, int qrx, int qry)
{
    if(qlx == l && qrx == r)
    {
        update_In(1, rt, 1, N, qly, qry);
        return;
    }
    int mid = (l + r)>>1;
    if(qlx>mid) update_Out(rt<<1|1, mid+1, r, qlx, qly, qrx, qry);
    else if(qrx<=mid) update_Out(rt<<1, l, mid, qlx, qly, qrx, qry);
    else
    {
        update_Out(rt<<1, l, mid, qlx, qly, mid, qry);
        update_Out(rt<<1|1, mid+1, r, mid+1, qly, qrx, qry);
    }
}
int query_In(int rt, int X0, int l, int r, int qy, int sum)
{
    sum^=tree[X0][rt];
    if(l == r) return sum;
    int mid = (l + r)>>1;
    if(qy>mid) return query_In(rt<<1|1, X0, mid+1, r, qy, sum);
    else return query_In(rt<<1, X0, l, mid, qy, sum);
}
int query_Out(int rt, int l, int r, int qx, int qy, int sum)
{
    sum^=query_In(1, rt, 1, N, qy, 0);
    if(l == r) return sum;
    int mid = (l + r)>>1;
    if(qx>mid) return query_Out(rt<<1|1, mid+1, r, qx, qy, sum);
    else return query_Out(rt<<1, l, mid, qx, qy, sum);
}
int main()
{
    int T;  scanf("%d", &T);
    int Cas = 0;
    while(T--)
    {
        if(Cas++ > 0) printf("\n");
        scanf("%d%d", &N, &Q);
        memset(tree, 0, sizeof(tree));
        while(Q--)
        {
            char s[3];
            scanf("%s", s);
            if(s[0] == 'C')
            {
                int lx, ly, rx, ry;
                scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
                update_Out(1, 1, N, lx, ly, rx, ry);
            }
            else
            {
                int x, y;
                scanf("%d%d", &x, &y);
                printf("%d\n", query_Out(1, 1, N, x, y, 0));
            }
        }
    }
    return 0;
}