Mod and Sum

线段树+区间更新+单点更新+区间查询

Mod and Sum
30000(ms) 65535(kb)
给出n个数ai（下标从1开始），系数k，m种操作 操作分为3种： 1 a b :将下标为a的数加上b（1<=a<=n,0<=b<=10^9） 2 a b :将区间[a,b]内每个数对k取模（1<=a,b<=n） 3 a b :询问区间[a,b]内每个数的和（1<=a,b<=n）
输入
第一行一个整数T(T<=10)，表示有T组测试数据
接下来每组测试数据第一行三个整数n,k,m
下面有m组操作。
1<=n,m,k<=10^5
0<=ai<=10^9
输出
对于每次询问输出答案
样例输入
1
4 3 3
1 2 3 4
1 1 1
2 1 4
3 1 4
样例输出
5

题目链接

题意很简单，如果学过线段树应该一眼就能看出是线段树的裸题（但是有毒QWQ）

涉及到的知识点已用粗体指出。

这道题比较难一点的就是区间更新，对区间的每个数进行取模，我们肯定不能直接对每个数进行取模，那还不如不用线段树。

当然我们可以想到线段树维护区间和，但是取模时怎么维护呢？这里我们需要维护另一个值 cnt。

我们首先要知道 : a % b == a - k * b，所以维护的cnt就是这里的k。

下面AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int T,n,k,m;
struct node
{
	ll sum;
	int cnt,lazy,l,r;
}t[N<<2];
void push_up(int p)
{
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].cnt=t[p<<1].cnt+t[p<<1|1].cnt;
}
void push_down(int p)
{
	if(t[p].lazy)
	{
		t[p<<1].lazy=1;
		t[p<<1|1].lazy=1;
		t[p<<1].sum-=t[p<<1].cnt*k;
		t[p<<1|1].sum-=t[p<<1|1].cnt*k;
		t[p<<1].cnt=0;
		t[p<<1|1].cnt=0;
		t[p].lazy=0;
	}
}
void build(int p,int l,int r)
{
	t[p].l=l;t[p].r=r;
	t[p].lazy=0;t[p].sum=0;t[p].cnt=0;
	if(l==r)
	{
		scanf("%lld",&t[p].sum);
		//read(t[p].sum);
		t[p].cnt=t[p].sum/k;
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void add(int p,int x,int v)
{
	if(t[p].l==t[p].r)
	{
		t[p].sum+=v;
		t[p].cnt=t[p].sum/k;
		return ;
	}
	push_down(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid)	add(p<<1,x,v);
	else	add(p<<1|1,x,v);
	push_up(p);
}
void mod(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].sum-=t[p].cnt*k;
		t[p].cnt=0;
		t[p].lazy=1;
		return ;
	}
	push_down(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(r<=mid)	mod(p<<1,l,r);
	else if(l>mid)	mod(p<<1|1,l,r);
	else	mod(p<<1,l,mid),mod(p<<1|1,mid+1,r);
	push_up(p);
}
ll ask(int p,int l,int r)
{
	if(t[p].l>=l&&t[p].r<=r)	return t[p].sum;
	push_down(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)+ask(p<<1|1,mid+1,r);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d %d",&n,&k,&m);
		build(1,1,n);
		while(m--)
		{
			int op,a,b;
			scanf("%d %d %d",&op,&a,&b);
			if(op==1)	add(1,a,b);
			else if(op==2)	mod(1,a,b);
			else	printf("%lld\n",ask(1,a,b));
		}
	}
	return 0;
}