首页 > 其他分享 >分块/莫队学习笔记（一）（2024.8.23）

分块/莫队学习笔记（一）（2024.8.23）

时间：2024-09-20 17:15:45浏览次数：8  
标签：ch 分块 2024.8 23 namespace long int using 莫队

分块

基本概念

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

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

LOJ小分块

#6277. 数列分块入门 1

基础分块题，将需要加的区间分成开头的零散块，中间几个整块，结尾的零散块，加的时候只用将两个零散块暴力增加，中间几个整块整体打上加标记，求点值只用求出它的暴力值加上它的块标记。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 9;
int a[N], v[N], b[N], n, k;
void add(int x, int y, int z){
	for(int i = x; i <= min(b[x] * k, y); i++)
		v[i] += z;//零散块暴力加
	if(b[x] != b[y])
		for(int i = (b[y] - 1) * k + 1; i <= y; i++)
			v[i] += z;//零散块暴力加
	for(int i = b[x] + 1; i <= b[y] - 1; i++)
		a[i] += z;//整块直接打标记
}
signed main(){
	scanf("%lld", &n);
	k = sqrt(n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &v[i]);
	for(int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	for(int i = 1; i <= n; i++){
		int opt, x, y, z;
		scanf("%lld%lld%lld%lld", &opt, &x, &y, &z);
		if(opt == 0)
			add(x, y, z);
		else
			printf("%lld\n", v[y] + a[b[y]]);//暴力值加标记值
	}
	return 0;
}

#6278. 数列分块入门 2

加法操作与第一题一样，考虑求小于给定值的数的个数，可以给每个块再维护一个已经排好序的数组，整块加法对于这个块排好序的数组没有影响，零散块加法直接在原序列上加，再将零散块所处的整块从新排序。查询时零散块暴力查找，整块二分查找。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 9;
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
int a[N], v[N], tmp[N], b[N], n, k;
inline void add(int x, int y, int z){
	for(register int i = x; i <= min(b[x] * k, y); i++)
		v[i] += z;
	for(register int i = (b[x] - 1) * k + 1; i <= min(n, b[x] * k); i++)
		tmp[i] = v[i];
	sort(tmp + (b[x] - 1) * k + 1, tmp + min(n, b[x] * k) + 1);//零散块所在整块排名会有变化，从新排序
	if(b[x] != b[y]){
		for(register int i = (b[y] - 1) * k + 1; i <= y; i++)
			v[i] += z;
		for(register int i = (b[y] - 1) * k + 1; i <= min(n, b[y] * k); i++)
			tmp[i] = v[i];
		sort(tmp + (b[y] - 1) * k + 1, tmp + min(n, b[y] * k) + 1);//零散块所在整块排名会有变化，从新排序
	}	
	for(register int i = b[x] + 1; i <= b[y] - 1; i++)
		a[i] += z;//整块都加一个数，排名不会有变化
}
signed main(){
	n = read();
	k = sqrt(n);
	for(register int i = 1; i <= n; i++){
		v[i] = read();
		tmp[i] = v[i];
	}
	for(register int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	for(register int i = b[1]; i <= b[n]; i++)
		sort(tmp + (i - 1) * k + 1, tmp + min(i * k, n) + 1);//一开始先将每个块排序
	int nn = n;
	while(nn--){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0)
			add(x, y, z);
		else {
			int ans = 0;
			for(register int i = x; i <= min(b[x] * k, y); i++)
				if(v[i] + a[b[i]] < z * z)
					ans++;
			if(b[x] != b[y])
				for(register int i = (b[y] - 1) * k + 1; i <= y; i++)
					if(v[i] + a[b[i]] < z * z)
						ans++;
			for(int register i = b[x] + 1; i <= b[y] - 1; i++){
				int l = (i - 1) * k + 1, r = i * k;
				while(l < r){//二分查找小于给定值的数的个数
					int mid = (l + r + 1) >> 1;
					if(tmp[mid] + a[i] < z * z)
						l = mid;
					else
						r = mid - 1;
				}
				if(tmp[l] + a[i] < z * z)
					ans += l - (i - 1) * k;
			}
			write(ans);
			putchar('\n');
		}
	}
	return 0;
}

#6279. 数列分块入门 3

与第二题一样，只是二分查找小于给定值的最大数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
int a[N], v[N], tmp[N], b[N], n, k;
inline void add(int x, int y, int z){
	for(register int i = x; i <= min(b[x] * k, y); i++)
		v[i] += z;
	for(register int i = (b[x] - 1) * k + 1; i <= min(n, b[x] * k); i++)
		tmp[i] = v[i];
	sort(tmp + (b[x] - 1) * k + 1, tmp + min(n, b[x] * k) + 1);
	if(b[x] != b[y]){
		for(register int i = (b[y] - 1) * k + 1; i <= y; i++)
			v[i] += z;
		for(register int i = (b[y] - 1) * k + 1; i <= min(n, b[y] * k); i++)
			tmp[i] = v[i];
		sort(tmp + (b[y] - 1) * k + 1, tmp + min(n, b[y] * k) + 1);	
	}	
	for(register int i = b[x] + 1; i <= b[y] - 1; i++)
		a[i] += z;
}
signed main(){
	n = read();
	k = sqrt(n);
	for(register int i = 1; i <= n; i++){
		v[i] = read();
		tmp[i] = v[i];
	}
	for(register int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	for(register int i = b[1]; i <= b[n]; i++)
		sort(tmp + (i - 1) * k + 1, tmp + min(i * k, n) + 1);
	int nn = n;
	while(nn--){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0)
			add(x, y, z);
		else {
			int ans = -1;
			for(register int i = x; i <= min(b[x] * k, y); i++)
				if(v[i] + a[b[i]] < z && ans < v[i] + a[b[i]])
					ans = v[i] + a[b[i]];
			if(b[x] != b[y])
				for(register int i = (b[y] - 1) * k + 1; i <= y; i++)
					if(v[i] + a[b[i]] < z && ans < v[i] + a[b[i]])
						ans = v[i] + a[b[i]];
			for(register int i = b[x] + 1; i <= b[y] - 1; i++){
				int l = (i - 1) * k + 1, r = i * k;
				while(l < r){
					int mid = (l + r + 1) >> 1;
					if(tmp[mid] + a[i] < z)
						l = mid;
					else
						r = mid - 1;
				}
				if(tmp[l] + a[i] < z)
					ans = max(tmp[l] + a[i], ans);
			}
			write(ans);
			putchar('\n');
		}
	}
	return 0;
}

#6280. 数列分块入门 4

加法操作与第一题一样，对每个块在维护一下块内暴力和，询问时零散块暴力加，整块则加上这块的暴力和以及加标记乘上区间长度。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
int a[N], v[N], sum[N], b[N], n, k;
inline void add(int x, int y, int z){
	for(register int i = x; i <= min(b[x] * k, y); i++){//暴力值统计在sum中
		v[i] += z;
		sum[b[x]] += z;
	}	
	if(b[x] != b[y])
		for(register int i = (b[y] - 1) * k + 1; i <= y; i++){//暴力值统计在sum中
			v[i] += z;
			sum[b[y]] += z;
		}		
	for(register int i = b[x] + 1; i <= b[y] - 1; i++)
		a[i] += z;
}
signed main(){
	n = read();
	k = sqrt(n);
	for(register int i = 1; i <= n; i++)
		v[i] = read();
	for(register int i = 1; i <= n; i++){
		b[i] = (i - 1) / k + 1;
		sum[b[i]] += v[i];//初始化sum
	}
	int nn = n;
	while(nn--){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0)
			add(x, y, z);
		else {
			int ans = 0;
			for(register int i = x; i <= min(b[x] * k, y); i++)
				ans += v[i] + a[b[i]];
			if(b[x] != b[y])
				for(register int i = (b[y] - 1) * k + 1; i <= y; i++)
					ans += v[i] + a[b[i]];	
			for(register int i = b[x] + 1; i <= b[y] - 1; i++)
				ans += sum[i] + a[i] * (min(i * k, n) - (i - 1) * k);//暴力值+块长*标记值 
			write(ans % (z + 1));
			putchar('\n');
		}
	}
	return 0;
}

