题解 [email protected]洛谷 【[Ynoi2017]由乃打扑克】

区间加区间第 kk 小问题。

碰到 Ynoi 题,先考虑分块。 ←暴论,但这题就是分块。


由于要求第 kk 小,我们将原数列分成若干块(这里我们块长为 400400),每块内先进行排序。

下面分别考虑两个操作:

  • 操作一:查询区间第 kk 小。

我们取两端点为区间内最大、最小值,进行二分。对于 midmid,我们求出区间内有多少个小于等于 midmid 的数。具体做法就是,对于零散块暴力统计,对于整块进行块内二分。对于每次二分,如果这个个数大于等于 kk,我们就可以更新答案,最后输出即可。

求出最大、最小值后,我们可以进行一点优化:

  1. 对于 k=1k=1,直接输出最小值,不用二分。
  2. 对于 k=rl+1k=r-l+1,直接输出最大值,不用二分。
  3. 特判 k<1k\lt 1k>rl+1k\gt r-l+1,输出 1-1
  • 操作二:区间加 kk

对于左侧零散块,我们暴力更新原数组和排序后的数组,由于后者有更新,因此将其按照是否在更改区间内分类,分别压入两个数组,然后对这两个数组进行归并。右侧零散块同理。

对于整块,暴力更新太费时,想到线段树的懒标记,我们这里也给每个块搞一个统计整块修改的 tag,直接更新它即可。注意查询时也要加上这个值,我因为有一处忘加这个 tag,调了几个小时,也可能是我太菜了吧。

调试过程中一次对拍的结果\small\color{gray}\text{调试过程中一次对拍的结果}

最终我们就得到了正解。


总结一下:我们通过分块,统计懒标记,对块内归并来维护块内有序性,然后根据分块进行统计答案即可。


主要代码:

struct Node {
	int val, pos;
	Node() {}
	Node(int a, int b) : val(a), pos(b) {}
	~Node() {}
	bool operator < (const Node &a) const {return val < a.val;}
}cp[N], mer1[SIZE], mer2[SIZE];
int L[K], R[K], tag[K];

void init() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) {
		scanf("%d", &a[i]);
		cp[i] = Node(a[i], i);
	}
}
#define whichBlock(x) (\
    (x - 1) / SIZE + 1\
)
void initBlock() {
	tot = whichBlock(n);
	for(int i=1;i<=tot;i++) {
		L[i] = R[i-1] + 1;
		R[i] = SIZE * i;
		sort(cp+L[i], cp+R[i]+1);
	}
	R[tot] = n;
}
void getBorder(int l, int r, int &_l, int &_r) {
	int bL = whichBlock(l), bR = whichBlock(r);
	if(bL == bR) {
		for(int i=l;i<=r;i++) {
			_l = min(_l, a[i]+tag[bL]);
			_r = max(_r, a[i]+tag[bL]);
		}
	}
	else {
		for(int i=l;i<=R[bL];i++) {
			_l = min(_l, a[i]+tag[bL]);
			_r = max(_r, a[i]+tag[bL]);
		}
		for(int i=L[bR];i<=r;i++) {
			_l = min(_l, a[i]+tag[bR]);
			_r = max(_r, a[i]+tag[bR]);
		}
		for(int i=bL+1;i<bR;i++) {
			_l = min(_l, cp[L[i]].val+tag[i]);
			_r = max(_r, cp[R[i]].val+tag[i]);
		}
	}
}
int getNumbersLeqK(int l, int r, int k) {
	int res = 0;
	int bL = whichBlock(l), bR = whichBlock(r);
	if(bL == bR) for(int i=l;i<=r;i++) res += (a[i] + tag[bL] <= k);
	else {
		for(int i=l;i<=R[bL];i++) res += (a[i] + tag[bL] <= k);
		for(int i=L[bR];i<=r;i++) res += (a[i] + tag[bR] <= k);
		for(int i=bL+1;i<bR;i++) {
			int mi = L[i], ma = R[i];
			if(cp[mi].val + tag[i] > k) continue;
			if(cp[ma].val + tag[i] <= k) {
				res += ma - mi + 1;
				continue;
			}
			while(mi < ma) {
				int mid = ((mi + ma) >> 1) + 1;
				if(cp[mid].val + tag[i] <= k) mi = mid;
				else ma = mid - 1;
			}
			if(cp[mi].val + tag[i] <= k) res += mi - L[i] + 1;
		}
	}
	return res;
}
int query(int l, int r, int k) {
	int mi = inf, ma = -inf;
	getBorder(l, r, mi, ma);
	if(k == 1) return mi;
	if(k == r - l + 1) return ma;
	if(k < 1 || k > r - l + 1) return -1;
	int res = -1;
	while(mi <= ma) {
		int mid = (mi + ma) >> 1;
		if(getNumbersLeqK(l, r, mid) < k) mi = mid + 1;
		else ma = (res=mid) - 1;
	}
	return res;
}
void modify(int l, int r, int k) {
	int bL = whichBlock(l), bR = whichBlock(r);
	int tp1, tp2;
	tp1 = tp2 = 0;
	for(int i=L[bL];i<=R[bL];i++) {
		if(i >= l && i <= r) a[i] += k;
		if(cp[i].pos >= l && cp[i].pos <= r) mer1[++tp1] = Node(cp[i].val+k, cp[i].pos);
		else mer2[++tp2] = cp[i];
	}
	int u1, u2;
	u1 = u2 = 1;
	int u = L[bL];
	while(u <= R[bL]) { // mergesort
		if(u1 <= tp1 && (u2 > tp2 || mer1[u1].val < mer2[u2].val)) cp[u++] = mer1[u1++];
		else cp[u++] = mer2[u2++];
	}
	if(bL != bR) {
		int tp1, tp2;
		tp1 = tp2 = 0;
		for(int i=L[bR];i<=R[bR];i++) {
			if(i >= l && i <= r) a[i] += k;
			if(cp[i].pos >= l && cp[i].pos <= r)mer1[++tp1] = Node(cp[i].val+k, cp[i].pos);
			else mer2[++tp2] = cp[i];
		}
		int u1, u2;
		u1 = u2 = 1;
		int u = L[bR];
		while(u <= R[bR]) { // mergesort
			if(u1 <= tp1 && (u2 > tp2 || mer1[u1].val < mer2[u2].val))cp[u++] = mer1[u1++];
			else cp[u++] = mer2[u2++];
		}
		for(int i=bL+1;i<bR;i++) tag[i] += k;
	}
}