【模板】数列分块入门-学习笔记

没学过分块的野生大蒟蒻感觉直接写[Violet]蒲公英那一道duliu题有些太难了,所以先来做个铺垫。。。++

1

给定数列,要求支持区间修改,单点查值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1e-8;
const int INF=2147483647;
typedef long long ll;
#define rint register int
inline int read() {
    rint x=0;char c=' ';
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x;
}
inline void print(rint x) {
    rint y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+'0');x%=y;}
}
int n;
const int maxn=500050;
//分块的变量参照数组版线段树
int val[maxn]; //val[i]表示第i个元素
int bl[maxn]; //表示每个元素属于那一块
int unit; //每块大小
int add[maxn]; //加法标记
//add[i]表示val[i]所在的区间被加了多少
void update(int l,int r,int c) {
    //[l,r]+=c
    //处理左端非整块
    for(int i=l;i<=min(bl[l]*unit,r);i++) val[i]+=c;
    //处理右端非整块
    if(bl[l]!=bl[r]) {
        for(int i=(bl[r]-1)*unit+1;i<=r;i++) val[i]+=c;
    } 
    //处理整块
    for(int i=bl[l]+1;i<bl[r];i++) add[i]+=c;
} 
int ask(int x) {
    return val[x]+add[bl[x]];
}
int opt,l,r,c;
int main() {
    n=read();
    for(int i=1;i<=n;i++) val[i]=read();
    //处理每块大小和分块数组初值
    //切记
    unit=sqrt(n);
    for(int i=1;i<=n;i++) bl[i]=(i-1)/unit+1;
    while(n--) {
        opt=read();l=read();r=read();c=read();
        if(opt==0) update(l,r,c);
        if(opt==1) printf("%dn",ask(r));
    }
    return 0;
}
点赞

发表评论