分块 | CmsBlog

简介

其实，分块是一种思想，而不是一种数据结构。

从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现。

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。

分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。

当然，分块的缺点是渐进意义的复杂度，相较于线段树和树状数组不够好。

不过在大多数问题上，分块仍然是解决这些问题的一个不错选择。

数列分块入门 1

题目描述

第一行输入一个数字 $n$ ( $n \leq 50000$ )。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt$ 、 $l$ 、 $r$ 、 $c$ ，以空格隔开。

若 $opt = 0$ ，表示将位于 $[l,r]$ 的之间的数字都加 $c$ 。

若 $opt = 1$ ，表示询问 $a_r$ 的值（ $l$ 和 $c$ 忽略）。

思路

我们考虑分块，将数列强行拆分为 $\sqrt n$ 块。

对于每一次区间加操作，不包含完整块的位置暴力修改，包含完整一个块的元素直接在块上打标记。

对于查询操作，只需要输出查询的数加上该位置所在块的标记即可。

代码

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

const int BLOCK_SIZE = 710;

int N;
int Num[500010];
int op , l , r , c;

int GetBel(int Pos) { //第 Pos 个元素属于第几个块
	return (Pos - 1) / BLOCK_SIZE + 1;
}

int Tag[710]; //每个块的标记

int main() {
	scanf("%d" ,&N);
	for(int i = 1; i <= N; i++) {
		scanf("%d" ,Num + i);
	}
	
	while(N--) {
		scanf("%d%d%d%d" ,&op ,&l ,&r ,&c);
		if(op == 0) {
			int L = GetBel(l);
			int R = GetBel(r);
			if(L == R) { //同一块内，暴力
				for(int i = l; i <= r; i++) {
					Num[i] += c;
				}
			}
			else {
				for(int i = l; i <= (min(L * BLOCK_SIZE , r)); i++) { //块外元素，暴力
					Num[i] += c;
				}
				for(int i = L + 1; i <= R - 1; i++) { //整块元素，打标记
					Tag[i] += c;
				}
				
				for(int i = ((R - 1) * BLOCK_SIZE + 1); i <= r; i++) {//块外元素，暴力
					Num[i] += c;
				}
			}
		}
		else {
			printf("%d\n" ,Tag[GetBel(r)] + Num[r]);
		}
	} 
	
	return 0;
}

数列分块入门 2

题目描述

第一行输入一个数字 $n$ ( $n \leq 50000$ )。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt$ 、 $l$ 、 $r$ 、 $c$ ，以空格隔开。

若 $opt = 0$ ，表示将位于 $[l,r]$ 的之间的数字都加 $c$ 。

若 $opt = 1$ ，表示询问位于 $[l,r]$ 中小于 $c^2$ 的数字个数。

思路

我们考虑分块，将数列强行拆分为 $\sqrt n$ 块。

由于要查询区间中小于某个数的个数，我们考虑用一个 std::vector 存下每一个块内的元素，并对每个块排序。

对于修改操作，可能会更改不完整的块的顺序，我们直接暴力修改加重构那个块，但对于完整的块显然不会改变，直接打标记。

对于查询操作，块外元素暴力寻找，块内元素二分（这就是为什么要排序的原因）。

代码

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

const int MAXN = 5e4 + 10 , BLOCK_SIZE = 230;

int GetBel(int Pos) {
    return (Pos - 1) / BLOCK_SIZE + 1;
}

int N , Num[MAXN];

vector<int> Block[BLOCK_SIZE];

int Tag[BLOCK_SIZE] , Left[BLOCK_SIZE] , Right[BLOCK_SIZE];
int op , l , r , c;

void ReBuild(int x) {
    Block[x].clear();
    for(int i = Left[x]; i <= Right[x]; i++) {
        Block[x].push_back(Num[i]);
    }
    sort(Block[x].begin() , Block[x].end());
}

void Add(int l , int r , int c) {
    int Bel_l = GetBel(l);
    int Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(int i = l; i <= r; i++) {
            Num[i] += c;
        }
        ReBuild(Bel_l);
    }

    else {
        for(int i = l; i <= Right[Bel_l]; i++) {
            Num[i] += c;
        }
        ReBuild(Bel_l);
        for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
            Tag[i] += c;
        }
        for(int i = Left[Bel_r]; i <= r; i++) {
            Num[i] += c;
        }
        ReBuild(Bel_r);
    }
}

