这里是块状数组

1.引入

分块是一种思想，把一个整体划分为若干个等长的小块，对整块整体处理，打标记。零散块暴力处理。可以做到均摊O(n)O(\sqrt{n})的询问时间复杂度，总时间复杂度O(nn)O(n\sqrt{n})的一个优雅的暴力思想

我们将一个长度为nn的数组分成lenlen个块，那么每个块的长度就是nlen\frac{n}{len}，一般来说这个lenlen取n\sqrt{n},是需要自己用基本不等式去算出来的，但是一般比赛中手算一下理论复杂度，只要块长n\sqrt{n}能过就行。

为啥非要取n\sqrt{n}？因为nn=n\frac{n}{\sqrt{n}}=\sqrt{n},显然用基本不等式可以证明

以下是对1~16进行分块，分块实质上就是3层树，第二层就是块，每个块的子树共有n\sqrt{n}个孩子节点。只不过，块状数组最顶层的信息不用维护。

我们对于一次区间操作，可能有如下的可能

  1. 我们所操作的区间左右端点刚好在一个块里，这时候我们就可以暴力操作。但是我们要注意如果所修改的信息对块整体有影响块也要更新（例如求和），如下图。但是问题我们怎么左右端点是否在一个区间里呢。很简单我们只需要在预处理每个块的时候记录一下各个端点所属于的块的id就行
    ![[粘贴的图像 (4).png]]
    当然下面这个情况也是属于第一种情况的，这种情况也可以保证复杂度是O(n)O(\sqrt{n})


2. 我们所操作的区间左右端点不在一个块，如下图

这种情况我们根据上面所说的定义，散块暴力，大块打tag，橙色就是打tag,绿色代表暴力处理，打tag显然复杂度O(1)O(1)，两边暴力加起来也不会绿色总长度超过2n2\sqrt{n}

优雅的暴力，虽然他的时间复杂度干不过O(nlog2n)O(nlog_2n)的算法，但是他有一个好处，就是他的信息不需要满足结合律，也不需要一层层地传递标记，它具有更高的灵活性。

根据定义就能够写出以下建块的代码，这里我们以P3374——单点加区间和为例子，我们用sum[i]sum[i]数组表示第i个块维护的数字和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init(){
    len=sqrt(n);//块长为根号n
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;//新块的左端点就是上一个块右端点+1
        r[i]=i*len;//处理右端点
    }
    if(r[len]<n){//如果长度不够就在建一个块
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){//注意这里len不在代表块长而是代表块的个数
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;//处理每个点对应块的id
            sum[i]+=a[j];//处理区间和，前缀和的思想
        }
    }
}

单点加如下，要注意对点修改也会对块维护的信息产生影响

1
2
3
4
void add(int x,ll k){
    a[x]+=k;
    sum[pos[x]]+=k;
}

询问如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll query(int fl,int fr){
    int ql=pos[fl],qr=pos[fr];//获取左右端点的对应块id
    ll ret=0;
    if(ql==qr){//如果在一个块里，就情况1暴力处理
        for(int i=fl;i<=fr;i++){
            ret+=a[i];
        }
        return ret;
    }
    //情况二，分散块暴力，整块看tag
    for(int i=fl;i<=r[ql];i++){//对左端点的分散块暴力
        ret+=a[i];
    }
    for(int i=l[qr];i<=fr;i++){//对右端点分散块暴力
        ret+=a[i];
    }
    for(int i=ql+1;i<qr;i++){//对整块直接加tag
        ret+=sum[i];
    }
    return ret;
}

AC代码如下

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
#include<iostream>
#include<cmath>
#define endl '\n'
#define ll long long
using namespace std;
const int MN=5e5+15;
int n,m;
int l[MN],r[MN],pos[MN];
ll a[MN],sum[MN],len;
void add(int x,ll k){
    a[x]+=k;
    sum[pos[x]]+=k;
}
void init(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            sum[i]+=a[j];
        }
    }
}
ll query(int fl,int fr){
    int ql=pos[fl],qr=pos[fr];
    ll ret=0;
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            ret+=a[i];
        }
        return ret;
    }
    for(int i=fl;i<=r[ql];i++){
        ret+=a[i];
    }
    for(int i=l[qr];i<=fr;i++){
        ret+=a[i];
    }
    for(int i=ql+1;i<qr;i++){
        ret+=sum[i];
    }
    return ret;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    while (m--)
    {
        int op;
        ll x,y;
        cin>>op>>x>>y;
        if(op==1){
            add(x,y);
        }else cout<<query(x,y)<<endl;
    }
    
    return 0;
}

