P5152

tcl_tcl_tcl · 2020-03-15 10:34:47 · 题解

蒟蒻的第一篇题解

(update:二维数组区间修改模板中有地方有误，已更正) 一位题解重度依赖患者由于没有题解被迫营业的悲惨经历

拿到题的的第一步当然是查看题解审题。相信在座的神犇们都已经看出来了，(我真的没有看算法标签)， 这题是一道树状数组的题，在刷完两道树状数组的模板题后，直接开始了强转一维树状数组的暴力解法，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2500;
const int K = 31;
int x0, Y0, x1, Y1;
int m, n, k;
int sum1[N*N + 1][K], sum2[N*N + 1][K];
char op;
int lowbit(int x) {
    return x & -x;
}
void update(int i, int ak, int bk) {
    int x = i;
    while (i <= n * n) {
        sum1[i][ak] += bk;
        sum2[i][ak] += (x - 1)*bk;
        i += lowbit(i);
    }
}
int getsum(int i, int k) {
    int x = i;
    int ans = 0;
    while (i != 0) {
        ans += (x * sum1[i][k] - sum2[i][k]);
        i -= lowbit(i);
    }
    return ans;
}
int main()
{
    cin >> n >> m;
    while (m--) {
        cin >> op;
        if (op == 'P') {
            cin >> x0 >> Y0 >> x1 >> Y1 >> k;
            while (k--) {
                int ak, bk;
                cin >> ak >> bk;
                if (bk & 1) {
                    for (int y = Y0; y <= Y1; y++) {
                        update(x0 + (y - 1) * n, ak, bk);
                        update(x1 + (y - 1) * n + 1, ak, -bk);
                    }
                }
            }
        }
        if (op == 'Q') {
            cin >> x0 >> Y0 >> x1 >> Y1;
            for (int i = 1; i <= 30; i++)
            {
                int sum = 0;
                for (int y = Y0; y <= Y1; y++) {
                    sum += getsum(x1 + (y - 1) * n, i) - getsum(x0 + (y - 1) * n - 1, i);
                }
                cout << ((sum % 2) + 1);
            }
            cout << endl;
        }
    }
    return 0;
}

结果当然是MLE+TLE大餐(其实三个点真香)，显然此题的正解不是 强转一维树状数组，而是二维树状数组，在分析开始我先介绍一下二维数组的三种题型以及对应的模板代码。

二维树状数组

1.单点修改+区间查询

//while用for写也是一样的
void update(int x, int y, int z){
    int _y = y;
    while(x <= n){
        y = _y;
        while(y <= n)
            tree[x][y] += z, y += lowbit(y);
        x += lowbit(x);
    }
}
void query(int x, int y){
    int ans = 0, _y = y;
    while(x){
        y = _y;
        while(y)
            ans += tree[x][y], y -= lowbit(y);
        x -= lowbit(x);
    }
}

2.区间修改+单点查询

类似于一维的处理，可以设差分数组

模板如下：

