为啥这种无脑二合一都做不出来了？哈哈哈，我真菜！

P4687 [IOI2008] Pyramid Base

• 给出一个 $N$ 列 $M$ 行的网格，称 从左往右 第 $i$ 列、从下往上 第 $j$ 行的网格坐标为 $(i,j)$。有 $P$ 个矩形障碍，第 $i$ 个矩形障碍左下角、右上角坐标分别为 $(X_{i_1},Y_{i_1})$ 和 $(X_{i_2},Y_{i_2})$，移除这个障碍需要 $C_i$ 的代价。小 L 希望在代价和不超过 $B$ 的情况移除一些障碍，并在网格中选取一个边长尽可能大的 正方形，满足她和所有障碍无交。
• Case 1：$P\le 10^3$，$B=0$，$N,M\le 10^6$。
• Case 2：$P\le 3\times 10^4$，$0<B\le 2\times 10^9$，$N,M\le 10^6$。
• Case 3：$P\le 4\times 10^5$，$B=0$，$N,M\le 10^6$。

默认 $\mathcal{O}(N)=\mathcal{O}(M)$。

Case 2

考虑二分。记当前二分的边长为 $L$，考虑对于以 $(L,L)$ 为左下角、$(N,M)$ 为右上角的矩形中的任意一个点维护一个信息（称这个矩形为信息的定义域）：以她为右上角边长为 $L$ 的正方形变得合法需要移除多少个障碍。显然所有与她相交的障碍都要删除。

考虑一个障碍 $i$ 对哪些点产生贡献，则会与这个障碍相交的点的正方形的右上角坐标一定位于以 $(X_{i_1},Y_{i_1})$ 为左下角、$(X_{i_2}+L-1,Y_{i_2}+L-1)$ 为右上角的矩形内（自动对信息的定义域取交）。

此时问题变成平面加，全部加完后求平面最大值。考对列虑扫描线，值域不大不需要离散化。枚举列坐标，维护这一列与上一列的变化量。考虑使用线段树维护区间加、区间最大值，在需要变化的区间上面区间加即可。使用标记永久化会方便一点。加完后，查询 $[L,M]$ 的最大值。注意到此时查询次数为 $\mathcal{O}(N)$ 而修改次数为 $\mathcal{O}(P)$ 二者不对等，可以考虑对 $[L,M]$ 建线段树而非 $[1,M]$，这样变成全局查询，容易 $\mathcal{O}(1)$ 时间。

时间复杂度为 $\mathcal{O}\left(N\log N + P\log^2 N\right)$。

Case 3

为啥 $4\times 10^5$ 和 $5\,\text{s}$ 会卡上面这个时间复杂度啊，无语。。。

此时 $B=0$ 不能移除任何障碍。考虑将正方形表示成行和列的区间 $[x,y],[i,j]$，满足 $j-i+1=y-x+1$。此时正方形的边长为 $j-i+1$，则求对于 $i$，以她为左边界列的边长最大的正方形可以转化为求最大的右边界列 $j$。

尝试枚举正方形最左边的列 $i$，考虑存在 $[i,j]$ 为列区间的正方形的充要条件。

记 $a_x$ 表示第 $x$ 行 $[i,j]$ 这些列被多少个障碍矩形覆盖，则存在左边界列为 $i$ 右边界列为 $j$ 的正方形，等价于存在长度 $\ge j-i+1$ 的 $a_x$ 全 $0$ 连续段。充分性考虑选择这个连续段任意一个长度为 $j-i+1$ 的子段均能与 $[i,j]$ 构成正方形；必要性考虑 $[x,y]$ 这个行区间就是一个长度 $\ge j-i+1$ 的 $a_x$ 全 $0$ 连续段。

不难发现当 $i$ 变大时，最大的右边界列 $j$ 不降，因为 $i$ 变大时，$a_x$ 不升，因此最长全 $0$ 连续段长度不降。只需选取同一个 $j$ 时，就能得到一个合法的正方形。考虑双指针维护，这部分被细节创飞了。

考虑实现时找到第一个不合法位置的然后她减一就是要求的最大的右边界列 $j$。记当前 闭区间 为 $[i,j]$，此时已经维护好 $[i,j]$ 对应的 $a_x$。若不合法，则退出循环；否则需要维护 $[i,j+1]$ 对应的 $a_x$ 进入下一轮判断。考虑 $[i,j+1]$ 对应的 $a_x$ 会发生哪些变化，显然左边界列为 $j+1$ 的障碍矩形会新覆盖 $[i,j+1]$ 列上其对应的行区间，使得这些 $a_x$ 加 $1$。问题变成区间加、求全局最长全 $0$ 段长度。同样考虑线段树标记永久化维护。注意到任意时刻 $a_x\ge 0$，因此只需要维护区间最长的最小值连续段长度，并判断最小值是否为 $0$ 即可。若两个子节点最小值不同，则继承更小的那个儿子的部分信息；否则类似区间最大子段和那样合并两个孩子的信息。反正是容易合并的。

从 $[1,0]$ 开始双指针即可。

当 $i$ 右移 $1$ 时，也要考虑 $a_x$ 的变化量。显然右边界列为 $i$ 的矩形会少覆盖其 $[i+1,j]$ 上其对应的行区间。$a_x$ 区间减 $1$ 即可。