int Query(int l , int r , int c) {
    c *= c;

    int res = 0;
    int Bel_l = GetBel(l);
    int Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(int i = l; i <= r; i++) {
            if(Num[i] + Tag[Bel_l] < c) {
                res++;
            }
        }
    }
    else {
        for(int i = l; i <= Right[Bel_l]; i++) {
            if(Num[i] + Tag[Bel_l] < c) {
                res++;
            }
        }

        for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
            res += lower_bound(Block[i].begin() , Block[i].end() , c - Tag[i]) - Block[i].begin();
        }

        for(int i = Left[Bel_r]; i <= r; i++) {
            if(Num[i] + Tag[Bel_r] < c) {
                res++;
            }
        }
    }

    return res;
}

int main() {
    scanf("%d" ,&N);
    for(int i = 1; i <= N; i++) {
        scanf("%d" ,Num + i);
    }

    for(int i = 1; i <= N; i++) {
        Block[GetBel(i)].push_back(Num[i]);
    }

    for(int i = 1; i <= GetBel(N); i++) {
        Left[i] = Right[i - 1] + 1;
        Right[i] = min(BLOCK_SIZE * i , N);
        sort(Block[i].begin() , Block[i].end());
    }

    while(N--) {
        scanf("%d%d%d%d" ,&op ,&l ,&r ,&c);
        if(op == 0) {
            Add(l , r , c);
        }
        else {
            printf("%d\n" ,Query(l , r , c));
        }
    }

    return 0;
}

数列分块入门 3

题面描述

第一行输入一个数字 $n$ ( $n \leq 10^5$ )。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt$ 、 $l$ 、 $r$ 、 $c$ ，以空格隔开。

若 $opt = 0$ ，表示将位于 $[l,r]$ 的之间的数字都加 $c$ 。

若 $opt = 1$ ，表示询问位于 $[l,r]$ 中 $c$ 的前驱（没有输出 $-1$ ）。

思路

我们考虑分块，将数列强行拆分为 $\sqrt n$ 块。

这道题和第二题差不多，只需要稍作更改即可。

但是这道题想告诉大家，当时间够的情况下，可以使用不同的数据结构来维护块。

比如本题，使用 std::set 就可以极大的降低编码/时间复杂度（因为相同元素的出现）。

代码

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

const int MAXN = 1e5 + 10 , BLOCK_SIZE = 1000;

set<int> Block[BLOCK_SIZE];

int N;

int Num[MAXN];
int Tag[BLOCK_SIZE];
int Left[BLOCK_SIZE] , Right[BLOCK_SIZE];

int op , l , r , c;

int GetBel(int Pos) {
    return (Pos - 1) / BLOCK_SIZE + 1;
}

void Add(int l , int r , int c) {
    int Bel_l = GetBel(l);
    int Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(int i = l; i <= r; i++) {
            Block[Bel_l].erase(Num[i]);
            Num[i] += c;
            Block[Bel_l].insert(Num[i]);
        }
    }
    else {
        for(int i = l; i <= Right[Bel_l]; i++) {
            Block[Bel_l].erase(Num[i]);
            Num[i] += c;
            Block[Bel_l].insert(Num[i]);
        }
        for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
            Tag[i] += c;
        }
        for(int i = Left[Bel_r]; i <= r; i++) {
            Block[Bel_r].erase(Num[i]);
            Num[i] += c;
            Block[Bel_r].insert(Num[i]);
        }
    }
}

int Query(int l , int r , int c) {
    int res = -1;

    int Bel_l = GetBel(l);
    int Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(int i = l; i <= r; i++) {
            if(Num[i] + Tag[Bel_l] < c) {
                res = max(res , Num[i] + Tag[Bel_l]);
            }
        }
    }
    else {
        for(int i = l; i <= Right[Bel_l]; i++) {
            if(Num[i] + Tag[Bel_l] < c) {
                res = max(res , Num[i] + Tag[Bel_l]);
            }
        }
        for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
            set<int>::iterator it = Block[i].lower_bound(c - Tag[i]);
            if(it == Block[i].begin()) continue;
            it--;
            res = max(res , *it + Tag[i]);
        }
        for(int i = Left[Bel_r]; i <= r; i++) {
            if(Num[i] + Tag[Bel_r] < c) {
                res = max(res , Num[i] + Tag[Bel_r]);
            }
        }
    }

    return res;
}

