数列分块入门1-9

notes

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
#include<bits/stdc++.h>
using namespace std;

#define gc getchar()
#define rd read()
const int N=5e4+100;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
} 

int n,a[N],bk[N];
int len,laz[N];

void add(int l,int r,int v){
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) a[i]+=v;
	else{
		for(int i=l;i<=min(n,bk[l]*len);i++) a[i]+=v;
		for(int i=bk[l]+1;i<=bk[r]-1;i++) laz[i]+=v;
		for(int i=(bk[r]-1)*len+1;i<=r;i++) a[i]+=v;
	}
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,bk[i]=(i-1)/len+1;
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) add(l,r,v);
		else printf("%d\n", a[r]+laz[bk[r]]);
	}
	
	return 0;
}

2

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
#include<bits/stdc++.h>
using namespace std;

#define st(i) ((i-1)*len+1)
#define ed(i) min(i*len,n)
#define gc getchar()
#define rd read()
const int N=5e4+100,L=300;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
} 

int n,a[N];
int bk[N],len,laz[L];
vector<int>vc[L];
inline void reset(int id){
	vc[id].clear();
	for(int i=st(id);i<=ed(id);i++) vc[id].push_back(a[i]);
	sort(vc[id].begin(),vc[id].end());
}

void add(int l,int r,int v){
	if(bk[l]==bk[r]){ for(int i=l;i<=r;i++) a[i]+=v; reset(bk[l]); }
	else{
		for(int i=l;i<=ed(bk[l]);i++) a[i]+=v; reset(bk[l]);
		for(int i=st(bk[r]);i<=r;i++) a[i]+=v; reset(bk[r]);
		for(int i=bk[l]+1;i<=bk[r]-1;i++) laz[i]+=v;
	}
}
int ask(int l,int r,int v){
	int res=0;
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) res+=(a[i]+laz[bk[i]])<v;
	else{
		for(int i=l;i<=ed(bk[l]);i++) res+=(a[i]+laz[bk[i]])<v;
		for(int i=st(bk[r]);i<=r;i++) res+=(a[i]+laz[bk[i]])<v;
		for(int i=bk[l]+1;i<=bk[r]-1;i++) res+=lower_bound(vc[i].begin(),vc[i].end(),v-laz[i])-vc[i].begin();
	}
	return res;
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,bk[i]=(i-1)/len+1;
	for(int i=1;i<=bk[n];i++) reset(i);
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) add(l,r,v);
		else printf("%d\n", ask(l,r,v*v));
	}
	
	return 0;
}

3

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
#include<bits/stdc++.h>
using namespace std;

#define bg(i) ((i-1)*len+1)
#define ed(i) min(i*len,n)
#define gc getchar()
#define rd read()
const int N=1e5+100,M=505,INF=1e9;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,a[N];

int len,bk[N],laz[M];
struct cmp{ bool operator()(int a,int b){ return a>b; } };
multiset<int,cmp>st[M];
//multiset<int>st[M];
inline void chg(int i,int v){ st[bk[i]].erase(st[bk[i]].find(a[i])),a[i]+=v,st[bk[i]].insert(a[i]); }

void add(int l,int r,int v){
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) chg(i,v);
	else{
		for(int i=l;i<=ed(bk[l]);i++) chg(i,v);
		for(int i=bk[l]+1;i<=bk[r]-1;i++) laz[i]+=v;
		for(int i=bg(bk[r]);i<=r;i++) chg(i,v);
	}
}

int ask(int l,int r,int v){
	int res=-1;
	if(bk[l]==bk[r]){
		for(int i=l;i<=r;i++)
			if(a[i]+laz[bk[i]]<v)
				res=max(res,a[i]+laz[bk[i]]);
	}
	else{
		for(int i=l;i<=ed(bk[l]);i++) if(a[i]+laz[bk[i]]<v) res=max(res,a[i]+laz[bk[i]]);
		for(int i=bk[l]+1;i<=bk[r]-1;i++){
			auto it=st[i].upper_bound(v-laz[i]);
			if(it!=st[i].end()) res=max(res,*it+laz[i]);
		}
		for(int i=bg(bk[r]);i<=r;i++) if(a[i]+laz[bk[i]]<v) res=max(res,a[i]+laz[bk[i]]);
	}
	return res;
}


