题解：P9061 [Ynoi2002] Optimal Ordered Problem Solver

Nazq · 2025-01-10 22:07:24 · 题解

考虑修改矩形的并，是左下角的梯形，被推的点都在轮廓线上。

维护轮廓线，每次查询轮廓线上对应区间，以及没有被推的 x_i\le X, y_i\le Y 的点。

加时间维，三位偏序。

考虑容斥。

对于询问 (X, Y)，把平面分为 4 块，左下角的 = 全部的 - ( 上面的 + 右面的 - 右上角的 ) + 左下角轮廓线上的。 也等于左面的 + 下面的 + 右上角的 - 全部的 + 左下角轮廓线上的。

无论如何我们都要询问一个二维偏序，我们通过容斥转化，使得不查询修改这部分的点，来降维。

这题除了有精妙的容斥，还有复杂的实现。

标记每个点第一次被哪个修改推

Sol 1

考虑按时间顺序修改。维护横坐标为 [1, X] 的非轮廓线上的点的纵坐标最小值。每次取出最小的点 (x_i,y_i)，因为这样取出的 y_i 是单调的，所以直到取到 y_i\gt Y 就停止。

用线段树维护纵坐标最小值，在每个横坐标挂一个链表维护相同横坐标的点的最小纵坐标（在链表上，纵坐标也是单调的），每次取最小值，就把对应横坐标的指针往后移到链表下一个。

Sol 2

相对好实现的一种。

反过来考虑每个点被谁第一次推，是右上角的第一个。

可以二维偏序做。

修改与询问

如果用平衡树，就不用说了。

还可以用线段树。

如这篇所说，对于轮廓线上点，按最后一次被推的方向分为横线和竖线，用 2 棵线段树分别维护横线和竖线。

对于修改，暴力枚举被包含的横线竖线，在所在线段树修改，最终合并成一段横线或竖线。时间复杂度是均摊 O(n\log{n})。

每次查询用 2 棵线段树对应区间和相加。 快速找区间可以在 set 上维护维护每个横线竖线，在上面二分。

关于贡献

如果查询区间在轮廓线左下方，则 ans_i = 0。否则用上述求答案。

是否被轮廓线包含，画图可知等价于横坐标在 [X+1, n]（这里不能是 [X, n]，读者不妨自己找 hack）是否存在纵坐标大于 Y 的轮廓线。

关于排序

可以挂在每个横坐标挂链表，然后统计。

代码参考 EuphoricStar。~其实就是照抄的。~

#include <cstdio>
#include <cstring>
#include <random>
#include <ctime>
using namespace std;
const int N = 1e6 + 5, Inf = 0x3f3f3f3f;

namespace IO {
    int len = 0;
    char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 26) + 1];
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define reg register
    inline int read() {
        reg char ch = gh();
        reg int x = 0;
        reg char t = 0;
        while (ch < '0' || ch > '9')
            t |= ch == '-', ch = gh();
        while (!(ch < '0' || ch > '9'))
            x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? -x : x;
    }
    inline void putc(char ch) {
        out[len++] = ch;
    }
    template <class T>
    void write(T x) {
        if (x < 0)
            putc('-'), x = -x;
        if (x > 9)
            write(x / 10);
        out[len++] = x % 10 | 48;
    }
    inline void flush() {
        fwrite(out, 1, len, stdout);
        len = 0;
    }
}
using IO::flush;
using IO::putc;
using IO::read;
using IO::write;

struct ANode {
    int x, y;
}a[N], atmp[N];
struct QNode {
    int op, x, y, X, Y, id;
}q[N], qtmp[N];
int n, m, ans[N];

namespace Sort {
    int head[N], val[N], nxt[N], len;
    void Ins(int x, int y) {
        val[++len] = y, nxt[len] = head[x];
        head[x] = len;
    }
    void Clear() { memset(head, 0, sizeof(int) * (n + 5)); len = 0; }
}
using namespace Sort;

