解題區/解題區 - UVa

UVa 12365 - Jupiter Atacks

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

查詢區間 hash 值、支持修改單一元素。

Sample Input

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
20 139 5 7
E 1 12
E 2 14
E 3 2
E 4 2
E 5 4
H 2 5
E 2 14
10 1000003 6 11
E 1 3
E 2 4
E 3 5
E 4 6
E 5 7
E 6 8
H 1 6
E 3 0
E 3 9
H 1 3
H 4 6
999999935 999999937 100000 7
E 100000 6
E 1 7
H 1 100000
E 50000 8
H 1 100000
H 25000 75000
H 23987 23987
0 0 0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
115
-
345678
349
678
-
824973478
236724326
450867806
0
-

Solution

線段樹套用

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long B, P; 
long long tree[262144 + 10], shiftP[131072 + 10];
void modify(int k, int l, int r, int x, int val) {
    if(l > r)	return;
    if(l == r) {
        tree[k] = val;	return ;
    }
    int m = (l + r)>>1;
    if(x <= m)	
        modify(k<<1, l, m, x, val);
    else		
        modify(k<<1|1, m+1, r, x, val);
    tree[k] = (tree[k<<1]*shiftP[r - m] + tree[k<<1|1])%P;
}
long long query(int k, int l, int r, int x, int y) {
    if(l > r)	return 0;
    if(x <= l && r <= y) {
        return tree[k]*shiftP[y - r];
    }
    int m = (l + r)>>1;
    long long ret = 0;
    if(x <= m)
        ret += query(k<<1, l, m, x, y);
    if(y > m)
        ret += query(k<<1|1, m+1, r, x, y);
    return ret%P;
}
int main() { 
    char cmd[1024];
    int a, b, n, q;
    while(scanf("%lld %lld %d %d", &B, &P, &n, &q) == 4 && n) {
        shiftP[0] = 1;
        for(int i = 1; i <= n; i++)
            shiftP[i] = (shiftP[i - 1] * B)%P;
        memset(tree, 0, sizeof(tree));
        while(q--) {
            scanf("%s %d %d", cmd, &a, &b);
            if(cmd[0] == 'E')
                modify(1, 1, n, a, b);
            else
                printf("%lld\n", query(1, 1, n, a, b));
        }
        puts("-");
    }
    return 0;
}