#6281. 数列分块入门 5

考虑到一个数最多进行 \(\log(n)\) 次就会变成 \(1\)，这时就不需要管这个数了，因此暴力就可以通过这道题。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 9;
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
int v[N], n;
signed main(){
	n = read();
	for(register int i = 1; i <= n; i++)
		v[i] = read();
	int nn = n;
	while(nn--){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0)
			for(int i = x; i <= y; i++)
				if(v[i] == 1 || v[i] == 0)
					continue;
				else
					v[i] = floor(sqrt(v[i] * 1.0));
		else {
			int ans = 0;
			for(int i = x; i <= y; i++)
				ans += v[i];
			write(ans);
			putchar('\n');
		}
	}
	return 0;
}

#6282. 数列分块入门 6

考虑使用块状链表，每个链表维护一个长为 \(\sqrt{n}\) 的块，插入时如果该块长度不足 \(\sqrt{n}\)，直接插入，否则将该块最后一个元素弹出，插入下一个块，重复此过程，就可以完成插入操作。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
vector <int> vec[N];
int v[N], b[N], n, k;
signed main(){
	n = read();
    k = sqrt(n);
    for(int i = 1; i <= n; i++)
        v[i] = read();
    for(int i = 1; i <= n; i++){
    	b[i] = (i - 1) / k + 1;
    	vec[b[i]].push_back(v[i]);
	}
	for(int i = 1; i <= n; i++){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0){
			int bl = (x - 1) / k + 1;
			x = (x - 1) % k;
			vec[bl].insert(vec[bl].begin() + x, y);
			while(vec[bl].size() > k){//该块长度超了 
				int u = vec[bl].back(); 
				vec[bl].pop_back();//弹出最后一个元素
				++bl;
				vec[bl].insert(vec[bl].begin(), u);//插入下一个块 
			}
		} else {
			int bl = (y - 1) / k + 1;
			y = (y - 1) % k;
			write(vec[bl].at(y));
			putchar('\n');
		}
	}
	return 0;
}

