题解 P5356 【[Ynoi2017]由乃打扑克】

rui_er · 2020-09-18 21:19:37 · 题解

区间加区间第 k 小问题。

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

由于要求第 k 小，我们将原数列分成若干块（这里我们块长为 400），每块内先进行排序。

下面分别考虑两个操作：

操作一：查询区间第 k 小。

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

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

对于 k=1，直接输出最小值，不用二分。
对于 k=r-l+1，直接输出最大值，不用二分。
特判 k\lt 1 和 k\gt r-l+1，输出 -1。

操作二：区间加 k。

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

对于整块，暴力更新太费时，想到线段树的懒标记，我们这里也给每个块搞一个统计整块修改的 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;
    }
}