int main(){
	
	n=rd; len=sqrt(n*log2(n));
	for(int i=1;i<=n;i++) a[i]=rd,bk[i]=(i-1)/len+1,st[bk[i]].insert(a[i]);
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) add(l,r,v);
		else printf("%d\n", ask(l,r,v));
	}
	
	return 0;
}

4

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
#include<bits/stdc++.h>
using namespace std;

#define bg(i) ((i-1)*len+1)
#define ed(i) min(i*len,n)
#define gc getchar()
#define rd read()
const int N=5e4+100,M=505,INF=1e9;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,a[N];

int len,bk[N],laz[M],sum[M];

void add(int l,int r,int v){
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) a[i]+=v,sum[bk[i]]+=v;
	else{
		for(int i=l;i<=ed(bk[l]);i++) a[i]+=v,sum[bk[i]]+=v;
		for(int i=bk[l]+1;i<=bk[r]-1;i++) laz[i]+=v;
		for(int i=bg(bk[r]);i<=r;i++) a[i]+=v,sum[bk[i]]+=v;
	}
}

int ask(int l,int r,int MOD){
	int res=0;
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) res=(res+a[i]+laz[bk[i]])%MOD;
	else{
		for(int i=l;i<=ed(bk[l]);i++) res=(res+a[i]+laz[bk[i]])%MOD;
		for(int i=bk[l]+1;i<=bk[r]-1;i++) res=(res+sum[i]+1ll*(ed(i)-bg(i)+1)*laz[i]%MOD)%MOD;
		for(int i=bg(bk[r]);i<=r;i++) res=(res+a[i]+laz[bk[i]])%MOD;
	}
	return res;
}


int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,sum[bk[i]=(i-1)/len+1]+=a[i];
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) add(l,r,v);
		else printf("%d\n", ask(l,r,v+1));
	}
	
	return 0;
}

5

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
#include<bits/stdc++.h>
using namespace std;

#define bg(i) (i*len-len+1)
#define ed(i) min(n,i*len)
#define gc getchar()
#define rd read()
const int N=5e4+100,M=505,INF=1e9;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,a[N];
int len,bk[N],sum[N],m1[N];

inline void chg(int i){ sum[bk[i]]-=a[i],a[i]=sqrt(a[i]),sum[bk[i]]+=a[i]; }

void sqr(int l,int r){
	if(bk[l]==bk[r]) for(int i=l;i<=r;++i) chg(i);
	else{
		for(int i=l;i<=ed(bk[l]);++i) chg(i);
		for(int i=bk[l]+1;i<=bk[r]-1;++i){
			if(m1[i]<=1) continue; m1[i]=sqrt(m1[i]);
			for(int j=bg(i);j<=ed(i);++j) chg(j);
		}
		for(int i=bg(bk[r]);i<=r;++i) chg(i);
	}
}
int ask(int l,int r){
	int res=0;
	if(bk[l]==bk[r]) for(int i=l;i<=r;++i) res+=a[i];
	else{
		for(int i=l;i<=ed(bk[l]);++i) res+=a[i];
		for(int i=bk[l]+1;i<=bk[r]-1;++i) res+=sum[i];
		for(int i=bg(bk[r]);i<=r;++i) res+=a[i];
	}
	return res;
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;++i) a[i]=rd,sum[bk[i]=(i-1)/len+1]+=a[i],m1[bk[i]]=max(m1[bk[i]],a[i]);
	
	for(int i=1,op,l,r,v;i<=n;++i){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) sqr(l,r);
		else printf("%d\n", ask(l,r));
	}

	return 0;
}

此题的并查集做法

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
#include<bits/stdc++.h>
using namespace std;

#define gc getchar()
#define rd read()
const int N=5e4+100;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,a[N];
//dsu
int fa[N];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
//Fenwick_Tree
int t[N];
inline void add(int x,int v){ for(;x<=n;x+=x&-x) t[x]+=v; }
inline int ask(int x){ int res=0; for(;x;x-=x&-x) res+=t[x]; return res; }

