Mathematicians are interesting (sometimes, I would say, even crazy) people. For example, my friend, a mathematician, thinks that it is very fun to play with a sequence of integer numbers. He writes the sequence in a row. If he wants he increases one number of the sequence, sometimes it is more interesting to decrease it (do you know why?..) And he likes to add the numbers in the interval [l;r]. But showing that he is really cool he adds only numbers which are equal some mod (modulo m).
Guess what he asked me, when he knew that I am a programmer? Yep, indeed, he asked me to write a program which could process these queries (n is the length of the sequence):
- + p r It increases the number with index p by r. (
, 
)
You have to output the number after the increase.
- - p r It decreases the number with index p by r. (, ) You must not decrease the number if it would become negative.
You have to output the number after the decrease.
- s l r mod You have to output the sum of numbers in the interval
which are equal mod (modulo m). (
) (
)
The first line of each test case contains the number of elements of the sequence n and the number m. (1 ≤ n ≤ 10000) (1 ≤ m ≤ 10)
The second line contains n initial numbers of the sequence. (0 ≤ number ≤ 1000000000)
The third line of each test case contains the number of queries q (1 ≤ q ≤ 10000).
The following q lines contains the queries (one query per line).
Output q lines - the answers to the queries.
3 4
1 2 3
3
s 1 3 2
+ 2 1
- 1 2
2
3
1
【题解】
m棵线段树即可
树状数组就够了，但是我就是想写线段树练一练怎么了（唔）
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdio> 6 #define max(a, b) ((a) > (b) ? (a) : (b)) 7 #define min(a, b) ((a) < (b) ? (a) : (b)) 8 9 inline void read(long long &x) 10 { 11 x = 0;char ch = getchar(), c = ch; 12 while(ch < '0' || ch > '9')c = ch, ch = getchar(); 13 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 14 if(c == '-')x = - x; 15 } 16 17 const long long INF = 0x3f3f3f3f; 18 const long long MAXN = 100000 + 10; 19 20 long long n,m,num[MAXN],sum[10][MAXN]; 21 22 void build(long long o = 1, long long l = 1, long long r = n) 23 { 24 if(l == r) 25 { 26 sum[num[l]%m][o] += num[l]; 27 return; 28 } 29 long long mid = (l + r) >> 1; 30 build(o << 1, l, mid); 31 build(o << 1 | 1, mid + 1, r); 32 for(register long long i = 0;i <= 9;++ i) 33 sum[i][o] = sum[i][o << 1] + sum[i][o << 1 | 1]; 34 return; 35 } 36 37 void modify(long long p, long long shu, long long x, long long o = 1, long long l = 1, long long r = n) 38 { 39 if(l == p && l == r) 40 { 41 sum[shu % m][o] += x * shu; 42 return; 43 } 44 long long mid = (l + r) >> 1; 45 if(mid >= p) modify(p, shu, x, o << 1, l, mid); 46 else modify(p, shu, x, o << 1 | 1, mid + 1, r); 47 sum[shu % m][o] = sum[shu % m][o << 1] + sum[shu % m][o << 1 | 1]; 48 } 49 50 long long ask(long long ll, long long rr, long long rk, long long o = 1, long long l = 1, long long r = n) 51 { 52 if(ll <= l && rr >= r) return sum[rk][o]; 53 long long mid = (l + r) >> 1; 54 long long ans = 0; 55 if(mid >= ll) ans += ask(ll, rr, rk, o << 1, l, mid); 56 if(mid < rr) ans += ask(ll, rr, rk, o << 1 | 1, mid + 1, r); 57 return ans; 58 } 59 60 long long q; 61 char c; 62 63 int main() 64 { 65 read(n), read(m); 66 for(register long long i = 1;i <= n;++ i) 67 read(num[i]); 68 build(); 69 read(q); 70 for(register long long i = 1;i <= q;++ i) 71 { 72 long long tmp1,tmp2,tmp3; 73 scanf("%s", &c); 74 if(c == 's') 75 { 76 read(tmp1), read(tmp2), read(tmp3); 77 printf("%I64d ", ask(tmp1, tmp2, tmp3)); 78 } 79 else if(c == '+') 80 { 81 read(tmp1), read(tmp2); 82 modify(tmp1, num[tmp1], -1); 83 num[tmp1] += tmp2; 84 modify(tmp1, num[tmp1], 1); 85 printf("%I64d ", num[tmp1]); 86 } 87 else 88 { 89 read(tmp1), read(tmp2); 90 modify(tmp1, num[tmp1], -1); 91 if(num[tmp1] - tmp2 >= 0) num[tmp1] -= tmp2; 92 modify(tmp1, num[tmp1], 1); 93 printf("%I64d ", num[tmp1]); 94 } 95 } 96 return 0; 97 }