int main() {
    scanf("%d" ,&N);
    for(int i = 1; i <= N; i++) {
        scanf("%d" ,Num + i);
        Block[GetBel(i)].insert(Num[i]);
    }
    for(int i = 1; i <= GetBel(N); i++) {
        Left[i] = Right[i - 1] + 1;
        Right[i] = min(i * BLOCK_SIZE , N);
    }
    while(N--) {
        scanf("%d%d%d%d" ,&op ,&l ,&r ,&c);
        if(op == 0) {
            Add(l , r , c);
        }
        else {
            printf("%d\n" ,Query(l , r , c));
        }
    }
    return 0;
}

数列分块入门 4

题目描述

第一行输入一个数字 $n$ ( $n \leq 50000$ )。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt$ 、 $l$ 、 $r$ 、 $c$ ，以空格隔开。

若 $opt = 0$ ，表示将位于 $[l,r]$ 的之间的数字都加 $c$ 。

若 $opt = 1$ ，表示询问位于 $[l,r]$ 的所有数的和 $\operatorname{mod}\ (c+1)$ 。

思路

我们考虑分块，将数列强行拆分为 $\sqrt n$ 块。

对于每一个块要维护的信息多了一个区间和。

对于区间加操作，块内元素打标记，块外元素暴力修改并维护区间和。

对于查询操作，块内元素加上标记乘块长和区间和，块外元素暴力即可。

代码

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

typedef long long LL;

const LL MAXN = 50010 , BLOCK_SIZE = 320;

LL GetBel(LL Pos) {
    return (Pos - 1) / BLOCK_SIZE + 1;
}

LL Left[MAXN] , Right[MAXN] , Sum[MAXN] , Tag[MAXN];
LL Num[MAXN];
LL N , op , l , r , c;

void Add(LL l , LL r , LL c) {
    LL Bel_l = GetBel(l);
    LL Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(LL i = l; i <= r; i++) {
            Num[i] += c;
            Sum[Bel_l] += c;
        }
    }
    else {
        for(LL i = l; i <= Right[Bel_l]; i++) {
            Num[i] += c;
            Sum[Bel_l] += c; 
        }
        for(LL i = Bel_l + 1; i <= Bel_r - 1; i++) {
            Tag[i] += c;
        }
        for(LL i = Left[Bel_r]; i <= r; i++) {
            Num[i] += c;
            Sum[Bel_r] += c; 
        }
    }
}

LL Query(LL l , LL r) {
    LL res = 0;

    LL Bel_l = GetBel(l);
    LL Bel_r = GetBel(r);

    if(Bel_l == Bel_r) {
        for(LL i = l; i <= r; i++) {
            res += Num[i] + Tag[Bel_l];
        }
    }
    else {
        for(LL i = l; i <= Right[Bel_l]; i++) {
            res += Num[i] + Tag[Bel_l];
        }
        for(LL i = Bel_l + 1; i <= Bel_r - 1; i++) {
            res += BLOCK_SIZE * Tag[i];
            res += Sum[i];
        }
        for(LL i = Left[Bel_r]; i <= r; i++) {
            res += Num[i] + Tag[Bel_r];
        }
    }

    return res;
}

int main() {
    scanf("%lld" ,&N);
    for(int i = 1; i <= N; i++) {
        scanf("%lld" ,Num + i);
        Sum[GetBel(i)] += Num[i];
    }

    for(int i = 1; i <= GetBel(N); i++) {
        Left[i] = Right[i - 1] + 1;
        Right[i] = min(i * BLOCK_SIZE , N);
    }

    while(N--) {
        scanf("%lld%lld%lld%lld" ,&op ,&l ,&r ,&c);
        if(op == 0) {
            Add(l , r , c);
        }
        else {
            printf("%lld\n" ,Query(l , r) % (c + 1));
        }
    }

    return 0;
}

数列分块入门 5

题目描述

第一行输入一个数字 $n$ ( $n \leq 50000$ )。

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入四个数字 $opt$ 、 $l$ 、 $r$ 、 $c$ ，以空格隔开。

若 $opt = 0$ ，表示将位于 $[l,r]$ 的之间的数开方。对于区间中每个 $a_i(l \le i \le r) \leftarrow \lfloor \sqrt a_i \rfloor$

若 $opt = 1$ ，表示询问 $[l,r]$ 的所有数字的和。

思路

我们考虑分块，将数列强行拆分为 $\sqrt n$ 块。

观察可以发现，每个数字经过几次开方后，就会变为 $1$ 。

所以我们只需记录每个块中的数字是否等于 $1$ 即可。

代码

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

