백준21607 Polynomial and Easy Queries

작성일 | In

문제 링크

  • http://icpc.me/21607

사용 알고리즘

  • 세그먼트 트리
  • 스파스 테이블

풀이

$f\circ g = g\circ f$이므로 두 함수를 적용하는 순서는 신경쓰지 않아도 됩니다. 그러므로, 초기 상태에서 각 $A_i$에 $f$와 $g$를 몇 번 적용해야 하는지 빠르게 구할 수 있다면 Sparse Table을 이용해서 문제를 풀 수 있습니다.

함수를 적용하는 횟수만 구하면 되므로, 1/2번 쿼리는 각각 Segment Tree나 Fenwick Tree를 이용해 구간에 1을 더하는 연산이라고 생각할 수 있습니다. 3번 쿼리는 $A_x$에 $f$, $g$를 적용해야 하는 횟수를 구한 뒤, Sparse Table을 이용해 로그 시간에 결과를 구하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int MOD = 1e5+3, SZ = 1 << 19, LG = 18;
inline int Mod(ll v){ v %= MOD; v += MOD; v %= MOD; return v; }
int f(ll x){ return Mod(2 * x * x - 1); }
int g(ll x){ return Mod(4 * x * x * x - 3 * x); }

int N, Q, A[SZ], F[LG][MOD], G[LG][MOD], T[SZ << 1][2];

void Update(int l, int r, int v){
    l |= SZ; r |= SZ;
    while(l <= r){
        if(l & 1) T[l++][v]++;
        if(~r & 1) T[r--][v]++;
        l >>= 1; r >>= 1;
    }
}

int Get(int v, int a, int b){
    for(int i=0; a; i++, a>>=1) if(a & 1) v = F[i][v];
    for(int i=0; b; i++, b>>=1) if(b & 1) v = G[i][v];
    return v;
}

int Query(int x){
    int ret = A[x]; x |= SZ;
    while(x >>= 1) ret = Get(ret, T[x][0], T[x][1]);
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=0; i<MOD; i++) F[0][i] = f(i);
    for(int i=1; i<LG; i++) for(int j=0; j<MOD; j++) F[i][j] = F[i-1][F[i-1][j]];
    for(int i=0; i<MOD; i++) G[0][i] = g(i);
    for(int i=1; i<LG; i++) for(int j=0; j<MOD; j++) G[i][j] = G[i-1][G[i-1][j]];
    for(int i=1; i<=Q; i++){
        int op, a, b; cin >> op >> a; if(op != 3) cin >> b;
        if(op == 3) cout << Query(a) << "\n";
        else Update(a, b, op-1);
    }
}