题解 P5356 【[Ynoi2017]由乃打扑克】
rui_er
2020-09-18 21:19:37
区间加区间第 $k$ 小问题。
~~碰到 Ynoi 题，先考虑分块。~~ ←暴论，但这题就是分块。
---
由于要求第 $k$ 小，我们将原数列分成若干块（这里我们块长为 $400$），每块内先进行排序。
下面分别考虑两个操作：
- 操作一：查询区间第 $k$ 小。
我们取两端点为区间内最大、最小值，进行二分。对于 $mid$，我们求出区间内有多少个**小于等于** $mid$ 的数。具体做法就是，对于零散块暴力统计，对于整块进行块内二分。对于每次二分，如果这个个数**大于等于** $k$，我们就可以更新答案，最后输出即可。
求出最大、最小值后，我们可以进行一点优化：
1. 对于 $k=1$，直接输出最小值，不用二分。
1. 对于 $k=r-l+1$，直接输出最大值，不用二分。
1. 特判 $k\lt 1$ 和 $k\gt r-l+1$，输出 $-1$。
- 操作二：区间加 $k$。
对于左侧零散块，我们暴力更新原数组和排序后的数组，由于后者有更新，因此将其按照是否在更改区间内分类，分别压入两个数组，然后对这两个数组进行归并。右侧零散块同理。
对于整块，暴力更新太费时，想到线段树的懒标记，我们这里也给每个块搞一个统计整块修改的 tag，直接更新它即可。注意查询时也要加上这个值，我因为有一处忘加这个 tag，调了几个小时，也可能是我太菜了吧。
$$\small\color{gray}\text{调试过程中一次对拍的结果}$$
最终我们就得到了正解。
---
总结一下：我们通过分块，统计懒标记，对块内归并来维护块内有序性，然后根据分块进行统计答案即可。
---
主要代码：
```cpp
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;
}
}
```