const int MAXN = 5e4 + 10;
const int BLOCK_SIZE = 250;

int N;
int Num[MAXN];
int op , l , r , c;
bool Is_One[BLOCK_SIZE + 10];
int Left[BLOCK_SIZE + 10] , Right[BLOCK_SIZE + 10];
int Sum[BLOCK_SIZE + 10];

int GetBel(int Pos) {
	return (Pos - 1) / BLOCK_SIZE + 1;
}

void Change_One_Block(int Pos) {
	Sum[Pos] = 0;
	Is_One[Pos] = true;
	for(int i = Left[Pos]; i <= Right[Pos]; i++) {
		Num[i] = sqrt(Num[i]);
		Sum[Pos] += Num[i];
        if(Num[i] > 1) Is_One[Pos] = false;
	}
}

void Change(int l , int r) {
	int Bel_l = GetBel(l);
	int Bel_r = GetBel(r);
	
	if(Bel_l == Bel_r) {
		for(int i = l; i <= r; i++) {
			Sum[GetBel(i)] -= Num[i];
			Num[i] = sqrt(Num[i]);
			Sum[GetBel(i)] += Num[i];
		}
	}
	else {
		for(int i = l; i <= Right[Bel_l]; i++) {
			Sum[GetBel(i)] -= Num[i];
			Num[i] = sqrt(Num[i]);
			Sum[GetBel(i)] += Num[i];
		}
		for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
			if(Is_One[i] == false) {
				Change_One_Block(i);
			}
		}
		for(int i = Left[Bel_r]; i <= r; i++) {
			Sum[Bel_r] -= Num[i];
			Num[i] = sqrt(Num[i]);
			Sum[Bel_r] += Num[i];
		}
	}
}

int Query(int l , int r) {
	int Bel_l = GetBel(l);
	int Bel_r = GetBel(r);
	
	int res = 0;
	
	if(Bel_l == Bel_r) {
		for(int i = l; i <= r; i++) {
			res += Num[i];
		}	
	}
	else {
		for(int i = l; i <= Right[Bel_l]; i++) {
			res += Num[i];
		}
		for(int i = Bel_l + 1; i <= Bel_r - 1; i++) {
			res += Sum[i];
		}
		for(int i = Left[Bel_r]; i <= r; i++) {
			res += Num[i];
		}
	}
	
	return res;
}

int main() {
	scanf("%d" ,&N);
	for(int i = 1; i <= N; i++) {
		scanf("%d" ,Num + i);
        Sum[GetBel(i)] += Num[i];
	}

    for(int i = 1; i <= GetBel(N); i++) {
        Left[i] = Right[i - 1] + 1;
        Right[i] = min(i * BLOCK_SIZE , N);
    }

	while(N--) {
		scanf("%d%d%d%d" ,&op ,&l ,&r ,&c);
		if(op == 0) {
			Change(l , r);
		}
		if(op == 1) {
			printf("%d\n" ,Query(l , r));
		}
	}
	return 0;
}

[Ynoi2019 模拟赛] Yuno loves sqrt technology III

题目描述

给你一个长为 $n$ 的序列 $a$ ， $m$ 次询问，每次查询一个区间的众数的出现次数，强制在线。

$1\leq n,m \leq 5\times 10^5$，$0 \leq a_i\leq 10^9$。

(时间限制:2.00s 内存限制:62.50MB)

思路

由于 Ynoi 的毒瘤性质，这题必须要线性空间。

我们使用 std::vector 存储相同数字出现的位置，空间复杂度 $O(n)$ (vector 在一下记作 Appear)，使用一个数组 Lacation 记录第 $i$ 个元素在该元素的 vector 中第几个出现了，空间复杂度 $O(n)$ 。

再开一个数组 Interval_Mode 记录完整两块之间众数的出现次数，空间复杂度 $O(n)$ 。

对于查询区间众数：

在相同块内的情况下，直接用分块暴力求解（桶）就行。
考虑包含完整块的情况。设当前寻找到的众数出现次数为 res ，对于左区间的每一个数，它如果可以成为区间众数，Appear[Num[i]][Lacation[i] + res] 必须存在，这样就在往后找在范围内所有的这个数字，更新 res 。
右侧同理。

时间复杂度： $O(n\sqrt n)$
空间复杂度： $O(n)$

代码

#include <bits/stdc++.h>

const int MAXN = 5e5 + 10;
const int BLOCK_SIZE = 710;

