- 无聊的数列
题解
- 2024-12-25 14:00:47 @
#include<iostream>
using namespace std;
#define ll long long
ll data[100005];
struct point{
ll sum;
ll tag;
} a[400005];
inline int ls(int root){return root<<1;}
inline int rs(int root){return root<<1|1;}
inline void up(int root){a[root].sum=a[ls(root)].sum+a[rs(root)].sum;}
void build(int root,int l,int r){
a[root].tag=0;int mid=(l+r)>>1;
if(l==r){a[root].sum=data[l];return;}
build(ls(root),l,mid);build(rs(root),mid+1,r);
up(root);
}
inline void pd(int root,int l,int r){
int mid=(l+r)>>1;
a[ls(root)].tag+=a[root].tag;
a[rs(root)].tag+=a[root].tag;
a[ls(root)].sum+=a[root].tag*(mid-l+1);
a[rs(root)].sum+=a[root].tag*(r-mid);
a[root].tag=0;
}
void add(int root,int l,int r,int ql,int qr,ll x){
if(ql<=l&&qr>=r){a[root].tag+=x;a[root].sum+=(r-l+1)*x;return;}
int mid=(l+r)>>1;
pd(root,l,r);
if(ql<=mid)add(ls(root),l,mid,ql,qr,x);
if(qr>mid) add(rs(root),mid+1,r,ql,qr,x);
up(root);
return;
}
ll query(int root,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)
return a[root].sum;
int mid=(l+r)>>1,ret=0;
pd(root,l,r);
if(ql<=mid)ret+=query(ls(root),l,mid,ql,qr);
if(qr>mid)ret+=query(rs(root),mid+1,r,ql,qr);
return ret;
}
int main()
{
int n,m,opt,l,r,k,d,t;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>data[i];
for(int i=n-1;i>0;i--)
data[i+1]=data[i+1]-data[i];
build(1,1,n);
for(int i=0;i<m;i++){
cin>>opt;
if(opt==1){
cin>>l>>r>>k>>d;
add(1,1,n,l,l,k);
if(l+1<=r)add(1,1,n,l+1,r,d);
if(r<n)add(1,1,n,r+1,r+1,-(k+d*(r-l)));//注意这里加了判断
}
else{
cin>>t;
cout<<query(1,1,n,1,t)<<endl;
}
}
return 0;
}
2 comments
-
C23lvzekai LV 6 @ 2024-12-25 16:29:09Edited
[手动狗头]
🍋 1👍 1 -
2024-12-25 16:26:35@
6→6→6→6↗,洛谷题解
👀 1
- 1
Information
- ID
- 293
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 40
- Accepted
- 6
- Uploaded By