分块

2018-10-18 15:27:12


#include<bits/stdc++.h>
using namespace std;
const int N=5e4+1e3;

int n,k;
int a[N],b[N],lt[N];

void add(int l,int r,int c){
    for(int i=l;i<=min(r,b[l]*k);i++)   a[i]+=c;
    if(b[l]!=b[r])
    for(int i=(b[r]-1)*k+1;i<=r;i++)    a[i]+=c;
    for(int i=b[l]+1;i<=b[r]-1;i++)     lt[i]+=c;
}

int val(int x){
    return a[x]+lt[b[x]];
}

int main(){
    scanf("%d",&n);
    k=sqrt(n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]),b[i]=(i-1)/k+1;
    for(int i=1,opt,l,r,c;i<=n;i++){
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(opt==0)  add(l,r,c);
        if(opt==1)  printf("%d\n",val(r));
    }
}