维护一个序列a_i,支持以下两种操作:
第一行包括两个整数n,m,代表数列长度和操作个数。
第二行包括n个整数,代表初始的数列。
接下来m行,每行一个操作,格式见题目描述。
对于每个操作输出一行代表答案。
5 2
1 2 3 4 5
1 2 4 1 2
2 3 5
20
对于20%的数据,$n,m \le 10^3$
对于100%的数据,$n,m \le 10^5$。其他输入的数都非负,且$1 \le l \le r \le n$。
数据保证任何时候数列的总和不超过$10^{18}$。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
struct mainn
{
int w;
int lk,ld;
void p(int tsg,int l,int r,int k,int d)
{
w+=(k+(r-l)*d+k)*(r-l+1)/2;
lk+=k;
ld+=d;
}
}t[1000005];
void pi(int xz,int l,int r)
{
if(!t[xz].ld&&!t[xz].lk) return;
int m=(l+r)>>1;
t[xz<<1].p(xz<<1,l,m,t[xz].lk,t[xz].ld);
t[xz<<1|1].p(xz<<1|1,m+1,r,t[xz].lk+(m-l+1)*t[xz].ld,t[xz].ld);
t[xz].ld=t[xz].lk=0;
}
void bj(int xz,int l,int r,int g,int h,int k,int d)
{
pi(xz,l,r);
if(l==g&&r==h){t[xz].p(xz,l,r,k,d);}
else
{
int m=(l+r)>>1;
t[xz].w+=(k+(h-g)*d+k)*(h-g+1)/2;
if(h<=m)bj(xz<<1,l,m,g,h,k,d);
else if(g>m)bj(xz<<1|1,m+1,r,g,h,k,d);
else
{
bj(xz<<1,l,m,g,m,k,d);
bj(xz<<1|1,m+1,r,m+1,h,k+(m+1-g)*d,d);
}
}
}
int qh(int xz,int l,int r,int l2,int r2)
{
int a=0;
pi(xz,l,r);
if(l2<=l&&r<=r2) return t[xz].w;
int m=(l+r)>>1;
if(l2<=m) a+=qh(xz<<1,l,m,l2,r2);
if(m<r2) a+=qh(xz<<1|1,m+1,r,l2,r2);
return a;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) a[i]+=a[i-1];
int pd;
while(m--)
{
cin>>pd;
if(pd==1)
{
int l,r,k,d;
cin>>l>>r>>k>>d;
bj(1,1,n,l,r,k,d);
}
else
{
int j,k;
cin>>j>>k;
cout<<qh(1,1,n,j,k)+a[k]-a[j-1]<<endl;
}
}
return 0;
}
数据都过了,但是0分,请问问题出在哪?