codeforce GYM 100741 A Queries

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. ( $\text{[math]}$ , $\text{[math]}$ )
You have to output the number after the increase.
- p r It decreases the number with index p by r. ( $\text{[math]}$ , $\text{[math]}$ ) 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 $\text{[math]}$ which are equal mod (modulo m). ( $\text{[math]}$ ) ( $\text{[math]}$ )

Input

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

Output q lines - the answers to the queries.

Examples

input

output

2
3
1

题意

一个长度为 n 的序列，q 次三种操作，

+ p r: 下标为 p 的数加 r.
- p r: 下表为 p 的数减 r.
s l r mod: 询问在区间[l,r]中模 m 等于 mod 的所有数的和。

分析

可以建立m个树状数组，然后询问就好处理了，加减要现在原来的树状数组中减掉，然后在之后的树状数组中加上。

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 const int MAXN = 10010;
 8 LL n,m,q;
 9 LL s[MAXN];
10 
11 LL read()
12 {
13     LL x = 0,f = 1;char ch = getchar();
14     while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch = getchar(); }
15     while (ch>='0'&&ch<='9') {x = x*10+ch-'0'; ch = getchar(); }
16     return x*f;
17 }
18 
19 struct Tree_array{
20     LL a[MAXN];
21     int lowbit(int x)
22     {
23         return x&(-x);
24     }
25     void update(int x,int v)
26     {
27         for (; x<=n; x+=lowbit(x)) a[x] += v;
28     }
29     LL query(int x)
30     {
31         LL ret = 0;
32         for (; x; x-=lowbit(x))
33          ret += a[x];
34         return ret;
35     }
36 }t[12];
37 
38 
39 int main()
40 {
41     n = read();m = read();
42     for (int i=1; i<=n; ++i)
43     {
44         s[i] = read();
45         t[s[i]%m].update(i,s[i]);
46     }
47     char opt[5];
48     q = read();
49     LL x,y,mo;
50     while (q--)
51     {
52         scanf("%s",opt);
53         x = read();y = read();
54         if (opt[0]=='s')
55         {
56             mo = read();
57             printf("%lld
",t[mo].query(y)-t[mo].query(x-1));
58         }
59         else if (opt[0]=='+')
60         {
61             t[s[x]%m].update(x,-s[x]);
62             s[x] += y;
63             t[s[x]%m].update(x,s[x]);
64             printf("%lld
",s[x]);
65         }
66         else 
67         {
68             if (s[x]<y) printf("%lld
",s[x]);
69             else 
70             {
71                 t[s[x]%m].update(x,-s[x]);
72                 s[x] -= y;
73                 t[s[x]%m].update(x,s[x]);
74                 printf("%lld
",s[x]);
75             }
76         }
77     }
78     return 0;    
79 }