백준13704 수열과 쿼리 11

작성일 | In

문제 링크

  • http://icpc.me/13704

사용 알고리즘

  • 모스 알고리즘

시간복잡도

  • $O(N+Q \sqrt N)$

풀이

어떤 구간의 원소를 모두 xor한 값은 prefix 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int sz = 300;

struct Query{
    int s, e, x;
    bool operator < (const Query &t) const {
        if(s/sz != t.s/sz) return s < t.s;
        return e < t.e;
    }
};

int n, k, q;
int arr[101010];
ll ans[101010];
vector<Query> qry;
ll now;
ll cnt[1 << 21];

int s, e;

void insert_l(int x){
    cnt[arr[x]]++;
    now += cnt[k^arr[x-1]];
}

void insert_r(int x){
    now += cnt[k^arr[x]];
    now += arr[s-1] == (k^arr[x]);
    cnt[arr[x]]++;
}

void erase_l(int x){
    now -= cnt[k^arr[x-1]];
    cnt[arr[x]]--;
}

void erase_r(int x){
    now -= cnt[k^arr[x]];
    now -= arr[s-1] == (k^arr[x]);
    cnt[arr[x]]--;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> arr[i];
    for(int i=1; i<=n; i++) arr[i] ^= arr[i-1];
    cin >> q;
    for(int i=0; i<q; i++){
        int s, e; cin >> s >> e;
        qry.push_back({s, e, i});
    }
    sort(qry.begin(), qry.end());

    s = e = qry[0].s;
    cnt[arr[s]] = 1;
    if((arr[s] ^ arr[s-1]) == k) now++;
    while(e < qry[0].e) insert_r(++e);
    ans[qry[0].x] = now;
    for(int i=1; i<q; i++){
        while(qry[i].s < s) insert_l(--s);
        while(qry[i].e > e) insert_r(++e);
        while(qry[i].s > s) erase_l(s++);
        while(qry[i].e < e) erase_r(e--);
        ans[qry[i].x] = now;
        if(now < 0) return -1;
    }
    for(int i=0; i<q; i++) cout << ans[i] << "\n";
}