[1602] Mod Three
- 时间限制: 5000 ms 内存限制: 65535 K
- 问题描述
- Please help me to solve this problem, if so, LiangChen must have zhongxie!
There is a sequence contains n integers a0, a1, ...., an, firstly all of them equal 0,
and there are q opertions, each of them either is0 x; add ax by 1
or
1 l r; calculator the total number of ai that ai mod 3 == 0 (l <= i <= r) - 输入
- Input starts with an integer T denoting the number of test cases.
For each test case, first line contains n and q(1 <= n, q <= 100,000), next line contain n integers. - 输出
- For each test case, first line contains "Case X:", then print your answer, one line contains one integer.
- 样例输入
1
10 8
0 4
0 3
0 6
1 2 3
0 7
1 1 10
0 8
1 1 8- 样例输出
Case 1:
1
6
3
题目链接：NBUT 1602
看了一下居然跟是1603重复的，不过这题没人写，另外题目描述有点问题，序列不是a0~an而是a1~an。
用val统计叶子节点此时的值，cnt统计区间（节点）内模3不为0的个数，一开始都是0因此cnt的初始值为1
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=100010;
struct seg
{
int l,mid,r;
int val,cnt;
};
seg T[N<<2];
void pushup(int k)
{
T[k].val=T[LC(k)].val+T[RC(k)].val;
T[k].cnt=T[LC(k)].cnt+T[RC(k)].cnt;
}
void build(int k,int l,int r)
{
T[k].l=l;
T[k].r=r;
T[k].mid=MID(l,r);
if(l==r)
{
T[k].val=0;
T[k].cnt=1;
return ;
}
else
{
build(LC(k),l,T[k].mid);
build(RC(k),T[k].mid+1,r);
pushup(k);
}
}
void update(int k,int x)
{
if(T[k].l==T[k].r&&T[k].l==x)
T[k].cnt=((++T[k].val)%3==0);
else
{
if(x<=T[k].mid)
update(LC(k),x);
else
update(RC(k),x);
pushup(k);
}
}
int query(int k,int l,int r)
{
if(l<=T[k].l&&T[k].r<=r)
return T[k].cnt;
else
{
if(r<=T[k].mid)
return query(LC(k),l,r);
else if(l>T[k].mid)
return query(RC(k),l,r);
else
return query(LC(k),l,T[k].mid)+query(RC(k),T[k].mid+1,r);
}
}
int main(void)
{
int tcase,i,n,m,ops,l,r,x;
scanf("%d",&tcase);
for (int q=1; q<=tcase; ++q)
{
scanf("%d%d",&n,&m);
build(1,1,n);
printf("Case %d:\n",q);
for (i=0; i<m; ++i)
{
scanf("%d",&ops);
if(ops==0)
{
scanf("%d",&x);
update(1,x);
}
else if(ops==1)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(1,l,r));
}
}
}
return 0;
}