[LOJ] 分块九题 1

区间修改，单点查询。
//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

#include<cstdio>

#include<cctype>

#include<cmath>

using namespace std;

const int MAXN=500005;

inline int read_d(){

    int ret=0,f=1;char c;

    while(c=getchar(),!isdigit(c)) f=(c=='-')?-1:1;

    while(isdigit(c)){

        ret=ret*10+c-'0';

        c=getchar();

    }

    return f*ret;

}

int n,m;

int block,num;

int a[MAXN];

int l[MAXN],r[MAXN],bl[MAXN],inc[MAXN];

void build(){

    block=sqrt(n);

    num=n/block;

    if(n%block) num++;

    for(int i=1;i<=num;i++){

        l[i]=(i-1)*block+1;

        r[i]=i*block;

    }

    for(int i=1;i<=n;i++)

        bl[i]=(i-1)/block+1;

    r[num]=n;

}

void updata(int x,int y,int w){

    if(bl[x]==bl[y]){

        for(int i=x;i<=y;i++) a[i]+=w;

        return ;

    }

    for(int i=x;i<=r[bl[x]];i++)

        a[i]+=w;

    for(int i=bl[x]+1;i<=bl[y]-1;i++)

        inc[i]+=w;

    for(int i=l[bl[y]];i<=y;i++)

        a[i]+=w;

}

inline int query(int x){

    return a[x]+inc[bl[x]];

}

int main(){

    n=read_d();m=n;

    for(int i=1;i<=n;i++)

        a[i]=read_d();

    build();

    for(int i=1;i<=m;i++){

        int x,y,z,q;

        q=read_d();x=read_d();

        y=read_d();z=read_d();

        if(q==0) updata(x,y,z);

        else printf("%d\n",query(y));

    }

    return 0;

}
巴特西

[LOJ] 分块九题 1

最新文章

热门文章