namespace IO {
    int _tmp_write[50] = {0}; // __int128_t max
    int _cnt_write = 0;    
#ifdef FILE_IO
    static int8_t _tmp_put = 0;
    static const u_int32_t _max_buf_size = 65536;
    static int8_t _buf[_max_buf_size], *_buf_now = _buf, *_buf_end = _buf;
    static int8_t _obuf[_max_buf_size], *_obuf_now = _obuf;
    #define getchar() (_buf_now == _buf_end && (_buf_end = (_buf_now = _buf) + fread(_buf, 1, _max_buf_size, stdin), _buf_now == _buf_end) ? EOF : *_buf_now++)
    #define putchar(x) do { _tmp_put = x; if (_obuf_now - _obuf >= _max_buf_size) { fwrite(_obuf, _obuf_now - _obuf, 1, stdout); _obuf_now = _obuf; } *_obuf_now++ = _tmp_put; } while (false)
    #define main_return do { fwrite(_obuf, _obuf_now - _obuf, 1, stdout); fclose(stdin); fclose(stdout); return 0; } while (false) // main 函数结尾一定要调用！！！
#endif
    template <typename _Tp> inline int read(_Tp& _r) {
        int ch = getchar(); bool f = false; _r = 0;
        while (ch < 48 || ch > 57) { if (ch == EOF) return EOF; if (ch == 45) f ^= 1; ch = getchar(); }
        while (ch > 47 && ch < 58) { _r = (_r << 1) + (_r << 3) + ch - 48; ch = getchar(); }
        if (f) _r = -_r; return ch;
    }
    template <typename _Tp> inline int uread(_Tp& _r) {
        int ch = getchar(); _r = 0;
        while (ch < 48 || ch > 57) { if (ch == EOF) return EOF; ch = getchar(); }
        while (ch > 47 && ch < 58) { _r = (_r << 1) + (_r << 3) + ch - 48; ch = getchar(); }
        return ch;
    }
    template <typename _Tp> inline int sread(_Tp* _r) {
        int ch = getchar(); int cnt = 0; _r[0] = 0;
        while (ch == 9 || ch == 10 || ch == 32 || ch == EOF) { if (ch == EOF) return EOF; ch = getchar(); }
        while (ch != 9 && ch != 10 && ch != 32 && ch != EOF) { _r[cnt++] = ch; _r[cnt] = 0; ch = getchar(); }
        return ch;
    }
    inline int strread(std::string& _r) {
        int ch = getchar(); _r = "";
        while (ch == 9 || ch == 10 || ch == 32 || ch == EOF) { if (ch == EOF) return EOF; ch = getchar(); }
        while (ch != 9 && ch != 10 && ch != 32 && ch != EOF) { _r += ch; ch = getchar(); }
        return ch;
    }
    template <typename _Tp> inline void write(_Tp _w, int8_t _end = 10) {
        if (_w == 0) { putchar(48); return; } if (_w < 0) { putchar(45); _w = -_w; } _cnt_write = 0;
        while (_w) { _tmp_write[_cnt_write++] = _w % 10 + 48; _w /= 10; }
        while (_cnt_write) putchar(_tmp_write[--_cnt_write]);
        putchar(_end); return;
    }
    template <typename _Tp> inline void uwrite(_Tp _w, int8_t _end = 10) {
        if (_w == 0) { putchar(48); return; } _cnt_write = 0;
        while (_w) { _tmp_write[_cnt_write++] = _w % 10 + 48; _w /= 10; }
        while (_cnt_write) putchar(_tmp_write[--_cnt_write]);
        putchar(_end); return;
    }
    template <typename _Tp> inline void swrite(_Tp* _w, int8_t _end = 10) {
        for (int i = 0; i < strlen(_w); i++) putchar(_w[i]);
        putchar(_end); return;
    }
    inline void strwrite(std::string _w, int8_t _end = 10) {
        for (int i = 0; i < _w.size(); i++) putchar(_w[i]);
        putchar(_end); return;
    }
};

int Max(int a , int b) {
    return a > b ? a : b;
}

int Min(int a , int b) {
    return a < b ? a : b;
}

// 以上为卡常

int N , M , Last_Ans , Ans;
int Num[MAXN] , Num2[MAXN]; //数组 + 离散化
int Left[BLOCK_SIZE] , Right[BLOCK_SIZE]; //每个块的左右端点

std::vector<int> Appear[MAXN]; //每个数在 Num 数组中出现的下标
int Lacation[MAXN]; //第 i 个数在 vector 中出现的下标
int Count[MAXN]; //桶