#6283. 数列分块入门 7

对一个整块维护一个加标记，一个乘标记。做加法时，如果有乘标记，不用管它，直接增加加标记；做乘法时如果有加标记，那么根据乘法分配律，加标记和乘标记都得乘上这个数。

考虑零散块的暴力计算，如果直接加或乘，那么会违反乘法分配律；如果先用区间标记更新这几个数，那么这个区间标记之后就无法适用于整个块。于是只能每次计算零散块时更新整个零散块所在整块。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		long long x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
const int N = 1e5 + 9, MOD = 10007;
int a[N], f[N], v[N], b[N], n, k;
inline void reset(int x){//重新计算零散块所在整块每个数的值
	for(int i = (b[x] - 1) * k + 1; i <= min(b[x] * k, n); i++){
		v[i] = v[i] * f[b[x]] + a[b[x]];
		v[i] %= MOD;
	}
	f[b[x]] = 1;
	a[b[x]] = 0;
}
inline void add(int x, int y, int z){
	reset(x);
	for(int i = x; i <= min(b[x] * k, y); i++){
		v[i] += z;
		v[i] %= MOD;
	}
	if(b[x] != b[y]){
		reset(y);
		for(int i = (b[y] - 1) * k + 1; i <= y; i++){
			v[i] += z;
			v[i] %= MOD;
		}
	}	
	for(int i = b[x] + 1; i <= b[y] - 1; i++){
		a[i] += z;//加法直接在加标记上增加
		a[i] %= MOD;
	}
}
inline void mult(int x, int y, int z){
	reset(x);
	for(int i = x; i <= min(b[x] * k, y); i++){
		v[i] *= z;
		v[i] %= MOD;
	}
	if(b[x] != b[y]){
		reset(y);
		for(int i = (b[y] - 1) * k + 1; i <= y; i++){
			v[i] *= z;
			v[i] %= MOD;
		}
	}	
	for(int i = b[x] + 1; i <= b[y] - 1; i++){
		f[i] *= z;//乘法要在加标记和乘标记上都乘
		f[i] %= MOD;
		a[i] *= z;
		a[i] %= MOD;
	}	
}
signed main(){
	n = read();
	k = sqrt(n);
	for(register int i = 1; i <= n; i++){
		v[i] = read();
		f[i] = 1;
	}	
	for(register int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	for(register int i = 1; i <= n; i++){
		int opt, x, y, z;
		opt = read();
		x = read();
		y = read();
		z = read();
		if(opt == 0)
			add(x, y, z);
		else if(opt == 1)
			mult(x, y, z);
		else {
			write((v[y] * f[b[y]] + a[b[y]]) % MOD);
			putchar('\n');
		}
	}
	return 0;
}

#6284. 数列分块入门 8

我们称一个颜色相同的块叫纯块，颜色不同的叫杂块，零散块直接暴力查找、暴力修改；一个整块如果是杂块，那么也暴力查找、暴力修改；一个整块如果是纯块，那么直接修改它的标记值即可。

考虑零散块的暴力操作，这个零散块所在整块可能已经被修改过了，于是我们先用标记值更新这个块的值，再暴力操作。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		int x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
const int N = 1e5 + 9, INF = 1e18;
int a[N], v[N], b[N], n, k, ans;
inline void change(int x, int y, int z){
	ans = 0;
	if(a[b[x]] != INF)
		for(int i = (b[x] - 1) * k + 1; i <= min(b[x] * k, n); i++)
			v[i] = a[b[x]];
	a[b[x]] = INF;
	for(int i = x; i <= min(b[x] * k, y); i++){
		if(v[i] == z)
			ans++;
		v[i] = z;
	}
	if(b[x] != b[y]){
		if(a[b[y]] != INF)
			for(int i = (b[y] - 1) * k + 1; i <= min(b[y] * k, n); i++)
				v[i] = a[b[y]];
		a[b[y]] = INF;
		for(int i = (b[y] - 1) * k + 1; i <= y; i++){
			if(v[i] == z)
				ans++;
			v[i] = z;
		}
	}	
	for(int i = b[x] + 1; i <= b[y] - 1; i++)
		if(a[i] != INF){
			if(a[i] == z)
				ans += k;
			a[i] = z;
		} else {
			for(int j = (i - 1) * k + 1; j <= i * k; j++)
				if(v[j] == z)
					ans++;
			a[i] = z;
		}
}
signed main(){
	for(int i = 1; i <= N; i++)
		a[i] = INF;
	n = read();
	k = sqrt(n);
	for(register int i = 1; i <= n; i++)
		v[i] = read();
	for(register int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	for(register int i = 1; i <= n; i++){
		int x, y, z;
		x = read();
		y = read();
		z = read();
		change(x, y, z);
		write(ans);
		putchar('\n');
	}
	return 0;
}

#6285. 数列分块入门 9

考虑一段区间的众数只可能是两头零散块中的数或中间这些整块的众数。

  • 处理几个整块的众数可以开个桶记录 \(1\) 到 \(n\) 块中每个数出现次数，当我们要从 \(i\) 到 \(j\) 块的众数扩展到 \(i\) 到 \(j + 1\) 块的众数时，只用考虑第 \(j + 1\) 块中的数是否会成为众数，这样外层枚举 \(i\) 的时间复杂度是 \(O(\sqrt{n})\)，内层枚举 \(j\) 的时间复杂度是 \(O(\sqrt{n})\)，转移的时间复杂度是 \(O(\sqrt{n})\)，一共 的时间复杂度 \(O(n \sqrt{n})\)，可以接受。

  • 考虑两头零散块中的数是否会成为众数，可以对每个值 \(a_i\) 开一个 vector，将 \(a_i\) 出现的位置记录下来，计算 \(a_i\) 在 \(l\) 到 \(r\) 中的出现次数时只用二分查找大于 \(l\) 的最小值，小于 \(r\) 的最大值，将两个值在 vector 中的下标相减再加 \(1\)，就可以知道 \(a_i\) 在 \(l\) 到 \(r\) 中的出现次数。

几种情况按题目要求取舍即可。

注意：

  • 先将 \(a\) 数组离散化，否则 vector 开不下

  • 我的代码在块长在 \(100\) 到 \(200\) 之间时跑得最快，具体代码具体分析。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace IO{
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1<<20) + 1, stdin), (iS == iT ? EOF: *iS++) : *iS++)
 	#else
	#define gh() getchar()
	#endif
	inline int read(){
		char ch = gh();
		int x = 0;
		bool t = 0;
		while(ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while(ch >= '0' && ch <= '9')
			x = x * 10 + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void write(int x){
	    if(x < 0){
	    	putchar('-');
			x = -x;
		}	
	    if(x < 10)
			putchar(x + '0');
	    else {
	    	write(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline char getc(){
		char ch = gh();
		while(ch < 'a' || ch > 'z')
			ch = gh();
		return ch;
	}
}
using namespace IO;
const int N = 1e5 + 9, M = 609;
int a[N], tmp[N], b[N], bas[N], s[M][N], p[M][M], n, k;
vector <int> v[N];
inline void prework(){
	for(register int i = 1; i <= n; i++)
		for(register int j = b[i]; j <= b[n]; j++)
			s[j][a[i]]++;//统计1到j块中a[i]的出现次数
	for(register int i = 1; i <= b[n]; i++){
		memset(bas, 0, sizeof(bas));
		for(register int j = i; j <= b[n]; j++){
			p[i][j] = p[i][j - 1];//初值为上一个枚举到的区间的众数
			for(register int l = (j - 1) * k + 1; l <= min(j * k, n); l++){//考虑新加进来的块中是否有数会成为众数
				bas[a[l]]++;
				if((bas[a[l]] > bas[p[i][j]]) || (bas[a[l]] == bas[p[i][j]] && a[l] < p[i][j]))
					p[i][j] = a[l];
			}
		}
	}
}
inline int ask(int x, int y){
	int ans = 1e18, id = 0;
	//处理零散块
	for(register int i = x; i <= min(b[x] * k, y); i++){
		int L = 0, R = v[a[i]].size() - 1;//求大于x的最小值
		while(L < R){
			int mid = (L + R) >> 1;
			if(v[a[i]].at(mid) < x)
				L = mid + 1;
			else
				R = mid;
		}
		int l = L;
		L = 0, R = v[a[i]].size() - 1;//求小于y的最大值
		while(L < R){
			int mid = (L + R + 1) >> 1;
			if(v[a[i]].at(mid) <= y)
				L = mid;
			else
				R = mid - 1;
		}
		int r = L;
		if(r - l + 1 > id || (r - l + 1 == id && a[i] < ans)){//是否可以更新
			ans = a[i];
			id = r - l + 1;
		}
	}
	if(b[x] != b[y]){//同理
		for(register int i = (b[y] - 1) * k + 1; i <= y; i++){
			int L = 0, R = v[a[i]].size() - 1;
			while(L < R){
				int mid = (L + R) >> 1;
				if(v[a[i]].at(mid) < x)
					L = mid + 1;
				else
					R = mid;
			}
			int l = L;
			L = 0, R = v[a[i]].size() - 1;
			while(L < R){
				int mid = (L + R + 1) >> 1;
				if(v[a[i]].at(mid) <= y)
					L = mid;
				else
					R = mid - 1;
			}
			int r = L;
			if(r - l + 1 > id || (r - l + 1 == id && a[i] < ans)){
				ans = a[i];
				id = r - l + 1;
			}
		}
	}
	//处理几个整块
	int now = s[b[y] - 1][p[b[x] + 1][b[y] - 1]] - s[b[x]][p[b[x] + 1][b[y] - 1]];
	if(now > id || (now == id && p[b[x] + 1][b[y] - 1] < ans))
		ans = p[b[x] + 1][b[y] - 1];
	return ans;
}
signed main(){
	n = read();
    for(register int i = 1; i <= n; i++){
        a[i] = read();
        tmp[i] = a[i];
    }
    //离散化
    sort(tmp + 1, tmp + n + 1);
    int sum = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    for(register int i = 1; i <= n; i++)
    	a[i] = lower_bound(tmp + 1, tmp + sum + 1, a[i]) - tmp;
    for(register int i = 1; i <= n; i++)
    	v[a[i]].push_back(i);
    //分块
	k = 200;
	for(register int i = 1; i <= n; i++)
		b[i] = (i - 1) / k + 1;
	prework();
	for(register int i = 1; i <= n; i++){
		int x, y;
		x = read();
		y = read();
		write(tmp[ask(x, y)]);
		putchar('\n');
	}
	return 0;
}

Ynoi小分块

雾满拦江第三分块

P5065 [Ynoi2014] 不归之人与望眼欲穿的人们

曲折探索第五分块

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

暗香浮动第八分块

P5073 [Ynoi2015] 世上最幸福的女孩

无人问津第九分块

P5313 [Ynoi2011] WBLT

路暗迷人十二分块

P4693 [Ynoi2016] 炸脖龙 II

Ynoi大分块

望月悲叹最初分块

P4119 [Ynoi2018] 未来日记

突刺贯穿第二分块

P4117 [Ynoi2018] 五彩斑斓的世界

拭尽破净第四分块

P5397 [Ynoi2018] 天降之物

深潜循藏第六分块

P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

寻寻觅觅第七分块

P5399 [Ynoi2018] 駄作

光芒照耀第十分块

P6578 [Ynoi2019] 魔法少女网站

沉滞留驻十一分块

P6580 [Ynoi2019] 美好的每一天~ 不连续的存在

迷途忘返十三分块

P6579 [Ynoi2019] Happy Sugar Life

点缀光辉十四分块

P5398 [Ynoi2018] GOSICK

莫队

标签：ch,分块,2024.8,23,namespace,long,int,using,莫队
From： https://www.cnblogs.com/JPGOJCZX/p/18422877

相关文章

  • 2024.8.31校测
    T1题目描述今天的酒席有\(n\)个人，他们要同时举杯，成对碰杯。碰杯的时候，不能有人不参与碰杯，也不希望有手臂交叉这种别扭的情况出现。如下图，左图的情况是好的，右图的情况是不希望出现的。每个人都有一个喜爱的酒种类，每个人想要与和自己喝一样酒的人碰杯，请你设计一个方法，在保证每......
  • 图论进阶学习笔记（三）（2024.8.12）
    二分图定义如果你能把一个图划分成两个集合，集合内部的点没有边相连接，那么这个图就是一个二分图，如图就是一个二分图：交错路：从一个没有被匹配的点出发，依次走非匹配边，匹配边，非匹配边……最后到达另外一部点当中某个没有被匹配的点的路径。增广路：从一个没有被匹配的点出发，依次走......
  • 图论进阶学习笔记（二）（2024.8.1）
    图的连通性强连通分量割点缩点例题一边双连通分量点双连通分量2-SAT例题二例题三欧拉回路例题四......
  • 多项式学习笔记（二）（2024.7.23）
    牛顿迭代快速多项式计算加法\(H(x)=F(x)+G(x)\)，求\(H(x)\)解：都已经\(O(n)\)了，还怎么优化！！！乘法\(H(x)\equivF(x)G(x)(\text{mod}x^n)\)，求\(H(x)\)解：参考多项式学习笔记（一）（2024.7.6）完整代码：P3803【模板】多项式乘法（FFT）#include<bits/stdc++.h>usingnamespacestd......
  • GEE教程：1950-2023年ECMWF数据中积雪的长时序统计分析
    目录简介数据函数millis()Arguments:Returns: Long代码结果简介1950-2023年ECMWF数据中积雪的长时序统计分析数据ECMWF/ERA5_LAND/DAILY_AGGR是由欧洲中期天气预报中心（ECMWF）提供的数据集。它是一个格网数据集，包含从ERA5-Land再分析数据集中得出的陆地区域每日聚......
  • 线段树进阶应用学习笔记（一）（2024.7.19）（2024.8.22）
    线段树优化建图算法流程复杂度分析例题一#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=5e5,M=5e6+9;structEdge{ intv,w,nex;}e[M];inthead[M],ecnt;voidAddEdge(intu,intv,intw){ e[++ecnt]=Edge{v,w,hea......
  • COSC2391 Further Programming
    COSC2391 FurtherProgramming/COSC1295AdvancedProgrammingAssignment2- Semester 2 20241.IntroductionThisassignmentisdesignedto:•   Evaluateyourabilitytodevelop GUI applications usingJavaFX.•   Evaluateyourskillsin stori......
  • D23 kubernetes 工作负载资源对象-DaemonSet{简介}
    1、DaemonSet简介DaemonSet资源用于在集群中的每个节点上运行一个pod副本，具有以下特点-在每个节点上运行一个pod-当向集群中加入一个新节点或者从集群中移除一个节点时，DaemonSet会自动在新节点上启动一个pod或在移除的节点上删除pod-可以使用节点选择器或亲和性来定义pod......
  • 10月23日，2024 OceanBase 年度发布会在北京等您
    海量数据管理，源于一笔笔记录， 不止于记录， 不仅要保障每一笔记录，更要实现每一份数据的价值。OceanBase正通过一体化架构和一体化引擎，不断创新实现 一体化的TP、AP和多模融合的多工作负载， 从线下到云端，全面加速基于跨分布式数据的创新。2024年10月23日，OceanBase将在北......
  • springboot社区医院管理信息系统-计算机毕业设计源码23303
    摘 要本文旨在探讨基于SpringBoot框架的社区医院管理信息系统的设计与实现。随着信息技术的快速发展，医院管理信息化已成为提升医疗服务水平、优化医疗资源配置的重要手段。社区医院作为基层医疗服务的重要组成部分，其信息化建设的推进对于提高基层医疗服务质量和效率具有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99