打卡信奥刷题（2864）用C++实现信奥题 P4939 Agent2

P4939 Agent2

题目背景

炎炎夏日还没有过去，Agent 们没有一个想出去外面搞事情的。每当 ENLIGHTENED 总部组织活动时，人人都说有空，结果到了活动日，却一个接着一个咕咕咕了。只有不咕鸟Lyn_king一个人冒着太阳等了半个多小时，然后居然看到连 ENLIGHTENED 行动参谋都咕咕咕了，果然咕咕咕是人类的本性啊。

题目描述

作为一个 ENLIGHTENED 行动指挥，自然不想看到这一点，于是他偷取到了那些经常咕咕咕的 Agent 的在下来NNN天的活动安排表，并且叫上了你来整理。在整理过程中，ENLIGHTENED 行动指挥对你说了MMM条命令，命令操作如下。

1. 输入0,a,b0,a,b0,a,b，这代表在第aaa天到第bbb天，有一名 Agent 要咕咕咕。
2. 输入111aaa，这代表 ENLIGHTENED 行动指挥询问你根据目前的信息，在第aaa天有多少名 Agent 会咕咕咕。

作为同是不咕鸟的你，也想要惩戒那些经常咕咕咕的人，所以，请协助完成 ENLIGHTENED 行动指挥完成整理，并且在他每次询问时，输出正确的答案。

输入格式

第一行输入两个整数N,MN,MN,M，接下来MMM行,每行输入一个命令，命令格式见题目描述。

输出格式

对于每一次询问的操作，都要输出询问的答案。答案之间用换行隔开。

输入输出样例 #1

输入 #1

5 5 0 1 2 0 1 5 1 1 0 3 5 1 5

输出 #1

2 2

说明/提示

对于20%20\%20%的数据N,M≤10N,M \leq 10N,M≤10；

对于40%40\%40%的数据N,M≤103N,M \leq 10^3N,M≤103；

对于60%60\%60%的数据N,M≤105N,M \leq 10^5N,M≤105；

对于100%100\%100%的数据1≤a,b≤N≤107,M≤4×1051 \leq a,b \leq N \leq 10^7,M \leq 4\times 10^51≤a,b≤N≤107,M≤4×105。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[10000001],c[10000001],m;intlowbit(inti){returni&(-i);}intgetSum(intx){//求和intsum=0;for(inti=x;i>0;i-=lowbit(i))//树状数组的前缀和sum+=c[i];returnsum;}voidmodify(intx,intdelta){//改变数据for(inti=x;i<=n;i+=lowbit(i))c[i]+=delta;}intmain(){cin>>n;cin>>m;for(inti=1;i<=m;i++){inta,b,c;cin>>c;if(c==1){cin>>a;cout<<getSum(a)<<endl;//树状数组前缀和得到单点查询}else{cin>>a>>b;modify(a,1);modify(b+1,-1);}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容