int Interval_Mode[BLOCK_SIZE][BLOCK_SIZE]; //Interval_Mode[i][j] 表示 块i 到 块j 众数出现次数

int GetBel(int Pos) {
    return (Pos - 1) / BLOCK_SIZE + 1;
}

void InItBlock() {
    for(int i = 1; i <= GetBel(N); i++) { //预处理每个块的左右端点
        Left[i] = Right[i - 1] + 1;
        Right[i] = i * BLOCK_SIZE;
    }

    Right[GetBel(N)] = N;

    for(int i = 1; i <= GetBel(N); i++) { //暴力计算 Insertval_Mode 数组
        memset(Count , 0 , sizeof Count);
        for(int j = i; j <= GetBel(N); j++) {
            Interval_Mode[i][j] = Interval_Mode[i][j - 1];
            for(int k = Left[j]; k <= Right[j]; k++) {
                Count[Num[k]]++;
                Interval_Mode[i][j] = Max(Interval_Mode[i][j] , Count[Num[k]]);
            }
        }
    }
}

int Query(int l , int r) {
    int res = 0;

    int Bel_l = GetBel(l);
    int Bel_r = GetBel(r);

    if(Bel_l == Bel_r) { // 在同一块，暴力算
        for(int i = l; i <= r; i++) { 
            Count[Num[i]] = 0;
        }
        for(int i = l; i <= r; i++) {
            Count[Num[i]]++;
            res = Max(res , Count[Num[i]]);
        }
    }
    else { //不在同一块
        res = Interval_Mode[Bel_l + 1][Bel_r - 1];
        for(int i = l; i <= Right[Bel_l]; i++) { //完整块左侧是否可能有数字成为众数
            int pos = Lacation[i];
            int v = pos + res;
            while(v < Appear[Num[i]].size() && Appear[Num[i]][v] <= r) { //在数量足够的情况下，改变答案的数量
                res++;
                v++;
            }
        }

        for(int i = Left[Bel_r]; i <= r; i++) { // 完整块右侧是否可能有数字成为众数
            int pos = Lacation[i];
            int v = pos - res;
            while(v >= 0 && Appear[Num[i]][v] >= l) { 
                res++;
                v--;
            }
        }
    }
    return res;
}

int main() {
    IO::read(N);
    IO::read(M);
    for(int i = 1; i <= N; i++) {
        IO::read(Num[i]);
        Num2[i] = Num[i];
    }

    std::sort(Num2 + 1 , Num2 + 1 + N);
    int Sum = std::unique(Num2 + 1 , Num2 + 1 + N) - 1 - Num2;

    for(int i = 1; i <= N; i++) {
        Num[i] = std::lower_bound(Num2 + 1 , Num2 + 1 + Sum , Num[i]) - Num2;
    }

    for(int i = 1; i <= N; i++) {
        Appear[Num[i]].push_back(i);
        Lacation[i] = Appear[Num[i]].size() - 1;
    }

    InItBlock();

    while(M--) {
        int l , r;
        IO::read(l);
        IO::read(r);

        l ^= Last_Ans;
        r ^= Last_Ans;

        Ans = Query(l , r);

        IO::write(Ans , '\n');

        Last_Ans = Ans;
    }

    return 0;
}

[Ynoi2018] 未来日记

题目描述

给了你一个长为 $n$ 的序列 $a$ ，有 $m$ 次操作。

把区间 $[l,r]$ 内所有的 $x$ 变成 $y$ 。
查询区间 $[l,r]$ 内第 $k$ 小值。

(时间限制:1.00s 内存限制:512.00MB)

思路

最初分块。

看到值域只有 $10^5$ 考虑在值域上也进行根号分块。

记 $Cnt1[x][i]$ 表示前 $x$ 块中数字 $i$ 的次数；

记 $Cnt2[x][i]$ 表示前 $x$ 块中数字出现在值域 $i$ 的次数。

这样我们就可以非常方便的做到查询 $k$ 小值的操作：

先利用前缀相减在加快外元素求助区间出现在每个值域的数字个数和每个数字的个数，再枚举寻找到 $k$ 小值出现的值域。最后在这个值域内查询即可。由于都是 $\sqrt n$ 个元素，所以总时间复杂度为 $O(\sqrt n)$ 。

再来看修改，套路考虑并查集。

记 $Id[x][i]$ 表示第 $x$ 块中第一个值为 $i$ 的下标；