对于每个 $i$ 计算得到的最大值即为答案。由于指针移动 $\mathcal{O}(N)$ 次且不会重复进行一列的区间修改，因此修改次数的总和与矩形个数同阶为 $\mathcal{O}(P)$。所以时间复杂度为 $\mathcal{O}(N+P\log N)$。

空间复杂度均为 $\mathcal{O}(N)$。

#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
using namespace std; const int N = 1e6 + 5, P = 400005, inf = 1e9;
int n, m, b, p; struct rec { int xa, ya, xb, yb, c; } a[P];
struct Lines { int l, r, v; }; vector<Lines> g[N];
void addrec(int xa, int ya, int xb, int yb, int v, int lim) {
    xa = max(lim, xa); ya = max(lim, ya); xb = min(n, xb); yb = min(m, yb);
    if (xa > xb || ya > yb) return;
    g[xa].emplace_back(Lines{ya, yb, v}); g[xb + 1].emplace_back(Lines{ya, yb, -v});
}
namespace Case2 {
    struct Seg {
        int s[N << 2], tg[N << 2];
        void build(int x, int l, int r) {
            tg[x] = 0; if (l == r) return void(s[x] = 0); int mid = l + r >> 1;
            build(ls(x), l, mid); build(rs(x), mid + 1, r);
            s[x] = min(s[ls(x)], s[rs(x)]);
        }
        void M(int x, int l, int r, int ql, int qr, int v) {
            if (ql <= l && r <= qr) return s[x] += v, tg[x] += v, void();
            int mid = l + r >> 1; if (ql <= mid) M(ls(x), l, mid, ql, qr, v);
            if (qr > mid) M(rs(x), mid + 1, r, ql, qr, v);
            s[x] = min(s[ls(x)], s[rs(x)]); s[x] += tg[x];
        }
    } tr;
    bool chk(int L) {
        tr.build(1, L, m); for (int i = 1; i <= n + 1; ++i) g[i].clear();
        for (int i = 1; i <= p; ++i)
            addrec(a[i].xa, a[i].ya, a[i].xb + L - 1, a[i].yb + L - 1, a[i].c, L);
        for (int i = L; i <= n; ++i) {
            for (auto [l, r, v] : g[i]) tr.M(1, L, m, l, r, v);
            if (tr.s[1] <= b) return 1;
        }
        return 0;
    }
    void work() {
        int l = 1, r = min(n, m), f = 0, mid;
        while (l <= r) {
            mid = l + r >> 1; if (chk(mid)) f = mid, l = mid + 1; else r = mid - 1;
        }
        print(f);
    }
}
namespace Case3 {
    struct node {
        int mn, lmx, rmx, ans, len;
        node operator+(const node &o) const {
            node ret; ret.mn = min(mn, o.mn); ret.len = len + o.len;
            if (ret.mn != mn) ret.lmx = 0, ret.rmx = o.rmx, ret.ans = o.ans;
            else if (ret.mn != o.mn) ret.rmx = 0, ret.lmx = lmx, ret.ans = ans;
            else
                ret.lmx = lmx + (lmx == len ? o.lmx : 0),
                ret.rmx = o.rmx + (o.rmx == o.len ? rmx : 0),
                ret.ans = max({ans, o.ans, rmx + o.lmx});
            return ret;
        }
    };
    struct Seg {
        node s[N << 2]; int tg[N << 2];
        void build(int x, int l, int r) {
            s[x].lmx = s[x].rmx = s[x].ans = s[x].len = r - l + 1;
            if (l == r) return; int mid = l + r >> 1;
            build(ls(x), l, mid); build(rs(x), mid + 1, r);
            s[x] = s[ls(x)] + s[rs(x)];
        }
        void M(int x, int l, int r, int ql, int qr, int v) {
            if (ql <= l && r <= qr) return s[x].mn += v, tg[x] += v, void();
            int mid = l + r >> 1; if (ql <= mid) M(ls(x), l, mid, ql, qr, v);
            if (qr > mid) M(rs(x), mid + 1, r, ql, qr, v);
            s[x] = s[ls(x)] + s[rs(x)]; s[x].mn += tg[x];
        }
        int Len() { return !s[1].mn ? s[1].ans : 0; }
    } tr;
    void work() {
        tr.build(1, 1, m); int ans = 0;
        for (int i = 1; i <= p; ++i)
            addrec(a[i].xa, a[i].ya, a[i].xb, a[i].yb, 1, 1);
        for (int i = 1, j = 0; i <= n; ++i) {
            for (auto [l, r, v] : g[i]) if (v < 0) tr.M(1, 1, m, l, r, v);
            for (; j <= n && j - i + 1 <= tr.Len(); ++j)
                for (auto [l, r, v] : g[j + 1]) if (v > 0) tr.M(1, 1, m, l, r, v);
            ans = max(ans, j - i);
        }
        print(ans);
    }
}
signed main() {
    read(n); read(m); read(b); read(p);
    for (int i = 1; i <= p; ++i)
        read(a[i].xa), read(a[i].ya), read(a[i].xb), read(a[i].yb), read(a[i].c);
    if (b) Case2::work(); else Case3::work(); return 0;
}