LuoguP4119 最初分块 题解

题目大意:

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

1.把区间[l,r]内所有x变成y

2.查询区间[l,r]内k小值

即:区间所有x变y,区间第k小.

对于区间第k小问题,我们进行权值分块,记b[i][j]为前i个位置块内,权值在第j权值块以下的数字个数,cnt[i][j]表示前i个块内数字x的出现次数.

查询时,先把散块信息处理出来.此时我们可以O(1)得到询问区间内权值在第j权值块以下的数字个数以及询问区间内每个数的出现个数.查询时暴力遍历每个权值块,找到第一个数字个数>k的权值块,则第k大必定在此块内.在块内暴力查找第k小,查询复杂度为O(msqrt(n)).

对于修改操作.考虑将整块中的x全部变成y时,则块内数字种类数要么不变要么-1.当块内不存在y时,直接随意搞一个映射将块内的x映射成y并且更新信息.当块内x与y都存在时直接重构整个块.重构复杂度O(sqrt(n)),最多有n+m种权值,因此修改复杂度为O((n+m)sqrt(n)).

注意特判x=y时不进行修改,不然可能爆复杂度.

代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100, MAXB = 320, M = 100050;
void read(int &x) {char ch;while(ch=getchar(),ch<'!');x=ch-48;while(ch=getchar(),ch>'!')x=(x<<3)+(x<<1)+ch-48;}
int n, m, L[MAXN], R[MAXN], Psiz, b[MAXB][1050], fh[MAXB][1050], h[MAXB][MAXN], ls[MAXN], ls2[2050], c[MAXN], a[MAXN], Vsiz, cnt[MAXB][MAXN], Q, _m;
void rep(int p) {for(int i = L[p]; i < R[p]; ++i) a[i] = fh[p][c[i]];}
void change(int B, int x, int y) {int id = h[B][x]; h[B][y] = id; fh[B][id] = y; h[B][x] = 0;}
inline int Vbl(int x) {return x/Vsiz;} inline int Pbl(int x) {return x/Psiz;}
void Rebuild(int p, int op = 1) {
	if(op) for(int i = 1; i <= Psiz; ++i) h[p][fh[p][i]] = 0;
	for(int top = 0, i = L[p]; i < R[p]; ++i) if(!h[p][a[i]]) h[p][a[i]] = ++top, fh[p][top] = a[i];
	for(int i = L[p]; i < R[p]; ++i) c[i] = h[p][a[i]];
}
int main() {
	read(n); read(Q); Psiz = Vsiz = 600; m = n/Psiz+1; _m = M/Vsiz+1;
	for(int i = 0; i < n; ++i) read(a[i]);
	for(int i = 0; i < m+10; ++i) L[i] = i*Psiz, R[i] = min((i+1)*Psiz, n);
	for(int i = 0; i < m; ++i) Rebuild(i, 0);
	for(int i = 0; i < m; ++i) {
		if(i) {
			for(int j = 0; j < M; ++j) cnt[i][j] = cnt[i-1][j];
			for(int j = 0; j < _m; ++j) b[i][j] = b[i-1][j];
		}
		for(int j = L[i]; j < R[i]; ++j) ++cnt[i][a[j]], ++b[i][Vbl(a[j])];
	}
	for(int op, l, r, x, y; Q--; ) {
		read(op); read(l); read(r); --l; --r;
		if(op == 1) {
			read(x); read(y); if(x == y) continue;
			int bl = Pbl(l), br = Pbl(r), bx = Vbl(x), by = Vbl(y);
			if(cnt[br][x] - (bl?cnt[bl-1][x]:0) == 0) continue;
			for(int i = m-1; i >= 1 && i >= bl; --i) {
				cnt[i][x] -= cnt[i-1][x]; cnt[i][y] -= cnt[i-1][y];
				b[i][bx] -= b[i-1][bx]; b[i][by] -= b[i-1][by];
			}
			if(bl == br) {
				rep(bl);
				for(int i = l; i <= r; ++i) 
					if(a[i] == x) {
						a[i] = y;
						--cnt[bl][x]; ++cnt[bl][y];
						--b[bl][bx]; ++b[bl][by];
					}
				Rebuild(bl);
			} else {
				rep(bl); rep(br);
				for(int i = l; i < R[bl]; ++i)
					if(a[i] == x) {
						a[i] = y;
						--cnt[bl][x]; ++cnt[bl][y];
						--b[bl][bx]; ++b[bl][by];
					}
				for(int i = L[br]; i <= r; ++i)
					if(a[i] == x) {
						a[i] = y;
						--cnt[br][x]; ++cnt[br][y];
						--b[br][bx]; ++b[br][by];
					}
				Rebuild(bl); Rebuild(br);
				for(int i = bl+1; i < br; ++i)
					if(cnt[i][x]) {
						if(cnt[i][y]) {
							rep(i);
							for(int j = L[i]; j < R[i]; ++j)
								if(a[j] == x) {
									a[j] = y;
									--cnt[i][x]; ++cnt[i][y];
									--b[i][bx]; ++b[i][by];
								}
							Rebuild(i);
						} else {
							b[i][by] += cnt[i][x]; b[i][bx] -= cnt[i][x];
							cnt[i][y] += cnt[i][x]; cnt[i][x] = 0;
							change(i, x, y);
						}
					}
			}
			for(int i = max(1, bl); i < m; ++i) {
				cnt[i][x] += cnt[i-1][x]; cnt[i][y] += cnt[i-1][y];
				b[i][bx] += b[i-1][bx]; b[i][by] += b[i-1][by];
			}
		}
		else {
			read(x); int bl = Pbl(l), br = Pbl(r);
			if(bl == br) {
				rep(bl);
				for(int i = l; i <= r; ++i) ls[i] = a[i];
				nth_element(ls+l, ls+l+x-1, ls+r+1);
				printf("%d\n", ls[l+x-1]);
				for(int i = l; i <= r; ++i) ls[i] = 0;
			} else {
				rep(bl); rep(br);
				for(int i = l; i < R[bl]; ++i) ++ls[a[i]], ++ls2[Vbl(a[i])];
				for(int i = L[br]; i <= r; ++i) ++ls[a[i]], ++ls2[Vbl(a[i])];
				for(int i = 0, sum = 0; i < _m; ++i) {
					if(ls2[i] + b[br-1][i] - b[bl][i] + sum >= x) {
						int flag = 0;
						for(int j = i*Vsiz; j < (i+1)*Vsiz; ++j) {
							if(ls[j] + cnt[br-1][j] - cnt[bl][j] + sum >= x) {
								printf("%d\n", j); flag = 1; break;
							} else sum += ls[j] + cnt[br-1][j] - cnt[bl][j];
						}
						if(flag) break;
					} else sum += ls2[i] + b[br-1][i] - b[bl][i];
				}
				for(int i = l; i < R[bl]; ++i) --ls[a[i]], --ls2[Vbl(a[i])];
				for(int i = L[br]; i <= r; ++i) --ls[a[i]], --ls2[Vbl(a[i])];
			}
		}
	}
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00