struct SumBIT {
    int t[N];
    void Init() { memset(t, 0, sizeof(int) * (n + 2)); }
    void Add(int x, int k) {
        while (x <= n) {
            t[x] += k;
            x += x & -x;
        }
    }
    int Ask(int x) {
        int ret = 0;
        while (x) {
            ret += t[x];
            x -= x & -x;
        }
        return ret;
    }
}T1, T2;

struct MinBIT {
    int t[N];
    void Init() { memset(t, 0x3f, sizeof(int) * (n + 2)); }
    void Add(int x, int k) {
        while (x) {
            if (t[x] > k)t[x] = k;
            x -= x & -x;
        }
    }
    int Ask(int x) {
        int ret = Inf;
        while (x <= n) {
            if (ret > t[x])ret = t[x];
            x += x & -x;
        }
        return ret;
    }
}T3;

struct MaxBIT {
    int t[N];
    void Init() { memset(t, 0, sizeof(int) * (n + 2)); }
    void Add(int x, int k) {
        while (x) {
            if (t[x] < k)t[x] = k;
            x -= x & -x;
        }
    }
    int Ask(int x) {
        int ret = 0;
        while (x <= n) {
            if (ret < t[x])ret = t[x];
            x += x & -x;
        }
        return ret;
    }
}T4;//

mt19937 Rand(time(0));

