백준15055 Dauting device

작성일 | In

문제 링크

  • http://icpc.me/15055

사용 알고리즘

  • Sqrt Decomposition
  • Lazy Propagation

풀이

구간을 어떤 수로 바꾸는 쿼리 / 수열에 어떤 수가 몇 개 있는지 구하는 쿼리를 처리해야 합니다.
세그먼트 트리로 처리하기는 힘들어 보이니까 sqrt decomposition을 해봅시다.

구간을 어떤 수로 바꾸는 것은 Lazy Propagation을 해주면 됩니다. 어떤 버킷이 쿼리로 주어진 구간에 완전히 포함된다면 굳이 버킷 내부의 원소를 바꿔줄 필요 없이 Lazy Tag만 붙여주면 됩니다. 버킷이 주어진 구간과 일부만 겹치는 경우에는 Lazy를 전파해주고 Naive하게 각 원소를 바꿔주면 됩니다.
각 쿼리마다 최대 2개의 버킷의 Lazy Tag가 없어지므로 전체 문제에서는 최대 (2 × 쿼리의 개수)번만 Lazy Tag가 없어집니다.

Lazy Tag를 달아주는 것은 $\sqrt L = O(B)$만에 가능하고(버킷이 최대 B개), Lazy를 전파해주는 것과 Naive하게 원소를 바꿔주는 것은 $\sqrt L = O(B)$가 걸립니다. Lazy를 전파해주는 것은 전체 문제를 풀면서 $O(N)$번밖에 수행하지 않으므로 $N$개의 쿼리를 $O(NB) = O(N\sqrt L)$만에 처리할 수 있습니다.

수열 전체에서 어떤 수가 몇 개 있는지 구하는 쿼리는, 업데이트 쿼리가 주어질 때마다 각 수가 몇 개씩 있는지 갱신해주면 됩니다.

전체 코드

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
#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())
using namespace std;

typedef long long ll;
const int sq = 400;

int n, m, q;
int v[101010], cnt[101010];
int st[444], ed[444], sz[444], tmp[444];

void push(int node){
    if(!tmp[node]) return;
    int s = st[node], e = ed[node];
    for(int i=s; i<=e; i++) v[i] = tmp[node];
    tmp[node] = 0;
}

void solve_bucket(int x, int color){
    if(!tmp[x]) for(int i=st[x]; i<=ed[x]; i++) cnt[v[i]]--, v[i] = color, cnt[v[i]]++;
    else cnt[tmp[x]] -= sz[x], cnt[color] += sz[x];
    tmp[x] = color;
}

void solve_naive(int s, int e, int b, int color){
    push(b);
    for(int i=s; i<=e; i++) cnt[v[i]]--, v[i] = color, cnt[v[i]]++;
}

void query(){
    ll p, x, a, b; cin >> p >> x >> a >> b;
    ll s = cnt[p];
    int l = (a + s*s) % n, r = (a + (s+b) * (s+b)) % n;
    if(l > r) swap(l, r);
    for(int i=0; i<m; i++){
        int s = st[i], e = ed[i];
        if(r < s || e < l) continue;
        if(l <= s && e <= r) solve_bucket(i, x);
        else solve_naive(max(s, l), min(e, r), i, x);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> q;
    int pv = 0;
    for(int i=0; ; i++){
        int s = pv, e = min(n-1, pv+sq-1);
        sz[i] = e - s + 1; tmp[i] = 1;
        st[i] = s; ed[i] = e;
        if(ed[i] == n-1){ m = i+1; break; }
        pv += sq;
    }
    cnt[1] = n;
    while(q--) query();

    cout << *max_element(cnt, cnt+101010);
}