分块例题4

题面描述

给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。

输入格式

第一行输入一个数字 n

第二行输入 n 个数字，第 i 个数字为a[i]，以空格隔开

接下来输入 n 行询问，每行输入四个数字 opt, l，r，c, 以空格隔开

若 opt = 0，表示将 [l,r] 的之间的数都加 c

若 opt = 1，表示询问[l,r]中 所有数累加和 mod (c+1)的值

输出格式

对于每次询问，输出一行一个数字表示答案

样例

区间求和的话，在块外的话，就直接用长度*所改变的值+之前的总和就好了，块内的话直接加上就好了，这个题要mod一个数，不能到最后再mod因为有可能在加的时候爆掉，所以要一直mod，要记住能多mod就多mod，千万不要稍mod。

代码

#include<bits/stdc++.h>
using namespace std;
long long r[100010],l[100010],sum[100010],a[100010],add[100010],n,t,pos[100010];
void change(long long x,long long y,long long z)
{
	for(long long i=1;i<=t;i++)
	{
		if(x>r[i]||y<l[i])
		continue;
		if(x<=l[i]&&y>=r[i])
		{
			add[i]+=z;
		}
		else
		{
			for(long long j=max(x,l[i]);j<=min(r[i],y);j++)
			{
				sum[i]+=z;
				a[j]+=z;
			}
		}
	}
}
long long ask(long long x,long long y,long long z)
{
	long long ans=0;
	for(int i=1;i<=t;i++)
	{
		if(x>r[i]||y<l[i])
		continue;
		if(x<=l[i]&&y>=r[i])
		{
			ans+=sum[i]+add[i]*(r[i]-l[i]+1);
			ans%=z;
		}
		else
		{
			for(long long j=max(x,l[i]);j<=min(r[i],y);j++)
			{
				ans+=(add[i]+a[j]);
				ans%=z;
			}
		}
	}
	return ans;
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		l[i]=(i-1)*sqrt(n)+1;
		r[i]=i*sqrt(n);
	}
	if(r[t]<n)
	{
		t++;
		l[t]=r[t-1]+1;
		r[t]=n;
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			pos[j]=i;
			sum[i]+=a[j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		long long op,x,y,z;
		cin>>op>>x>>y>>z;
		if(op==0)
		{
			change(x,y,z);
		}
		else
		{
			cout<<ask(x,y,z+1)<<endl;
		}
	}
}