记 $ReId[x][i]$ 表示第 $x$ 块中下表 $i$ 对应的值；

记 $Pos[i]$ 表示每个元素的 $Id$ 。

如果要还原序列，只需让 $a_i = ReId[Bel[i]][Pos[i]]$

接下来进行分类讨论：

区间内无 $x$ ，跳过；
区间内有 $x$ 无 $y$ , 则将 $Id[Bel][y] = Id[Bel][x],ReId[Bel][Id[Bel][x]] = y,Id[Bel][x] = 0$
区间内有 $x$ 有 $y$ ，还原区间，暴力。此时值的个数减少了 $1$ ，最多有 $n + m$ 种值域，均摊为 $O((n + m) \sqrt n)$

对于更新 $Cnt$ 数组，考虑先差分在累加再前缀，时间复杂度 $O(\sqrt n)$

代码

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

const int MAXN = 1e5 + 5;
const int BS = 620;

namespace Fread
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S, *T;
    inline char getchar()
    {
        if (S == T)
        {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return '\n';
        }
        return *S++;
    }
}
namespace Fwrite
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush()
    {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c)
    {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct NTR
    {
        ~NTR()
        {
            flush();
        }
    } ztr;
}

#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}


int N , M , Num[MAXN + 10] , Bel[MAXN + 10];

int BLOCK , op , l , r , k , x , y;

int Id[BS][MAXN + 10] , ReId[BS][MAXN + 10];
int Left[BS] , Right[BS];
int Pos[MAXN + 10];

int Cnt1[BS][BS] , Cnt2[BS][MAXN + 10];

int Query_Cnt1[BS] , Query_Cnt2[MAXN + 10];

inline void Build(int x) {
    int ToT = 0;
    for(int i = 1; i <= BLOCK; i++) {
        Id[x][ReId[x][i]] = 0;
    }
    for(int i = Left[x]; i <= Right[x]; i++) {
        if(!Id[x][Num[i]]) {
            Id[x][Num[i]] = ++ToT;
            ReId[x][ToT] = Num[i];
        }
    }
    for(int i = Left[x]; i <= Right[x]; i++) {
        Pos[i] = Id[x][Num[i]];
    }
}

inline void UpDateValue(int x) {
    for(int i = Left[x]; i <= Right[x]; i++) {
        Num[i] = ReId[x][Pos[i]];
    }
}

inline void DutyChange(int l , int r , int x , int y) {
    for(int i = l; i <= r; i++) {
        if(Num[i] == x) {
            Cnt1[Bel[l]][Bel[x]]--;
            Cnt1[Bel[l]][Bel[y]]++;
            Cnt2[Bel[l]][x]--;
            Cnt2[Bel[l]][y]++;
            Num[i] = y;
        }
    }
}

inline void Change(int l , int r , int x , int y) {
    if(x == y || Cnt2[Bel[r]][x] - Cnt2[Bel[l] - 1][x] == 0) return;
    for(int i = Bel[N]; i >= Bel[l]; i--) {
        Cnt2[i][x] -= Cnt2[i - 1][x];
        Cnt2[i][y] -= Cnt2[i - 1][y];
        Cnt1[i][Bel[x]] -= Cnt1[i - 1][Bel[x]];
        Cnt1[i][Bel[y]] -= Cnt1[i - 1][Bel[y]];
    }

    if(Bel[l] == Bel[r]) {
        UpDateValue(Bel[l]);
        DutyChange(l , r , x , y);
        Build(Bel[l]);
        for(int i = Bel[l]; i <= Bel[N]; i++) {
            Cnt2[i][x] += Cnt2[i - 1][x];
            Cnt2[i][y] += Cnt2[i - 1][y];
            Cnt1[i][Bel[x]] += Cnt1[i - 1][Bel[x]];
            Cnt1[i][Bel[y]] += Cnt1[i - 1][Bel[y]];
        }
        return;
    }

    UpDateValue(Bel[l]);
    DutyChange(l , Right[Bel[l]] , x , y);
    Build(Bel[l]);

    UpDateValue(Bel[r]);
    DutyChange(Left[Bel[r]] , r , x , y);
    Build(Bel[r]);

    for(int i = Bel[l] + 1; i <= Bel[r] - 1; i++) {
        if(!Cnt2[i][x]) continue;
        if(Cnt2[i][y]) {
            UpDateValue(i);
            DutyChange(Left[i] , Right[i] , x , y);
            Build(i);
        }
        else {
            Cnt1[i][Bel[y]] += Cnt2[i][x];
            Cnt1[i][Bel[x]] -= Cnt2[i][x];
            Cnt2[i][y] = Cnt2[i][x];
            Cnt2[i][x] = 0;
            Id[i][y] = Id[i][x];
            ReId[i][Id[i][x]] = y;
            Id[i][x] = 0;
        }
    }

    for(int i = Bel[l]; i <= Bel[N]; i++) {
        Cnt2[i][x] += Cnt2[i - 1][x];
        Cnt2[i][y] += Cnt2[i - 1][y];
        Cnt1[i][Bel[x]] += Cnt1[i - 1][Bel[x]];
        Cnt1[i][Bel[y]] += Cnt1[i - 1][Bel[y]];
    }
}

