书海扬帆的博客

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

分块入门1

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k