2.数列分块

成功解锁了分块，那么现在就来开始做题吧

  1. 单点加，区间求值，就是P3369
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
#include<iostream>
#include<cmath>
#define endl '\n'
#define ll long long
using namespace std;
const int MN=5e5+15;
int n,m;
int l[MN],r[MN],pos[MN];
ll a[MN],sum[MN],len;
void add(int x,ll k){
    a[x]+=k;
    sum[pos[x]]+=k;
}
void init(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            sum[i]+=a[j];
        }
    }
}
ll query(int fl,int fr){
    int ql=pos[fl],qr=pos[fr];
    ll ret=0;
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            ret+=a[i];
        }
        return ret;
    }
    for(int i=fl;i<=r[ql];i++){
        ret+=a[i];
    }
    for(int i=l[qr];i<=fr;i++){
        ret+=a[i];
    }
    for(int i=ql+1;i<qr;i++){
        ret+=sum[i];
    }
    return ret;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    while (m--)
    {
        int op;
        ll x,y;
        cin>>op>>x>>y;
        if(op==1){
            add(x,y);
        }else cout<<query(x,y)<<endl;
    }
    
    return 0;
}
  1. 区间加，区间查询小于等于某个数

显然这个我们入手角度就是对于整个块怎么进行处理，我们显然可以发现。“小于等于”，如果暴力就是O(n)O(n),但是如果我们以有序数组二分那就是O(log2n)O(log_2n)。思想就是对于块要维护有序。对于区间加，对于情况1和情况2的散列块我们需要重新建块进行sort排序。对于查询，我们可以对散列块暴力找，整块二分找。区间加对于大块来说是都加上一个数，不会改变相对大小的顺序所以只需要打tag就可以啦

代码如下

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MN=5e4+15,MQ=700;
int n;
vector<int> bl[MQ];
int l[MQ],r[MQ],pos[MN],tag[MQ],a[MN],len;
void init(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            bl[i].push_back(a[j]);
        }
        sort(bl[i].begin(),bl[i].end());//处理完后要排序
    }
}
void bladd(int fl,int fr,int k){//暴力加
    int ql=pos[fl];
    for(int i=fl;i<=fr;i++){
        a[i]+=k;
    }
    bl[ql].clear();
    for(int i=l[ql];i<=r[ql];i++){
        bl[ql].push_back(a[i]);
    }
    sort(bl[ql].begin(),bl[ql].end());
}
void add(int fl,int fr,int k){//区间加操作
    int ql=pos[fl],qr=pos[fr];
    if(ql==qr){
        bladd(fl,fr,k);
        return;
    }
    bladd(fl,r[ql],k);
    bladd(l[qr],fr,k);
    for(int i=ql+1;i<qr;i++){
        tag[i]+=k;
    }
}
int query(int fl,int fr,int k){
    int ql=pos[fl],qr=pos[fr],ret=0;
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            if(a[i]+tag[ql]<k){
                ret++;
            }
        }
        return ret;
    }
    //两边暴力大块二分
    //分块九讲对于暴力写的是推到一个数组排序后二分，但是直接暴力也是可以的吧
    for(int i=fl;i<=r[ql];i++){
        if(a[i]+tag[ql]<k){
            ret++;
        }
    }
    for(int i=l[qr];i<=fr;i++){
        if(a[i]+tag[qr]<k){
            ret++;
        }
    }
    for(int i=ql+1;i<qr;i++){
        ret+=lower_bound(bl[i].begin(),bl[i].end(),k-tag[i])-bl[i].begin();
    }
    return ret;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    while (n--)
    {
        int op,l,r,k;
        cin>>op>>l>>r>>k;
        if(op==0){
            add(l,r,k);
        }else cout<<query(l,r,k*k)<<endl;
    }
    
    return 0;
}
  1. 区间加，查询某个数的前继

