专栏首页数据结构与算法Codeforce GYM 100741 A. Queries

Codeforce GYM 100741 A. Queries

A. Queries

time limit per test

0.25 s

memory limit per test

64 MB

input

standard input

output

standard output

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). (

) (

)

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

3 4
1 2 3
3
s 1 3 2
+ 2 1
- 1 2

output

2
3
1


看一下数据范围,
m<=20
果断开20个树状数组
注意:要开long long
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define lli long long int 
 8 using namespace std;
 9 const lli MAXN=10001;
10 void read(lli &n)
11 {
12     char c='+';lli x=0;bool flag=0;
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
15     n=flag==1?-x:x;
16 }
17 lli n,m;
18 struct node
19 {
20     lli a[MAXN];
21     lli lowbit(lli x){return x&(-x);}
22     lli change(lli pos,lli val)
23     {
24         for(;pos<=n;pos+=lowbit(pos))
25             a[pos]+=val;
26     }
27     lli query(lli l,lli r)
28     {
29         return ask(r)-ask(l-1);
30     }
31     lli ask(lli pos)
32     {
33         lli ans=0;
34         for(;pos;pos-=lowbit(pos))
35             ans+=a[pos];
36         return ans;
37     }    
38     node(){memset(a,0,sizeof(a));}
39 }bit[21];
40 lli date[MAXN];
41 int main()
42 {
43     read(n);read(m);
44     for(lli i=1;i<=n;i++)
45     {
46         read(date[i]);
47         bit[date[i]%m].change(i,date[i]);
48     }
49     lli T;read(T);
50     while(T--)
51     {
52         char how;cin>>how;
53         if(how=='+')
54         {
55             lli p,num;read(p);read(num);
56             bit[date[p]%m].change(p,-date[p]);
57             date[p]+=num;
58             bit[date[p]%m].change(p,date[p]);
59             printf("%lld\n",date[p]);
60         }
61         else if(how=='-')
62         {
63             lli p,num;read(p);read(num);
64             if(date[p]<num)
65                 printf("%lld\n",date[p]);
66             else
67             {
68                 bit[date[p]%m].change(p,-date[p]);
69                 date[p]-=num;
70                 bit[date[p]%m].change(p,date[p]);
71                 printf("%lld\n",date[p]);
72             }
73             
74         }
75         else if(how=='s')
76         {
77             lli l,r,mod;read(l);read(r);read(mod);
78             printf("%lld\n",bit[mod].query(l,r));
79         }
80     }
81     return 0;
82 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1506 Largest Rectangle in a Histogram(单调栈)

    attack
  • agc016D - XOR Replace(图论 智商)

    不难看出,我们把所有数$xor$起来的数替换掉之后再次$xor$,得到的一定是被替换掉的数。

    attack
  • Tour UVA - 1347

    John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small...

    attack
  • Variant 分析阶段小结1-基础碎碎念

    所谓遗传变异是生物体内遗传物质发生变化而造成的可以遗传给后代的变异,这些变异导致了生物在不同水品上体现出遗传的多样性。生物信息学中各种基因组研究的基础就是遗传变...

    生信技能树
  • NSURLSession 所有的都在这里(一)

    Mr.RisingSun
  • 关于无意识匹配问题

    作者:Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

    罗大琦
  • 基于利用率差异的混合临界系统分区调度(CS OS)

    混合临界性(MC)系统将具有不同临界性的多个功能合并到一个硬件平台上。这样的系统提高了资源的整体利用率,同时保证了关键任务的资源。本文主要研究了多处理器MC调度...

    非过度曝光
  • 一个好用的SAP ABAP工作进程跟踪工具

    As an ABAPer we have SAT, ST05 ( or sometimes ST12 ) for trace in our toolbox, a...

    Jerry Wang
  • universe-starter-agent

    The codebase implements a starter agent that can solve a number of universe envi...

    用户1908973
  • 手把手教强化学习1: Q-learning 十步实现猫捉耗子视频及代码

    用户1908973

扫码关注云+社区

领取腾讯云代金券