【第三站】末日时在做什么？有没有空？可以来拯救吗？题解
这题欢迎各位用线段树、分块、平衡树、带修莫队吊打std！
题目大概就是让我们维护两个操作：区间和，区间加。
不过，看看数据范围就知道，这题用不到什么平衡树、带修莫队之类的毒瘤数据结构啦\(^o^)/！
骗分大法：Subtask#1
由于题目中说过了为样例1，直接输出样例1即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"11"<<endl;
cout<<"8"<<endl;
cout<<"20"<<endl;
return 0;
}骗分效果不咋地，得
正解：
#include<bits/stdc++.h> //万能头最棒!QwQ
using namespace std;
int a[10005]; //原数组
int main(){
int n,m;
scanf("%d%d",&n,&m); //输入 n,m
for(int i=1;i<=n;i++){ //输入数组 a
scanf("%d",&a[i]);
}
while(m--){ //for(int i=1;i<=m;i++)的偷懒写法
int cmd=0,x=0,y=0,k=0;
scanf("%d",&cmd); //输入操作编号
if(cmd==1){ //如果是1，那么意思是把区间[x,y]内的数加上k。
scanf("%d%d%d",&x,&y,&k); //输入x,y,k
for(int i=x;i<=y;i++){ //暴力在区间[x,y]内遍历每个数
a[i]+=k; //每一个数都加上k
}
}
else{ //如果不是一，那么意思是查询区间[x,y]内所有数的和。
scanf("%d%d",&x,&y); //输入x,y
int ans=0; //查询结果，记得初始化为0
for(int i=x;i<=y;i++){ //暴力在区间[x,y]内遍历每个数
ans+=a[i]; //把查询结果加上a[i]
}
printf("%d\n",ans); //输出查询结果，记得换行
}
}
return 0; //完结撒花
}有趣的东西：
此题分块做法（自己写的）：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define ll long long
#define kkk 500005
using namespace std;
ll a[kkk],sum[kkk],sumr[kkk],f[kkk];
int sq,n,q;
ll min(ll r,ll s){
return r<s?r:s;
}
void change(ll l,ll r,ll k){
for(int i=l;i<=min(f[l]*sq,r);i++){
a[i]+=(ll)k;
sum[f[i]]+=(ll)k;
}
for(int i=f[l]+1;i<=f[r]-1;i++){
sum[i]+=(ll)k*sq;
sumr[i]+=(ll)k;
}
if(f[l]!=f[r]){
for(int i=(f[r]-1)*sq+1;i<=r;i++){
a[i]+=(ll)k;
sum[f[i]]+=(ll)k;
}
}
}
ll query(ll l,ll r){
ll ans=0;
for(int i=l;i<=min(f[l]*sq,r);i++){
ans+=(ll)a[i]+sumr[f[i]];
}
for(int i=f[l]+1;i<=f[r]-1;i++){
ans+=(ll)sum[i];
}
if(f[l]!=f[r]){
for(int i=(f[r]-1)*sq+1;i<=r;i++){
ans+=(ll)a[i]+sumr[f[i]];
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
sq=sqrt(n);
for(int i=1;i<=n;i++){
f[i]=(i-1)/sq+1;
cin>>a[i];
sum[f[i]]+=a[i];
}
while(q--){
int cmd,l,r,k;
cin>>cmd;
switch(cmd){
case 1:{
cin>>l>>r>>k;
change(l,r,k);
break;
}
case 2:{
cin>>l>>r;
ll tmp=query(l,r);
cout<<tmp<<endl;
break;
}
}
}
return 0;
}此题线段树做法：
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
long long n,m,in[250],f;
struct node{
long long l,r,sum,lz;
}t[1000];
void build(long long i,long long l,long long r){
t[i].l=l,t[i].r=r;
if (t[i].l==t[i].r){
t[i].sum=in[l];
return;
}
long long mid=(l+r)>>1;
build((i<<1),l,mid);
build((i<<1)+1,mid+1,r);
t[i].sum=t[(i<<1)].sum+t[(i<<1)+1].sum;
}
void push_down(long long i){
if (t[i].lz!=0){
t[(i<<1)].lz+=t[i].lz;
t[(i<<1)+1].lz+=t[i].lz;
long long mid=(t[i].l+t[i].r)>>1;
t[(i<<1)].sum+=t[i].lz*(mid-t[(i<<1)].l+1);
t[(i<<1)+1].sum+=t[i].lz*(t[(i<<1)+1].r-mid);
t[i].lz=0;
}
}
long long search(long long i,long long l,long long r){
if (t[i].l>=l&&t[i].r<=r) return t[i].sum;
if (t[i].r<l||t[i].l>r) return 0;
push_down(i);
long long s=0;
if (t[(i<<1)].r>=l) s+=search((i<<1),l,r);
if (t[(i<<1)+1].l<=r) s+=search((i<<1)+1,l,r);
return s;
}
void add(long long i,long long l,long long r,long long k){
if (t[i].l>=l&&t[i].r<=r){
t[i].sum+=k*(t[i].r-t[i].l+1);
t[i].lz+=k;
return;
}
if (t[i].l>r||t[i].r<l) return;
push_down(i);
long long mid=(l+r)>>1;
if (t[(i<<1)].r>=l) add((i<<1),l,r,k);
if (t[(i<<1)+1].l<=r) add((i<<1)+1,l,r,k);
t[i].sum=t[(i<<1)].sum+t[(i<<1)+1].sum;
}
int main(){
scanf("%lld %lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&in[i]);
build(1,1,n);
while (m--){
long long f,x,y,k;
scanf("%lld",&f);
switch(f){
case 1:
scanf("%lld %lld %lld",&x,&y,&k);
add(1,x,y,k);
break;
case 2:
scanf("%lld %lld",&x,&y);
printf("%lld\n",search(1,x,y));
break;
}
}
return 0;
}（感谢@翼德天尊提供线段树解法，%%%）
差分做法：
#include <iostream>
using namespace std;
int n, m, num[2333], cf[114514], l, r, k, opt, sum;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for(register int i = 1; i <= n; i++)
cin >> num[i];
for(register int i = 1; i <= n; i++)
cf[i] = num[i] - num[i - 1];
for(register int i = 1; i <= m; i++)
{
cin >> opt;
if(opt == 1)
{
cin >> l >> r >> k;
cf[l] += k, cf[r + 1] -= k;
}
else
{
cin >> l >> r;
sum = 0;
for(register int j = 1; j <= n; j++)
num[j] = cf[j] + num[j - 1];
for(register int j = l; j <= r; j++)
sum += num[j];
cout << sum << endl;
}
}
return 0;
}（感谢@__VAN♂游戏__提供差分做法，%%%）
平衡树做法：
等一下哈，本蒟蒻正在打（
带修莫队做法：
等一下哈，本蒟蒻正在打（