这个其实和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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
const int inf=1e5+7;
int n,len,a[inf];
int bel[inf],L[400],R[400];
int tag[400];
vector<int>h[400];
void baoli(int l,int r,int k)
{
	int in=bel[l];
	for(int i=l;i<=r;i++)
		a[i]+=k;
	h[in].clear();
	for(int i=L[in];i<=R[in];i++)
		h[in].push_back(a[i]);
	sort(h[in].begin(),h[in].end());
}
void update(int l,int r,int k)
{
	int lin=bel[l],rin=bel[r];
	if(lin==rin)
	{
		baoli(l,r,k);
		return;
	}
	baoli(l,R[lin],k);
	baoli(L[rin],r,k);
	for(int i=lin+1;i<rin;i++)
		tag[i]+=k;
}
int query(int l,int r,int k)
{
	vector<int>ls;
	for(int i=l;i<=r;i++)
		ls.push_back(a[i]+tag[bel[l]]);
	sort(ls.begin(),ls.end());
	vector<int>::iterator ret=lower_bound(ls.begin(),ls.end(),k);
	if(ret==ls.begin())return -1;
	return *--ret;
}
int ask(int l,int r,int k)
{
	int lin=bel[l],rin=bel[r];
	if(lin==rin)return query(l,r,k);
	int ans=-1;
	ans=max(ans,query(l,R[lin],k));
	ans=max(ans,query(L[rin],r,k));
	for(int i=lin+1;i<rin;i++)
	{
		vector<int>::iterator ls=lower_bound(h[i].begin(),h[i].end(),k-tag[i]);
		if(ls==h[i].begin())ans=max(ans,-1);
		else ans=max(ans,*--ls+tag[i]);
	}
	return ans;
}
int main()
{
	n=re();len=sqrt(n);
	for(int i=1;i<=n;i++)
		a[i]=re();
	for(int i=1;i<=len;i++)
		L[i]=R[i-1]+1,R[i]=i*len;
	R[len]=n;
	for(int i=1;i<=len;i++)
	{
		for(int j=L[i];j<=R[i];j++)
			bel[j]=i,h[i].push_back(a[j]);
		sort(h[i].begin(),h[i].end());
	}
	for(int i=1;i<=n;i++)
	{
		int op=re(),l=re(),r=re(),k=re();
		if(op)wr(ask(l,r,k)),putchar('\n');
		else update(l,r,k);
	}
	return 0;
}
  1. 区间加，区间求和

我会线段树！！！！

用分块也是可以做的，与第一类型的相比来说只需要维护两个tag，一个区间加tag，一个区间和tag就可以啦

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
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int MN=1e5+15,MQ=700;
int l[MQ],r[MQ],pos[MN],sum[MQ],tag[MQ],a[MN],n,len;
void init(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        r[++len]=n;
        l[len]=r[len-1]+1;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            sum[i]+=a[j];
        }
    }
}
void add(int fl,int fr,int k){
    int ql=pos[fl],qr=pos[fr];
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            a[i]+=k;
            sum[ql]+=k;
        }
        return;
    }
    for(int i=fl;i<=r[ql];i++){
        a[i]+=k;
        sum[ql]+=k;
    }
    for(int i=l[qr];i<=fr;i++){
        a[i]+=k;
        sum[qr]+=k;
    }
    for(int i=ql+1;i<qr;i++){
        tag[i]+=k;
        sum[i]+=(r[i]-l[i]+1)*k;
    }
}
int query(int fl,int fr,int k){
    int ql=pos[fl],qr=pos[fr],ans=0;
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            ans=(ans+a[i]+tag[ql])%k;
        }
        return ans;
    }
    for(int i=fl;i<=r[ql];i++){
        ans=(ans+a[i]+tag[ql])%k;
    }
    for(int i=l[qr];i<=fr;i++){
        ans=(ans+a[i]+tag[qr])%k;
    }
    for(int i=ql+1;i<qr;i++){
        ans=(ans+sum[i])%k;
    }
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    while (n--)
    { 
        int op,l,r,k;
        cin>>op>>l>>r>>k;
        if(op==0){
            add(l,r,k);
        }else cout<<query(l,r,k+1)<<endl;
    }
    
    return 0;
}
  1. 区间开方，区间求和

唉这个题不还是线段树么

P4145

这个题我们不要被101210^{12}吓到了，对其一直开根号，操作次数显然可证明为log2log2nlog_2log_2{n},计算一下大约一个2642^{64}的数开7次就可以开到1或0。解题的关键就是1=1\sqrt{1}=1,0=0\sqrt{0}=0，只要对块进行检测，如果都是1或都是0就打个tag，之后就不用处理啦