inline int Kth(int l , int r , int k) {
	if(Bel[l] == Bel[r]) {
		UpDateValue(Bel[l]);
		for(int i = l; i <= r; i++) {
			Query_Cnt2[i] = Num[i];
		}
		nth_element(Query_Cnt2 + l , Query_Cnt2 + l + k - 1 , Query_Cnt2 + r + 1); 
		int Ans = Query_Cnt2[k + l - 1];
		
		for(int i = l; i <= r; i++) {
			Query_Cnt2[i] = 0;
		}
		
		return Ans;
	}
	
	else {
		UpDateValue(Bel[l]);
		UpDateValue(Bel[r]);
		
		for(int i = l; i <= Right[Bel[l]]; i++) {
			Query_Cnt1[Bel[Num[i]]]++;
			Query_Cnt2[Num[i]]++;
		}
		
		for(int i = Left[Bel[r]]; i <= r; i++) {
			Query_Cnt1[Bel[Num[i]]]++;
			Query_Cnt2[Num[i]]++;
		}
		
		int Sum = 0;
        
        for(int i = 1; i <= (MAXN - 1) / BLOCK + 1; i++) {
        	if(Sum + Query_Cnt1[i] + Cnt1[Bel[r] - 1][i] - Cnt1[Bel[l]][i] >= k) {
        		for(int j = (i - 1) * BLOCK + 1; j <= i * BLOCK; j++) {
        			if(Sum + Query_Cnt2[j] + Cnt2[Bel[r] - 1][j] - Cnt2[Bel[l]][j] >= k) {
        				for(int i = l; i <= Right[Bel[l]]; i++) {
							Query_Cnt1[Bel[Num[i]]] = 0;
							Query_Cnt2[Num[i]] = 0;
						}
					
						for(int i = Left[Bel[r]]; i <= r; i++) {
							Query_Cnt1[Bel[Num[i]]] = 0;
							Query_Cnt2[Num[i]] = 0;
						}
        				return j;
					}
					else Sum += Query_Cnt2[j] + Cnt2[Bel[r] - 1][j] - Cnt2[Bel[l]][j];
				}
			}
			else Sum += Query_Cnt1[i] + Cnt1[Bel[r] - 1][i] - Cnt1[Bel[l]][i];
		}
	}
}

int main() {
	N = read();
	M = read();
	
	BLOCK = sqrt(N * 1.2);
	
	for(int i = 1; i <= N; i++) {
		Num[i] = read();
	}
	
	for(int i = 1; i <= MAXN; i++) {
		Bel[i] = (i - 1) / BLOCK + 1;
	}
	
	for(int i = 1; i <= Bel[N]; i++) {
		Left[i] = Right[i - 1] + 1;
		Right[i] = i * BLOCK;
	}
	
	Right[Bel[N]] = N;
	
	for(int i = 1; i <= Bel[N]; i++)
		Build(i); 
	
	for(int i = 1; i <= Bel[N]; i++) {
		for(int j = 1; j <= Bel[MAXN - 1 - 5]; j++) {
			Cnt1[i][j] = Cnt1[i - 1][j];
		}
		for(int j = 1; j <= MAXN - 5; j++) {
			Cnt2[i][j] = Cnt2[i - 1][j];
		}
		
		for(int j = Left[i]; j <= Right[i]; j++) {
			Cnt1[i][Bel[Num[j]]]++;
			Cnt2[i][Num[j]]++;
		}
	}
	
	while(M--) {
		op = read();
		l = read();
		r = read();
		if(op == 1) {
			x = read();
			y = read();
			Change(l , r , x , y);
		}
		else {
			k = read();
			write(Kth(l , r , k));
			putchar('\n');
		}
	}
    return 0;
}