//用万能头的选手不要使用x1,y1
void update(int x, int y, int z){ 
    int _y = y;
    while(x <= n){
        y = _y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void range_update(int x1, int y1, int x2, int y2, int val){
    update(x1, y1, val);
    update(x1, y2 + 1, -val);
    update(x2 + 1, y1, -val);
    update(x2 + 1, y2 + 1, val);
}
void ask(int x, int y){
    int ans = 0, _y = y;
    while(x){
        y = _y;
        while(y)
            ans += tree[x][y], y -= lowbit(y);
        x -= lowbit(x);
    }
}

3.区间修改+区间查询

类比一维树状数组的区间修改查询，(x,y)的前缀和：

其中,d[1][1]出现了x*y次,d[1][2]出现了x*(y-1)次 于是

展开得

那么我们需要维护四个树状数组：

代码模板如下：

void update(int x, int y, int val) {
    for (int X = x; X <= n; X += lowbit(X))
        for (int Y = y; Y <= m; Y += lowbit(Y)) {
            t1[X][Y] += val;
            t2[X][Y] += val *x;
            t3[X][Y] += val * y;
            t4[X][Y] += val * x * y;
        }
}
void range_update(int xa, int ya, int xb, int yb, int val) { 
    update(xa, ya, val);
    update(xa, yb + 1, -val);
    update(xb + 1, ya, -val);
    update(xb + 1, yb + 1, val);
}
int query(int x, int y) {
    int res = 0;
    for (int i = x; i; i -= i & -i)
        for (int j = y; j; j -= j & -j)
            res += (x + 1) * (y + 1) * t1[i][j]
            - (y + 1) * t2[i][j]
            - (x + 1) * t3[i][j]
            + t4[i][j];
    return res;
}
int range_query(int xa, int ya, int xb, int yb) {
    return query(xb, yb) - query(xb, ya - 1) - query(xa - 1, yb) + query(xa - 1, ya - 1);
}

题目分析

很明显这道题属于以上分析的第三种题型区间修改+区间查询，套用模板可得以下代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2500 + 1;
const int K = 31;
int t1[N][N][K], t2[N][N][K], t3[N][N][K], t4[N][N][K]; //第三个维度表示种类
int m, n, k;
int X1, Y1, X2, Y2;
int ak, bk;
char op;
int lowbit(int x)
{
    return x & -x;
}
void update(int x, int y, int k, int p)
{
    for (int X = x; X <= n; X += lowbit(X))
        for (int Y = y; Y <= n; Y += lowbit(Y)) {
            t1[X][Y][k] += p;
            t2[X][Y][k] += p * x;
            t3[X][Y][k] += p * y;
            t4[X][Y][k] += p * x * y;
        }
}
void range_update(int xa, int ya, int xb, int yb, int k, int p)
{
    update(xa, ya, k, p);
    update(xa, yb + 1, k ,-p);
    update(xb + 1, ya, k, -p);
    update(xb + 1, yb + 1, k, p);
}
int query(int x, int y, int k)
{
    int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            ans += (x + 1)*(y + 1)*t1[i][j][k]
            - (y + 1)*t2[i][j][k]
            - (x + 1)*t3[i][j][k]
            + t4[i][j][k];
    return ans;
}
int range_query(int xa, int ya, int xb, int yb, int k)
{
    return query(xb, yb, k) - query(xb, ya - 1, k) - query(xa - 1, yb, k) + query(xa - 1, ya - 1, k)  ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    while (m--) {
        cin >> op;
        if (op == 'P')
        {
            cin >> X1 >> Y1 >> X2 >> Y2 >> k;
            while (k--)
            {
                cin >> ak >> bk;
                range_update(X1, Y1, X2, Y2, ak, bk);
            }
        }
        if (op == 'Q')
        {
            cin >> X1 >> Y1 >> X2 >> Y2;
            for (int i = 1; i <= 30; i++)
                cout<<((range_query(X1, Y1, X2, Y2, i)%2)+1);
            cout << endl;
        }
    }
    return 0;
}

很抱歉，这次30分也没有，本地会直接报错：LNK1248 映像大小(BA135000)超过允许的最大大小(80000000)，(通过查阅资料)仔细分析发现这和强转一维得到大小没有变化可能甚至还超过。观察到题目仅有最多30种物件，于是我们考虑状态压缩，用每一位表示物品奇偶性(0表示偶数个，1表示奇数个)，自然而然地就会想到异或运算。完整AC代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2500 + 1;
const int K = 5;
unsigned int t1[N][N], t2[N][N], t3[N][N], t4[N][N];
int m, n, k;
int X1, Y1, X2, Y2;
int ak, bk;
unsigned int ans, val;
char op;
int lowbit(int x)
{
    return x & -x;
}
void update(int x, int y, unsigned int p)
{
    for (int X = x; X <= n; X += lowbit(X))
        for (int Y = y; Y <= n; Y += lowbit(Y)) {
            t1[X][Y] ^= p;
            t2[X][Y] ^= ((y) & 1) ? p : 0;  //如果(y-1)是偶数，乘以任何数也是偶数，对结果不影响
            t3[X][Y] ^= ((x) & 1) ? p : 0;
            t4[X][Y] ^= ((x)&(y) & 1) ? p : 0;
        }
}
void range_update(int xa, int ya, int xb, int yb, int p)
{
    update(xa, ya, p);
    update(xa, yb + 1 ,p);
    update(xb + 1, ya, p);
    update(xb + 1, yb + 1, p);
}
unsigned int query(int x , int y)
{
    unsigned int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            ans ^= (((x + 1)&(y + 1)&1)?t1[i][j]:0)^
            (((x + 1) & 1) ? t2[i][j] : 0) ^
            (((y + 1) & 1) ? t3[i][j] : 0) ^
            t4[i][j];
    return ans;
}
unsigned int range_query(int xa, int ya, int xb, int yb)
{
    return query(xb, yb) ^ query(xb, ya - 1) ^ query(xa - 1, yb) ^ query(xa - 1, ya - 1)  ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    while (m--) {
        cin >> op;
        if (op == 'P')
        {
            val = 0;
            cin >> X1 >> Y1 >> X2 >> Y2 >> k;
            while (k--)
            {
                cin >> ak >> bk;
                if (bk & 1)
                    val ^= (1 << ak);//只有奇数个有更新的必要，偶数个不影响结果
            }
            range_update(X1, Y1, X2, Y2, val);
        }
        if (op == 'Q')
        {
            cin >> X1 >> Y1 >> X2 >> Y2;
            ans = range_query(X1, Y1, X2, Y2);
            for (int i = 1; i <= 30; i++)
            {
                ans = ans >> 1;
                if (ans & 1)
                    cout << 2;
                else
                    cout << 1;
            }
                cout << endl;
        }
    }
    return 0;
}

看在我码的辛苦这是第一篇该题的详细题解的份上，各位大佬何不留个赞再走？