代码如下

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
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
const int MN=1e5+15,MQ=710;
bool isok[MQ];
int l[MQ],r[MQ],pos[MN],n,len,m;
ll a[MN],sum[MQ];
void build(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    if(r[len]<n){
        len++;
        l[len]=r[len-1]+1;
        r[len]=n;
    }
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
            sum[i]+=a[j];
        }
    }
}
void kuaikai(int x){
    if(isok[x]) return;
    sum[x]=0;
    isok[x]=1;
    for(int i=l[x];i<=r[x];i++){
        a[i]=sqrt(a[i]);
        sum[x]+=a[i];
        if(a[i]>1) isok[x]=0;
    }
}
void kai(int fl,int fr){
    int ql=pos[fl],qr=pos[fr];
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            sum[ql]-=a[i];
            a[i]=sqrt(a[i]);
            sum[ql]+=a[i];
        }
        return;
    }
    for(int i=fl;i<=r[ql];i++){
        sum[ql]-=a[i];
        a[i]=sqrt(a[i]);
        sum[ql]+=a[i];
    }
    for(int i=l[qr];i<=fr;i++){
        sum[qr]-=a[i];
        a[i]=sqrt(a[i]);
        sum[qr]+=a[i];
    }
    for(int i=ql+1;i<qr;i++){
        kuaikai(i);
    }
}
ll ask(int fl,int fr){
    ll ans=0;
    int ql=pos[fl],qr=pos[fr];
    if(ql==qr){
        for(int i=fl;i<=fr;i++){
            ans+=a[i];
        }
        return ans;
    }
    for(int i=fl;i<=r[ql];i++){
        ans+=a[i];
    }
    for(int i=l[qr];i<=fr;i++){
        ans+=a[i];
    }
    for(int i=ql+1;i<qr;i++){
        ans+=sum[i];
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build();
    cin>>m;
    while (m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(x>y) swap(x,y);
        if(op==0) kai(x,y);
        else cout<<ask(x,y)<<endl;
    }
    
    return 0;
}
  1. 单点修改，单点查询

考虑用vector存块，vector在中间插入的时间复杂度是O(len)O(len)，但是长度是n\sqrt{n},所以修改复杂度其实也是O(n)O(\sqrt{n})

代码如下（粘贴自分块九讲)

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
const int inf=1e5+7;
int n,len,a[inf];
int L[400],R[400];
vector<int>h[inf];
void insert(int id,int k)
{
	for(int i=1;i<=len;i++)
	{
		if(id<=h[i].size())
		{
			vector<int>::iterator ls=h[i].begin()+id-1;
			h[i].insert(ls,k);
			return;
		}
		id-=h[i].size();
	}
}
int ask(int id)
{
	for(int i=1;i<=len;i++)
	{
		if(id<=h[i].size())
			return *(h[i].begin()+id-1);
		id-=h[i].size();
	}
}
int main()
{
	n=re();len=sqrt(n);
	for(int i=1;i<=n;i++)
		a[i]=re();
	for(int i=1;i<=len;i++)
		L[i]=R[i-1]+1,R[i]=i*len;
	R[len]=n;
	for(int i=1;i<=len;i++)
		for(int j=L[i];j<=R[i];j++)
			h[i].push_back(a[j]);
	for(int i=1;i<=n;i++)
	{
		int op=re(),l=re(),r=re(),k=re();
		if(op)wr(ask(r)),putchar('\n');
		else insert(l,r);
	}
	return 0;
}
  1. 区间众数问题 P4168

我们显然可以考虑用桶来去计数，但是问题是只知道一个块的众数很显然没有用是吧。

这里我们考虑众数的性质本身就是统计数字出现的个数，也就是说对于询问[L,R][L,R]区间的众数，其本质可以用[1,R][1,R]的数字个数减去[1,L−1][1,L-1]的数字个数

那么就很简单了，我们开一个二位数组定义为zs，zsi,jzs_{i,j}表示第i个块到第j个块的众数

我们可以使用O(nn)O(n\sqrt{n})的复杂度预处理众数

既然大块的众数已经解决，那么零散块如何处理，我们显然可以发现众数只会有两种情况，第一种就是在中间的大块，第二种就是在零散块中。

暴力找数可以，但是我们需要找出现次数的话，我们可以考虑用vector存储点的出现顺序，显然这个序列满足单调递增的顺序，我们就可以对左端点进行二分，右端点进行二分，右减去左就能够得到顺序啦