inline void chg(int l,int r){
	for(int i=find(l);i<=r;i=find(i+1)){
		if(a[i]>1) add(i,-a[i]),a[i]=sqrt(a[i]),add(i,a[i]);
		if(a[i]<=1) fa[i]=i+1;
	}
}

int main(){
	
	n=rd; for(int i=1;i<=n;i++) a[i]=rd,add(i,a[i]),fa[i]=i; fa[n+1]=n+1;

	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) chg(l,r);
		else printf("%d\n", ask(r)-ask(l-1));
	}
	
	return 0;
}

6

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
#include<bits/stdc++.h>
using namespace std;

#define gc getchar()
#define rd read()
const int N=2e5+100,M=505,INF=1e9;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,len,a[N],cnt=0;
vector<int>vc[M];

inline void bui(){
	int all=0; for(int i=1;!vc[i].empty();vc[i].clear(),++i) for(int j:vc[i]) a[++all]=j;
	for(int i=1,len1=sqrt(all);i<=all;i++) vc[(i-1)/len1+1].push_back(a[i]);
}
inline void ins(int x,int v){
	int bk=1; for(;x>vc[bk].size();x-=vc[bk].size(),++bk);
	vc[bk].insert(vc[bk].begin()+x-1,v);  
	if((++cnt)%len==0) bui();
}
inline int ask(int x){
	int bk=1; for(;x>vc[bk].size();x-=vc[bk].size(),++bk);
	return vc[bk][x-1];
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,vc[(i-1)/len+1].push_back(a[i]);
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) ins(l,r);
		else printf("%d\n", ask(r));
	}

	return 0;
}

7

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
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
using namespace std;

#define bg(i) (i*len-len+1)
#define ed(i) min(n,i*len)
#define gc getchar()
#define rd read()
const int N=2e5+100,M=505,MOD=10007;
void mod(int &a){ a+=a>=MOD?-MOD:a<0?MOD:0; }
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,a[N];
int len,bk[N],mtag[M],atag[M];

void pushdown(int id){
	if(atag[id]==0&&mtag[id]==1) return;
	for(int i=bg(id);i<=ed(id);i++) a[i]=(a[i]*mtag[id]%MOD+atag[id])%MOD;
	atag[id]=0,mtag[id]=1;
}
void add(int l,int r,int v){
	pushdown(bk[l]),pushdown(bk[r]);
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) mod(a[i]+=v);
	else{
		for(int i=l;i<=ed(bk[l]);i++) mod(a[i]+=v);
		for(int i=bk[l]+1;i<=bk[r]-1;i++) mod(atag[i]+=v);
		for(int i=bg(bk[r]);i<=r;i++) mod(a[i]+=v);
	} 
}
void mul(int l,int r,int v){
	pushdown(bk[l]),pushdown(bk[r]);
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) a[i]=1ll*a[i]*v%MOD;
	else{
		for(int i=l;i<=ed(bk[l]);i++) a[i]=1ll*a[i]*v%MOD;
		for(int i=bk[l]+1;i<=bk[r]-1;i++) mtag[i]=1ll*mtag[i]*v%MOD,atag[i]=1ll*atag[i]*v%MOD;
		for(int i=bg(bk[r]);i<=r;i++) a[i]=1ll*a[i]*v%MOD;
	} 
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,bk[i]=(i-1)/len+1,mtag[bk[i]]=1;
	
	for(int i=1,op,l,r,v;i<=n;i++){
		op=rd,l=rd,r=rd,v=rd;
		if(op==0) add(l,r,v);
		else if(op==1) mul(l,r,v);
		else printf("%d\n", (a[r]*mtag[bk[r]]%MOD+atag[bk[r]])%MOD);
	}

	return 0;
}

