解題區►解題區 - 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;
}