给博主点赞关注一下,谢谢你的支持~
题目描述
给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,区间求和。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字,第 i 个数字为 ai,以空格隔开。
接下来输入 n 行询问,每行输入四个数字 opt、l、r、c,以空格隔开。
若 opt = 0,表示将位于 [l, r] 的之间的数字都加 c。
若 opt = 1,表示询问位于 [l, r] 的所有数字的和 mod (c+1)。
输出格式
对于每次询问,输出一行一个数字表示答案。
样例
输入复制
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出复制
1
4
AC代码
//特别提醒:一定要开 long long !
#include <iostream>
#include <bits/stdc++.h>//万能头文件
#define int long long
using namespace std;
int n;
int a[50005];
int bl[50005];
int blo;//块长
int atag[505];//sqrt(50005)
int sum[505];//sqrt(50005)
int read(){//快读
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void add(int l,int r,int c){//区间求和
for(int i=l;i<=min(bl[l]*blo,r);i++){
a[i]+=c;
sum[bl[l]]+=c;
}
if(bl[l]!=bl[r]){
for(int i=(bl[r]-1)*blo+1;i<=r;i++){
a[i]+=c;
sum[bl[r]]+=c;
}
}
for(int i=bl[l]+1;i<=bl[r]-1;i++){
atag[i]+=c;
}
}
int query(int l,int r,int c){//区间求和(查询)
int ans=0;
for(int i=l;i<=min(bl[l]*blo,r);i++){
ans+=a[i];
ans+=atag[bl[l]];
}
if(bl[l]!=bl[r]){
for(int i=(bl[r]-1)*blo+1;i<=r;i++){
ans+=a[i];
ans+=atag[bl[r]];
}
}
for(int i=bl[l]+1;i<=bl[r]-1;i++){
ans+=sum[i];
ans+=atag[i]*blo;
}
ans%=(c+1);//原题要求
return ans;
}
signed main(){
n=read();
blo=sqrt(n);
for(int i=1;i<=n;i++){//下标从1开始
a[i]=read();
}
for(int i=1;i<=n;i++){
bl[i]=(i-1)/blo+1;//分块
}
for(int i=1;i<=n;i++){
sum[bl[i]]+=a[i];
}
for(int i=1;i<=n;i++){
int opt=read(),l=read(),r=read(),c=read();
if(opt==0){
add(l,r,c);//区间加法
}
else if(opt==1){
cout<<query(l,r,c)<<endl;//区间求和(查询)
}
}
return 0;
}