## 8
```c++
#include<bits/stdc++.h>
using namespace std;

#define bg(i) (i*len-len+1)
#define ed(i) min(n,i*len)
#define gc getchar()
#define rd read()
const int N=2e5+100,M=505,MOD=10007;
void mod(int &a){ a+=a>=MOD?-MOD:a<0?MOD:0; }
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,len,a[N],bk[N],ctag[M];

void pushdown(int id){ if(ctag[id]!=-1) for(int i=bg(id);i<=ed(id);a[i]=ctag[id],i++); ctag[id]=-1; }
int sol(int l,int r,int v){
	int res=0; pushdown(bk[l]),pushdown(bk[r]);
	if(bk[l]==bk[r]) for(int i=l;i<=r;i++) res+=(a[i]==v),a[i]=v;
	else{
		for(int i=l;i<=ed(bk[l]);i++) res+=(a[i]==v),a[i]=v;
		for(int i=bg(bk[r]);i<=r;i++) res+=(a[i]==v),a[i]=v;
		
		for(int i=bk[l]+1;i<=bk[r]-1;i++){
			if(ctag[i]!=-1) res+=(ctag[i]==v)*(ed(i)-bg(i)+1);
			else for(int j=bg(i);j<=ed(i);j++) res+=(a[j]==v);
			ctag[i]=v;
		}
	}
	return res;
}

int main(){
	
	n=rd; len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=rd,bk[i]=(i-1)/len+1;
	for(int i=1;i<=bk[n];i++) ctag[i]=-1;
	
	for(int i=1,l,r,v;i<=n;i++){
		l=rd,r=rd,v=rd;
		printf("%d\n", sol(l,r,v));
	}

	return 0;
}

9

回滚莫队代码

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
#include<bits/stdc++.h>
using namespace std;

#define bg(i) (i*len-len+1)
#define ed(i) min(n,i*len)
#define gc getchar()
#define rd read()
const int N=3e5+100;
int read(){
	int x=0,f=1; char c=gc;
	for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+c-'0';
	return f*x;
}

int n,len,a[N],ls[N],ls_c=0,bk[N];

int ans[N];
struct Q{ int id,l,r; }q[N];
bool cmp0(Q a,Q b){ return bk[a.l]!=bk[b.l]?a.l<b.l:a.r<b.r; }

int dr=0,dans0=0,dans1=0,cnt0[N],cnt1[N];
inline void add0(int x){ ++cnt0[a[x]]; if(cnt0[a[x]]>cnt0[dans0]||(cnt0[a[x]]==cnt0[dans0]&&a[x]<dans0)) dans0=a[x]; }
inline void add1(int x){ ++cnt1[a[x]]; if(cnt1[a[x]]+cnt0[a[x]]>cnt1[dans1]+cnt0[dans1]||(cnt0[a[x]]+cnt1[a[x]]==cnt0[dans1]+cnt1[dans1]&&a[x]<dans1)) dans1=a[x]; }

int main(){
	
	n=rd; len=sqrt(n); for(int i=1;i<=n;i++) bk[i]=(i-1)/len+1,a[i]=rd,ls[++ls_c]=a[i];
	sort(ls+1,ls+ls_c+1); ls_c=unique(ls+1,ls+ls_c+1)-ls-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(ls+1,ls+ls_c+1,a[i])-ls;
	
	for(int i=1,l,r;i<=n;i++){
		q[i]={i,l=rd,r=rd};
		if(bk[l]==bk[r]){
			for(int j=l;j<=r;j++) add0(j);
			ans[i]=dans0;
			dans0=0; for(int j=l;j<=r;j++) cnt0[a[j]]=0;
		}
	} 
	sort(q+1,q+n+1,cmp0);
	
	for(int i=1,id,ql,qr,las=0;i<=n;i++){
		id=q[i].id,ql=q[i].l,qr=q[i].r;
		if(bk[ql]==bk[qr]) continue;
		
		if(bk[ql]!=bk[las]){ dans0=0,dr=ed(bk[ql]); for(int j=1;j<=ls_c;j++) cnt0[j]=0; }
		
		while(dr<qr) add0(++dr);
		for(int j=ql;j<=ed(bk[ql]);j++) add1(j);
		
		if(cnt0[dans0]+cnt1[dans0]>cnt0[dans1]+cnt1[dans1]||(cnt0[dans0]+cnt1[dans0]==cnt0[dans1]+cnt1[dans1]&&dans0<dans1)) dans1=dans0;
		ans[id]=dans1;
		
		dans1=0; for(int j=ql;j<=ed(bk[ql]);j++) cnt1[a[j]]=0;
		las=ql;
	}
	for(int i=1;i<=n;i++) printf("%d\n", ls[ans[i]]);
	
	
	return 0;
}