Algorithm/Tree/block.cpp at main · KagariET01/Algorithm · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// [分塊.cpp]
#include<bits/stdc++.h>
using namespace std;
#define INT long long int
#define FN function<INT(INT,INT)>

vector<INT> block;//分塊
vector<INT> arr;//原始數列
INT n;
INT block_sz;

INT sqrt(INT n){
	INT l=0,r=n;
	while(l<r){
		INT mnt=(r-l)/r+l;
		if(mnt*mnt<n){
			l=mnt+1;
		}else{
			r=mnt;
		}
	}
	return l-1;
}

void build(FN merge){
	block.clear();
	block_sz=300;
	block.reserve(n/block_sz+1);
	INT nw=0;
	for(INT i=0;i<n;i++){
		if(!(i%block_sz)){
			nw=arr[i];
		}else{
			nw=merge(nw,arr[i]);
		}
		if((i%block_sz)==block_sz-1){
			block.push_back(nw);
		}
	}
}

void modify(INT x,INT v,FN merge){
	INT l=(x/block_sz)*block_sz;
	INT r=l+block_sz;
	arr[x]=v;
	INT nw=0;
	for(INT i=l;i<r;i++){
		if(!(i%block_sz)){
			nw=arr[i];
		}else{
			nw=merge(nw,arr[i]);
		}
		if((i%block_sz)==block_sz-1){
			block[l/block_sz]=nw;
		}
	}
}

void modify_add(INT x,INT v,FN merge){
	INT l=(x/block_sz)*block_sz;
	INT r=l+block_sz;
	arr[x]+=v;
	INT nw=0;
	for(INT i=l;i<r;i++){
		if(!(i%block_sz)){
			nw=arr[i];
		}else{
			nw=merge(nw,arr[i]);
		}
		if((i%block_sz)==block_sz-1){
			block[l/block_sz]=nw;
		}
	}
}

INT query(INT l,INT r,FN merge){
	INT re=0;
	bool flag=1;
	for(;l<=r && l%block_sz;l++){
		if(flag){
			re=arr[l];
			flag=0;
		}
		else{
			re=merge(re,arr[l]);
		}
	}
	for(;l+block_sz<=r;l+=block_sz){
		re=merge(re,block[l/block_sz]);
	}
	for(;l<=r;l++){
		re=merge(re,arr[l]);
	}
	return re;
}

FN merger=[](INT a,INT b){return max(a,b);};