Codeforces 869E The Untended Antiquity(二维树状数组)解题报告

2017-10-17 3,174 次浏览 解题报告

解题思路

很巧妙的一道题。我们可以考虑用二维树状数组去做,新建障碍视为在二位数组中对一个矩形区域增加一个值,而移除障碍就是减掉这个值,查询就是判断两个点的值是否一致。

那么问题来了,这个值要加多少呢?这个题给了很巧妙的做法,就是每次随机一个数(可以去 Editorial 看一下证明)。当然其他不会导致重复的生成方式也是可以的。

参考代码

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const long long p = 3;
const int MAX = 2500;

int n, m, q, t, x1, y1, x2, y2;
long long c[MAX+2][MAX+2];
map<pair<pair<int, int>, pair<int, int> >, long long> mp;

int LowBit(int x) {
    return x&(-x);
}

void Add(int x, int y, long long v) {
    for(int i=x; i<=n; i+=LowBit(i)) {
        for(int j=y; j<=m; j+=LowBit(j)) {
            c[i][j] += v;
        }
    }
}

long long Sum(int x, int y) {
    long long sum = 0;
    for(int i=x; i>=1; i-=LowBit(i)) {
        for(int j=y; j>=1; j-=LowBit(j)) {
            sum += c[i][j];
        }
    }

    return sum;
}

int main(int argc, char const *argv[]) {
    scanf("%d %d %d", &n, &m, &q);
    long long val = 1;
    while(q--) {
        scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);
        if(t == 1) {
            val *= p;
            mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))] = val;
            Add(x1, y1, val);
            Add(x1, y2+1, -val);
            Add(x2+1, y1, -val);
            Add(x2+1, y2+1, val);
        }
        if(t == 2) {
            long long tmp = mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))];
            Add(x1, y1, -tmp);
            Add(x1, y2+1, tmp);
            Add(x2+1, y1, tmp);
            Add(x2+1, y2+1, -tmp);
        }
        if(t == 3) {
            if(Sum(x1, y1) == Sum(x2, y2))
                printf("Yes\n");
            else printf("No\n");
        }
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/10/17/codeforces-869e.dream

还不快抢沙发

添加新评论