Codeforces 869E

发表于 |

题目

在一个$N\times M$的网格图上，有$Q$个操作。操作分三种：（1）将给定的矩形区域的边界围上围栏。（2）将给定的矩形区域的边界的围栏去掉。（3）问给定的两个格子有没有不穿过围栏的路。

数据范围

$1\le N,M \le 2500 \quad 1\le q \le 10^5$

做法

切入点：两个点$a,b$之间有不穿过围栏的路当且仅当包围$a$的围栏的集合和包围$b$的围栏的集合完全相等。

为了判断包围某个点的围栏集合是否相等，可以给每个围栏一个随机的值。操作1和操作2就变成了矩形区域的加、减（抑或也可以），操作3就是查询某个点的值。区间修改，单点查询，可以转化为：单点修改，区间查询。这样用二维树状数组就行。

为了提高成功的概率，可将每个围栏的int值变为pair<int, int>。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pii2;
const int MAX_N = 2500 + 5;
struct BIT
{
  pii dat[MAX_N][MAX_N];
  int lowbit(int x) {return x & -x;}
  void add(int x, int y, pii v)
  {
    for (int i = x; i < MAX_N; i += lowbit(i)) {
      for (int j = y; j < MAX_N; j += lowbit(j)) {
        dat[i][j].first += v.first;
        dat[i][j].second += v.second;
      }
    }
  }
  pii sum(int x, int y)
  {
    pii s;
    for (int i = x; i > 0; i -= lowbit(i)) {
      for (int j = y; j > 0; j -= lowbit(j)) {
        s.first += dat[i][j].first;
        s.second += dat[i][j].second;
      }
    }
    return s;
  }
};
BIT bit;
int N, M, Q;
map<pii2, pii> mp;
int main()
{
  srand(time(NULL));
  scanf("%d%d%d", &N, &M, &Q);
  while (Q--) {
    int t, r1, c1, r2, c2;
    scanf("%d%d%d%d%d", &t, &r1, &c1, &r2, &c2);
    if (t == 1) {
      pii add = pii(rand(), rand());
      pii del = pii(-add.first, -add.second);
      mp[pii2(pii(r1, c1), pii(r2, c2))] = add;
      bit.add(r1, c1, add);
      bit.add(r2 + 1, c2 + 1, add);
      bit.add(r2 + 1, c1, del);
      bit.add(r1, c2 + 1, del);
    } else if (t == 2) {
      pii add = mp[pii2(pii(r1, c1), pii(r2, c2))];
      pii del = pii(-add.first, -add.second);
      bit.add(r1, c1, del);
      bit.add(r2 + 1, c2 + 1, del);
      bit.add(r2 + 1, c1, add);
      bit.add(r1, c2 + 1, add);
    } else {
      pii v1 = bit.sum(r1, c1);
      pii v2 = bit.sum(r2, c2);
      if (v1 == v2) {
        puts("Yes");
      } else {
        puts("No");
      }
    }
  }
  return 0;
}