namespace Treap {
#define lch(u) t[u].ls
#define rch(u) t[u].rs
    struct TreapNode {
        int ls, rs, x, y, pri, xtag, ytag, sz;
    }t[N];
    int cnt, rt;
    inline int newnode(int x, int y) {
        t[++cnt] = (TreapNode){ 0,0,x,y,(int)Rand(),0,0,1 };
        return cnt;
    }
    inline void pushup(int u) {
        t[u].sz = t[lch(u)].sz + t[rch(u)].sz + 1;
    }
    inline void pushdown(int u) {
        if (t[u].xtag) {
            if (lch(u))t[lch(u)].x = t[lch(u)].xtag = t[u].xtag;
            if (rch(u))t[rch(u)].x = t[rch(u)].xtag = t[u].xtag;
            t[u].xtag = 0;
        }
        if (t[u].ytag) {
            if (lch(u))t[lch(u)].y = t[lch(u)].ytag = t[u].ytag;
            if (rch(u))t[rch(u)].y = t[rch(u)].ytag = t[u].ytag;
            t[u].ytag = 0;
        }
    }
    void SplitByY(int u, int y, int &L, int &R) {//>y, <=y
        if (!u) { L = R = 0; return; }
        pushdown(u);
        if (t[u].y > y) {
            L = u;
            SplitByY(rch(u), y, rch(u), R);
            pushup(u);
        } else {
            R = u;
            SplitByY(lch(u), y, L, lch(u));
            pushup(u);
        }
    }
    void SplitByX(int u, int x, int &L, int &R) {//<=x, >x
        if (!u) { L = R = 0; return; }
        pushdown(u);
        if (t[u].x <= x) {
            L = u;
            SplitByX(rch(u), x, rch(u), R);
            pushup(u);
        } else {
            R = u;
            SplitByX(lch(u), x, L, lch(u));
            pushup(u);
        }
    }
    void SplitByXY(int u, int x, int y, int &L, int &R) {//<x|| =x and >=y
        if (!u) { L = R = 0; return; }
        pushdown(u);
        if (t[u].x < x || t[u].x == x && t[u].y >= y) {
            L = u;
            SplitByXY(rch(u), x, y, rch(u), R);
            pushup(u);
        } else {
            R = u;
            SplitByXY(lch(u), x, y, L, lch(u));
            pushup(u);
        }
    }
    int Merge(int L, int R) {
        if (!L || !R)return L + R;
        if (t[L].pri < t[R].pri) {
            pushdown(L);
            rch(L) = Merge(rch(L), R);
            pushup(L);
            return L;
        } else {
            pushdown(R);
            lch(R) = Merge(L, lch(R));
            pushup(R);
            return R;
        }
    }
}
using namespace Treap;

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i].x = read(), a[i].y = read();
    for (int i = 1; i <= m; ++i)
        q[i].op = read(), q[i].x = read(), q[i].y = read(), q[i].X = read(), q[i].Y = read(), q[i].id = i;

    //重排 a 和 q
    for (int i = 1; i <= n; ++i) {
        Ins(a[i].x, i);
        atmp[i] = a[i];
    }
    int tot = 0;
    for (int x = 1; x <= n; ++x)
        for (int i = head[x]; i; i = nxt[i])
            a[++tot] = atmp[val[i]];

    Clear();
    for (int i = 1; i <= m; ++i) {
        Ins(q[i].X, i);
        qtmp[i] = q[i];
    }
    tot = 0;
    for (int x = 1; x <= n; ++x)
        for (int i = head[x]; i; i = nxt[i])
            q[++tot] = qtmp[val[i]];

    //数询问右上角的点
    for (int ap = n, qp = m; qp; --qp) {
        while (ap && a[ap].x > q[qp].X) {
            T1.Add(a[ap].y, 1);
            --ap;
        }
        ans[q[qp].id] = n - ap - T1.Ask(q[qp].Y);
    }

    //标记哪些点被哪个修改推

    //询问按 x 排序
    Clear();
    for (int i = 1; i <= m; ++i) {
        Ins(q[i].x, i);
        qtmp[i] = q[i];//
    }
    tot = 0;
    for (int x = 1; x <= n; ++x)
        for (int i = head[x]; i; i = nxt[i])
            q[++tot] = qtmp[val[i]];

    Clear();
    T3.Init();
    for (int ap = n, qp = m; ap; --ap) {
        while (qp && q[qp].x >= a[ap].x) {
            T3.Add(q[qp].y, q[qp].id);
            --qp;
        }
        int t = T3.Ask(a[ap].y);
        if (t <= m)Ins(t, ap);
    }

    T1.Init();//加点，一维偏序
    for (int i = 1; i <= n; ++i) {
        T1.Add(a[i].x, 1);
        T2.Add(a[i].y, 1);
    }

    for (int i = 1; i <= m; ++i)
        qtmp[q[i].id] = q[i];
    for (int i = 1; i <= m; ++i)
        q[i] = qtmp[i];

    for (int i = 1; i <= m; ++i) {
        T4.Add(q[i].x, q[i].y);

        int L, p, R;
        SplitByX(rt, q[i].x, p, R);
        SplitByY(p, q[i].y, L, p);
        if (p) {
            if (q[i].op == 1)
                t[p].y = t[p].ytag = q[i].y;
            else
                t[p].x = t[p].xtag = q[i].x;
        }
        for (int j = head[i], ap, x, y; j; j = nxt[j]) {
            ap = val[j];
            x = a[ap].x, y = a[ap].y;
            T1.Add(x, -1), T2.Add(y, -1);
            if (q[i].op == 1)
                y = q[i].y;
            else
                x = q[i].x;
            int K;
            SplitByXY(p, x, y, p, K);
            p = Merge(Merge(p, newnode(x, y)), K);
        }
        rt = Merge(Merge(L, p), R);
        if (T4.Ask(q[i].X + 1) > q[i].Y)
            ans[i] = 0;
        else {
            SplitByX(rt, q[i].X, p, R);
            SplitByY(p, q[i].Y, L, p);
            ans[i] = T1.Ask(q[i].X) + T2.Ask(q[i].Y) + ans[i] + (t[L].sz + t[p].sz + t[R].sz) + t[p].sz - n;
            rt = Merge(Merge(L, p), R);
        }
        write(ans[i]), putc('\n');
    }
    flush();
    return 0;
}