C++14(g++5.4) 解法, 执行用时: 255ms, 内存消耗: 4996K, 提交时间: 2020-02-09 16:24:37

#include<bits/stdc++.h>
#define MAX_INT  ((unsigned)(-1)>>1)
#define MIN_INT  (~MAX_INT)
#define pi 3.1415926535898
typedef long long ll;
#define inf 0x3f3f3f3f
#define infmax 0x3f3f3f3f3f3f3f3f
using namespace std;
ll read()
{
    ll c=0;int flag=1;
    char s;
    while((s=getchar())>'9'||s<'0')if(s=='-')flag=-1;
    c=s-'0';
    while((s=getchar())<='9'&&s>='0') c=c*10+s-'0';
    return c*flag;
}
ll n,m;
ll a[100005];
ll t1[100005];
ll t2[100005];
void add(int L, int R, ll x, ll y)
{
    for(int i=L;i<=n;i+=i&-i){t1[i]+=x; t2[i]+=y;}
    for(int i=R+1;i<=n;i+=i&-i){t1[i]-=x; t2[i]-=y;}
}
ll ask(int p)
{
    ll x=0, y=0;
    for(int i=p;i;i-=i&-i){x+=t1[i]; y+=t2[i];}
    return x + p*y;
}
int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(m--){
        int q;cin>>q;
        if(q==1){
            int l,r,k,d;cin>>l>>r>>k>>d;
            //b[l]+=k;b[r+1]-=k+(r-l)*d;  即区间(l+1,r)值加(r-l)*d
            add(l,r,k-d*l,d);
        }
        else{
            int q;cin>>q;
            cout<<a[q]+ask(q)<<endl;
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 95ms, 内存消耗: 2424K, 提交时间: 2019-12-08 08:56:20

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int n,m,k;
ll C[maxn],D[maxn];
void add(int L, int R, ll x, ll y){
    for(int i=L;i<=n;i+=i&-i){C[i]+=x; D[i]+=y;}
    for(int i=R+1;i<=n;i+=i&-i){C[i]-=x; D[i]-=y;}
}
ll query(int p){
    ll x=0, y=0;
    for(int i=p;i;i-=i&-i){x+=C[i]; y+=D[i];}
    return x + p*y;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x; scanf("%d",&x);
        add(i,i,x,0);
    }
    while(m--){
        int op; scanf("%d",&op);
        if(op==1){
            int L, R; ll k, d;
            scanf("%d %d %lld %lld",&L,&R,&k,&d);
            add(L,R,k-d*L,d);
        }else{
            int p; scanf("%d",&p);
            ll ans = query(p);
            printf("%lld\n",ans);
        }
    }
    return 0;
}