백준17773 Fortune Telling

작성일 | In

문제 링크

  • http://icpc.me/17773

문제 출처

  • 2011/2012 JOISC Day3 1번

사용 알고리즘

  • 스위핑

풀이

좌표압축/스위핑 연습 문제입니다.

각 쿼리는 $(x_1, y_1)$부터 $(x_2, y_2)$까지의 직사각형 영역에 XOR 연산을 하는 것이고, Prefix XOR의 관점에서 생각해보면 $x_1$ 시점에 구간 $[y_1, y_2]$에 XOR을 하고, $x_2+1$ 시점에 다시 구간에 $[y_1, y_2]$에 XOR 연산을 하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
constexpr int SZ = 1 << 19;

int N, M, Q, A[101010], B[101010], C[101010], D[101010], W[SZ << 1], T[SZ << 1], L[SZ << 1];
vector<int> X, Y;
vector<PII> Qry[303030];

void Push(int node, int s, int e){
    if(!L[node]) return;
    T[node] = W[node] - T[node];
    if(s != e) L[node<<1] ^= 1, L[node<<1|1] ^= 1;
    L[node] = 0;
}
void Update(int l, int r, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] ^= 1; Push(node, s, e); return; }
    int m = s + e >> 1;
    Update(l, r, node<<1, s, m); Update(l, r, node<<1|1, m+1, e);
    T[node] = T[node<<1] + T[node<<1|1];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int i=1; i<=Q; i++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        X.push_back(A[i]); X.push_back(B[i]); X.push_back(B[i] + 1);
        Y.push_back(C[i]); Y.push_back(D[i]); Y.push_back(D[i] + 1);
    }
    compress(X); compress(Y);
    for(int i=1; i<=Q; i++){
        A[i] = IDX(X, A[i]); B[i] = IDX(X, B[i]);
        C[i] = IDX(Y, C[i]); D[i] = IDX(Y, D[i]);
        Qry[A[i]].emplace_back(C[i], D[i]);
        Qry[B[i]+1].emplace_back(C[i], D[i]);
    }
    for(int i=0; i+1<Y.size(); i++) W[i|SZ] = Y[i+1] - Y[i];
    for(int i=SZ-1; i>=1; i--) W[i] = W[i<<1] + W[i<<1|1];

    ll ans = 0;
    for(int i=0; i+1<X.size(); i++){
        for(auto j : Qry[i]) Update(j.x, j.y);
        Push(1, 0, SZ-1);
        ans += 1LL * T[1] * (X[i+1] - X[i]);
    }
    cout << 1LL * N * M - ans;
}