백준19651 수열과 쿼리 39

작성일 | In

문제 링크

  • http://icpc.me/19651

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(Q \log N)$

풀이

2번 쿼리를 푸는 방법을 먼저 알아봅시다.

연속한 세 원소 $A_{i-1}, A_i, A_{i+1}$이 등차수열을 이룬다면 $2A_i = A_{i-1}+A_{i+1}$이 성립합니다.
새로운 수열 $B_i = A_{i-1}+A_{i+1}-2A_i$를 정의하면, 수열 $B$에서 연속된 0의 개수를 구하는 문제로 바뀌게 됩니다.

만약 쿼리로 주어지는 구간의 크기가 2라면 쿼리의 결과는 2가 되고, 2보다 큰 경우에는 (연속한 0의 개수 + 2)가 됩니다. 연속한 0의 개수는 흔히 금광 세그라고 불리는 테크닉을 이용해 $O(\log N)$만에 구할 수 있습니다. 이 부분의 구현은 아래 코드의 11-37번 라인을 참고하시면 됩니다.

1번 쿼리는 수열 $A$의 특정 구간에 등차 수열을 더하는 쿼리입니다.

구간 $[s, e]$에 초항이 $x$, 공차가 $y$인 등차 수열을 더하는 것은 아래에 나와있는 방법을 Fenwick Tree 등을 통해 구현하면 $O(\log N)$만에 처리할 수 있습니다.

  • 구간 $[s, e]$의 각 원소에 $x-sy$를 더한다.
  • $i \in [s, e]$인 $i$에 대해, $i$번째 원소에 $iy$를 더한다.

수열 $A$의 구간 $[s, e]$에 등차 수열을 더했을 때 수열 $B$에서 값이 변하는 원소는 최대 4개밖에 없습니다. ($s-1, s, e, e+1$)
수열 $A$의 값을 모두 알기 때문에 4개의 지점에 대해서만 세그먼트 트리를 업데이트해주면 문제를 풀 수 있습니다.

전체 코드

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
#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 int long long
using namespace std;

typedef long long ll;

struct Node{
    int l, r, mx, flag;
    Node(){ l = r = mx = flag = 0; }
    Node(int l, int r, int mx, int flag) : l(l), r(r), mx(mx), flag(flag) {}
    void set(int v){ l = r = mx = flag = v; }
} tree[1 << 18];
const int sz = 1 << 17;
Node merge(Node a, Node b){
    if(a.flag == -1) return b;
    if(b.flag == -1) return a;
    Node ret;
    ret.flag = a.flag && b.flag;
    ret.l = a.flag ? a.mx + b.l : a.l;
    ret.r = b.flag ? a.r + b.mx : b.r;
    ret.mx = max({a.mx, b.mx, a.r + b.l});
    return ret;
}
void update(int x, int v){
    x |= sz; tree[x].set(!v);
    while(x >>= 1) tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
}
Node query(int l, int r, int node = 1, int s = 0, int e = sz-1){
    if(r < s || e < l) return {0, 0, 0, -1};
    if(l <= s && e <= r) return tree[node];
    int m = s + e >> 1;
    return merge(query(l, r, node << 1, s, m), query(l, r, node << 1 | 1, m+1, e));
}

struct BIT{
    ll tree[101010];
    void add(int x, int v){ for(x++; x<101010; x+=x&-x) tree[x] += v; }
    ll query(int x){ ll ret = 0; for(x++; x; x-=x&-x) ret += tree[x]; return ret; }
} t1, t2;
void add(int s, int e, int a, int b){
    t1.add(s, a-b*s); t1.add(e+1, b*s-a);
    t2.add(s, b); t2.add(e+1, -b);
}
ll get(int x){ return t1.query(x) + t2.query(x)*x; }

int n, q;

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        int t; cin >> t; t1.add(i, t); t1.add(i+1, -t);
    }
    for(int i=2; i<n; i++) update(i, get(i-1)+get(i+1)-2*get(i));
    cin >> q;
    while(q--){
        int op; cin >> op;
        if(op == 1){
            int s, e, a, b; cin >> s >> e >> a >> b;
            add(s, e, a, b);
            for(auto x : {s-1, s, e, e+1}){
                if(1 < x && x < n) update(x, get(x-1)+get(x+1)-2*get(x));
            }
        }
        else{
            int l, r; cin >> l >> r;
            if(l == r) cout << "1\n";
            else if(l+1 == r) cout << "2\n";
            else cout << query(l+1, r-1).mx+2 << "\n";
        }
    }
}