P2184 贪婪大陆
我们考虑记录每个位置作为左右端点的次数的信息。
- 直接在两个位置处+1.
- 查询区间相当于=左端点在当前区间左侧的区间个数-右端点在
#include<cstdio>
#include<iostream>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
#define ls p<<1
#define rs p<<1|1
const int N=100010,M=4*N;
int n,m,l[M],r[M],a[N];
typedef long long ll;
ll v[M],f[M];
void up(int p){
v[p]=v[ls]+v[rs];
}
void down(int p){
ll &vv=f[p];
if(vv){
v[ls]+=(r[ls]-l[ls]+1)*vv;
f[ls]+=vv;
v[rs]+=(r[rs]-l[rs]+1)*vv;
f[rs]+=vv;
vv=0;
}
}
void build(int p,int ll,int rr){
l[p]=ll,r[p]=rr;
if(ll==rr){
v[p]=a[ll]-a[ll-1];
return;
}
int mid=ll+rr>>1;
build(ls,ll,mid),build(rs,mid+1,rr);
up(p);
}
void update(int p,int ll,int rr,int va){
if(ll<=l[p]&&r[p]<=rr){
v[p]+=(r[p]-l[p]+1ll)*va;
f[p]+=va;
return;
}
int mid=l[p]+r[p]>>1;
down(p);
if(ll<=mid)update(ls,ll,rr,va);
if(rr>mid)update(rs,ll,rr,va);
up(p);
}
ll query(int p,int L,int R){
if(L<=l[p]&&r[p]<=R)return v[p];
int mid=l[p]+r[p]>>1;
down(p);
ll res=0;
if(L<=mid)res=query(ls,L,R);
if(R>mid)res+=query(rs,L,R);
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
E(i, n)cin>>a[i];
build(1,1,n);
E(i, m){
int op,l,r,k,d;
cin>>op;
if(op==1){
cin>>l>>r>>k>>d;
update(1,l,l,k);
if(l<n)update(1,l+1,r,d);
if(r<n)update(1,r+1,r+1,(l-r)*d-k);
}
else{
cin>>d;
cout<<query(1,1,d)<<'\n';
}
}
return 0;
}