思路:
对于操作打分来说,整个数的贡献为( r − l + 1 ) ∗ z。而对于区间里的任意一个数,如果在询问操作里被提出,整个区间的贡献都是不计的。所以,对于操作打分来说,将区间里的所有数都加上( r − l + 1 ) ∗ z;对于操作询问x来说,用总贡献减去x所在区间的贡献就是答案。
相当于区间修改+单点查询,套个数据结构就行了。
代码是用的树状数组。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+7; ll a[N],c[N];//原数组和树状数组 ll n,m; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline ll lowbit(ll x){ return x&-x; } void add(ll i,ll k){ while(i<=n){ c[i]+=k; i+=lowbit(i); } } ll sum(ll i){//求a[1]到a[n]的和 ll res=0; while(i>0){ res+=c[i]; i-=lowbit(i); } return res; } int main(){ n=read();m=read(); ll ans=0; while(m--){ ll op=read(); if(op==0){ ll l=read(),r=read(),z=read(); ll now=(r-l+1)*z; ans=ans+now; add(l,now);add(r+1,-now); } else{ ll x=read(); printf("%lld\n",ans-sum(x)); } } return 0; }