注意数据过大，由于二分我们需要经过离散话才可以

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
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int MN=1e5+15,MQ=420;
unordered_map<int,int> um,fum;//存离散化后的值，通过离散化的值找原数
int ls=0;
//zs数字表示从第i个块到第j个块的众数编号
int n,zs[MQ][MQ],l[MQ],r[MQ],pos[MN],a[MN],len,bok[MN];
int tong[MN]{};
vector<int> numpos[MN];
void build(){
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
    r[len]=n;
    for(int i=1;i<=len;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
        }
    }
    for(int i=1;i<=len;i++){//找众数，用桶计数
        memset(tong,0,sizeof(tong));
        int zsnum=0,maxx=0;
        for(int j=l[i];j<=n;j++){
            tong[a[j]]++;
            if(maxx<tong[a[j]]||(maxx==tong[a[j]]&&zsnum>a[j])){//第一个是找到一个出现次数更多的，第二个是要求众数编号最小
                zsnum=a[j];
                maxx=tong[a[j]];
            }
            zs[i][pos[j]]=zsnum;
        }
    }
}
//获取这个数在[l,r]区间内出现次数（即众数），使用二分
int getcishu(int fl,int fr,int k){
    auto start=lower_bound(numpos[k].begin(),numpos[k].end(),fl);
    auto end=upper_bound(numpos[k].begin(),numpos[k].end(),fr);
    return end-start;
}
int query(int fl,int fr){
    int ql=pos[fl],qr=pos[fr];
    int zsnum=0,maxx=0;
    if(ql==qr){
        //暴力找
        memset(tong,0,sizeof(tong));
        for(int i=fl;i<=fr;i++){
            tong[a[i]]++;
            if(maxx<tong[a[i]]||(maxx==tong[a[i]]&&zsnum>a[i])){
                zsnum=a[i];
                maxx=tong[zsnum];
            }
        }
        return bok[zsnum];//反向查找直接返回答案
    }
    //先把答案设置在中间的块
    //显然答案只能在中间块或左右两个块中（如果左中或右中合并最终答案还是中间的众数）
    zsnum=zs[ql+1][qr-1];
    maxx=getcishu(fl,fr,zsnum);
    for(int i=fl;i<=r[ql];i++){
        int ret=getcishu(fl,fr,a[i]);
        if(maxx<ret||(maxx==ret&&zsnum>a[i])){
            zsnum=a[i];
            maxx=ret;
        }
    }
    for(int i=l[qr];i<=fr;i++){
        int ret=getcishu(fl,fr,a[i]);
        if(maxx<ret||(maxx==ret&&zsnum>a[i])){
            zsnum=a[i];
            maxx=ret;
        }
    }
    return bok[zsnum];
}
int main(){
    int m;
    ios::sync_with_stdio(0);
    cin>>n>>m;
    // for(int i=1;i<=n;i++){
    //     int p;
    //     cin>>p;
    //     if(um.find(p)==um.end()){
    //         um[p]=++ls;
    //         fum[ls]=p;
    //     }
    //     a[i]=um[p];
    //     numpos[a[i]].push_back(i);//1~n保证内部单调递增不用sort降级nlogn（?）
    // }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        bok[i]=a[i];
    }
    sort(bok+1,bok+1+n);
    int num=unique(bok+1,bok+1+n)-bok-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(bok+1,bok+1+num,a[i])-bok;
        numpos[a[i]].push_back(i);
    }
    build();
    int bef=0;
    for(int i=1;i<=m;i++){
        int fl,fr;
        cin>>fl>>fr;
        fl=(fl+bef-1)%n+1;
        fr=(fr+bef-1)%n+1;
        if(fl>fr) swap(fl,fr);
        bef=query(fl,fr);
        cout<<bef<<endl;
        // cout<<query(fl,fr)<<endl;
    }
    // len=sqrt(n);
    return 0;
}

3.总结

分块是一种思想，不同的题目有不同的做法，具体情况具体分析。分块强调整块的统一处理，算法设计十分重要。

注意块长直接决定你的时间复杂度，如果根号被卡

可以考虑n+1\sqrt{n}+1,nlgn\sqrt{\frac{n}{lgn}},n+常数\sqrt{n}+常数

YNOI大分块之后再说

引用

  1. Zvelig1205的分块九讲——link