H. Skyscraper
time limit per test
4.0 s
memory limit per test
512 MB
input
standard input
output
standard output
At the main street of Byteland, there will be built nn skyscrapers, standing sequentially one next to other. If look leftside right, sequence of their height will be a1,a2,…,ana1,a2,…,an.
Initially the street is empty, every skyscraper's height is 00. Hamster is the leader of the construction team. In each stage, Hamster can select a range [l,r][l,r], then the team will work on this range. Specifically, assume the height sequence is h1,h2,…,hnh1,h2,…,hn, then hl,hl+1,…,hrhl,hl+1,…,hr will increase by 11during this stage. When hi=aihi=ai holds for all i∈[1,n]i∈[1,n], the project will be closed.
The plan may be changed for many times. There will be mm events of 22 kinds below:
- 1 l r k (1≤l≤r≤n,1≤k≤1051≤l≤r≤n,1≤k≤105), for all x∈[l,r]x∈[l,r], change axax to ax+kax+k.
- 2 l r (1≤l≤r≤n1≤l≤r≤n), assume a1,a2,…,al−1,ar+1,ar+2,…,an=0a1,a2,…,al−1,ar+1,ar+2,…,an=0, ask for the minimum number of required stages to close the project.
Input
The first line of the input contains an integer T(1≤T≤1000)T(1≤T≤1000), denoting the number of test cases.
In each test case, there are two integers n,m(1≤n,m≤100000)n,m(1≤n,m≤100000) in the first line, denoting the number of skyscrapers and events.
In the second line, there are nn integers a1,a2,...,an(1≤ai≤100000)a1,a2,...,an(1≤ai≤100000).
For the next mm lines, each line describes an event.
It is guaranteed that ∑n≤106∑n≤106 and ∑m≤106∑m≤106.
Output
For each query event, print a single line containing an integer, denoting the answer.
Example
input
Copy
1
5 4
1 3 1 4 5
2 1 5
1 3 4 2
2 2 4
2 1 5
output
Copy
7
6
6仔细读了官方题解之后突然明白
原来本题并不需要区间更新
本题巧妙地运用了前缀和
在每次更新是我们把l+x r+1-x
这样我们其实也是妙的进行了一次区间更新
#include<bits/stdc++.h>
#define N 100005
using namespace std;
long long n;
long long bsum[N];
long long csum[N];
long long a[N];
long long b[N];
long long c[N];
long long lowbit(long long x)
{
return x&(-x);
}
void updateb(long long k,long long x)
{
for(long long i=k; i<=n; i+=lowbit(i))
bsum[i]+=x;
}
long long getsumb(long long x)
{
long long ans=0;
for(long long i=x; i; i-=lowbit(i)) //i要大于0
ans+=bsum[i];
return ans;
}
void updatec(long long k,long long x)
{
for(long long i=k; i<=n; i+=lowbit(i))
csum[i]+=x;
}
long long getsumc(long long x)
{
long long ans=0;
for(long long i=x; i; i-=lowbit(i)) //i要大于0
ans+=csum[i];
return ans;
}
int main()
{
long long T;
cin>>T;
while(T--)
{
long long m;
n=2;
memset(bsum,0,sizeof(bsum));
memset(csum,0,sizeof(csum));
a[0]=0;
cin>>n>>m;
for(long long i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(long long i=1;i<=n;i++)//预处理b
{
b[i]=a[i]-a[i-1];
updateb(i,b[i]);
}
for(long long i=1;i<=n;i++)//预处理c
{
if(b[i]>0) c[i]=b[i];
else c[i]=0;
updatec(i,c[i]);
}
while(m--)
{
long long op;
scanf("%lld",&op);
if(op==2)
{
long long l,r;
scanf("%lld%lld",&l,&r);
long long ans=0;
ans=getsumb(l)+getsumc(r)-getsumc(l);
//cout<<getsumb(l)<<" "<<getsumc(r)<<" "<<getsumc(l)<<endl;
printf("%lld
",ans);
}
else
{
long long l,r,temp3;
long long add1,add2;
scanf("%lld%lld%lld",&l,&r,&temp3);
if(b[l]<0)
{
add1=temp3+b[l];
add1=max(1LL*0,add1);
}
else add1=temp3;
if(b[r+1]>0)
{
add2=min(b[r+1],temp3);
}
else add2=0;
b[l]+=temp3;
b[r+1]-=temp3;
updateb(l,temp3);
updateb(r+1,-temp3);
updatec(l,add1);
updatec(r+1,-add2);
}
}
}
return 0;
}