【题解】[Ynoi2009] rprmq

题目链接:[Ynoi2009] rprmq

题意:

有一个 $n \times n$ 的矩阵 $A$,初始全是 $0$,有 $m$ 次修改操作和 $q$ 次查询操作,先进行所有修改操作,然后进行所有查询操作

一次修改操作会给出 $l_1,l_2,r_1,r_2,x$,代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素加上一个值 $x$。

一次查询操作会给出 $l_1,l_2,r_1,r_2$,代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $A_{i,j}$ 元素的最大值。

$1\le n,m\le 5\times 10^4,1\le q \le 5\times 10^5$。

或许是一个实现方式有一些小差别的做法。

首先考虑离线分治,每次考虑跨过分治中心的查询与修改。

将第二维放在线段树上,第一维做扫描线,每次从分治中心 $\text{mid}$ 向左、右进行拓展,如果遇到一个矩阵的开始,或一个矩阵的结束,就在线段树上进行区间修改。

由于我们需要的是“矩形 $\max$”,而在分治的时候,第一维变成了时间,所以这个问题在这里就是线段树历史 $\max$。

于是对于一个跨过 $\text{mid}$ 的询问,我们只需要在扫描线到了左端点处,或到了右端点处的时候,查询区间历史最大值即可。

这一部分中,一个实现的细节是当扫描完 $\text{mid}$ 左侧时,需要将整棵线段树的状态 $\text{roll back}$ 回到还没有扫描左侧时的状态,然后再进行右侧的扫描线。这个可以通过直接对线段树 $\text{DFS}$,将每一个遍历过的节点的权值进行回滚来做到。

另一个容易错的点是,如果一个位置上同时有矩形的结束与矩形的开始(即有区间加与区间减操作),那么应该先进行区间减操作,这样才能使历史 $\max$ 保持正确。

这样单次查询的复杂度就是 $\mathcal{O}(\log n)$ 的,$\mathcal{O}(q\log n)$ 的总复杂度可以接受。

但是修改的复杂度实际上是不太对的。在一般的分治中,其时间复杂度的保证基于每一个操作在进入分治树下一层的时候,都只会进入一边(一个分治树节点)。然而在这里,一个跨越了 $\text{mid}$ 的操作,可以同时向 $[\text{L},\text{mid}]$ 与 $[\text{mid+1},\text{R}]$ 进行递归。

也就是说,任意一个修改实际上是在分治的时间维度的一个区间上存在的,而分治的结构本身就类似一棵线段树,所以可以认为一个操作是存在在分治树的一个区间上的。

由于分治树是线段树结构,而操作存在在分治树的区间上,这让我们想到“线段树分治”。线段树分治的思想就是将一个存在在某个时间段的修改划分为 $\log$ 个部分,通过在 $\text{DFS}$ 整棵线段树的时候,维护当前线段树节点的祖先的所有修改操作,来保证复杂度。

于是,把这个思想套到本题上,就变成了:如果一个操作完全覆盖了当前的分治区间,则把他看作一个类似“初值”的部分。

因为在这个区间中这次操作永远存在,所以只需要在进入区间的时候将该操作执行,则分治树的子树中这个操作就一直存在了。

从而一个操作被拆分成了 $\mathcal{O}(\log n)$ 次操作,总复杂度是 $\mathcal{O}(m\log^2n+q\log n)$。

一个细节:由于进行分治的过程中可能需要进行状态的回滚,而状态的修改次数是 $\mathcal{O}(m\log^2 n)$ 的,直接记录的话空间将与时间同阶。

不过实际上,即使修改次数是 $\mathcal{O}(n\log^2 n)$,其修改的元素个数却是 $\mathcal{O}(n\log n)$,可以通过把可回退的部分较为精细地实现来保证空间复杂度。

//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define pb emplace_back
#define LL long long
#define mp make_pair
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 5e4 + 10;
const int MAXQ = 5e5 + 10;
const int MAXD = 16;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

struct info {
    int l, r, x;
    info(int _l = 0, int _r = 0, int _x = 0) : l(_l), r(_r), x(_x) {}
    bool operator < (const info &b) const { return x < b.x; }
};

int n, m, q;
LL Ans[MAXQ];
vec<info> qp[MAXN], add[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

struct NODE {
    int l1, l2, r1, r2, x, id;
    void read(int i) { id = i, ::read(l1), ::read(l2), ::read(r1), ::read(r2); }
}; vec<NODE> qs[MAXN << 2], mdf[MAXN << 2];

inline LL max(const LL x, const LL y) { return x > y ? x : y; }

namespace SMT {
    int D;
    LL mx[MAXN << 2], hmx[MAXN << 2], tag[MAXN << 2], htag[MAXN << 2];
    LL mx_bak[MAXD][MAXN << 2], hmx_bak[MAXD][MAXN << 2];
    LL tag_bak[MAXD][MAXN << 2], htag_bak[MAXD][MAXN << 2];
    bool vis[MAXD][MAXN << 2];
    inline void pushup(const LL &x) {
        mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
        hmx[x] = max(hmx[x], mx[x]);
    }
    inline void push(const int &x, const LL &v, const LL &hv) {
        htag[x] = max(htag[x], tag[x] + hv); 
        tag[x] = tag[x] + v;
        hmx[x] = max(hmx[x], mx[x] + hv); 
        mx[x] = mx[x] + v;
    }
    inline void pushdown(const LL &x) {
        push(x << 1, tag[x], htag[x]);
        push(x << 1 | 1, tag[x], htag[x]);
        htag[x] = 0; tag[x] = 0;
    }
    void save(int x) {
        if(!vis[D][x]) {
            vis[D][x] = true;
            mx_bak[D][x] = mx[x], hmx_bak[D][x] = hmx[x];
            tag_bak[D][x] = tag[x], htag_bak[D][x] = htag[x];
        }
    }
    void update(int x, int l, int r, int L, int R, int v) {
        save(x);
        if(L <= l && r <= R) return push(x, v, v), void();
        int mid = (l + r) >> 1; 
        save(x << 1), save(x << 1 | 1); pushdown(x);
        if(L <= mid) update(x << 1, l, mid, L, R, v);
        if(R > mid) update(x << 1 | 1, mid + 1, r, L, R, v);
        pushup(x);
    }
    LL query(int x, int l, int r, int L, int R) {
        save(x);
        if(L <= l && r <= R) return hmx[x];
        int mid = (l + r) >> 1; LL res = 0;
        save(x << 1), save(x << 1 | 1); pushdown(x);
        if(L <= mid) res = max(res, query(x << 1, l, mid, L, R));
        if(R > mid) res = max(res, query(x << 1 | 1, mid + 1, r, L, R));
        return res;
    }
    void clear(int x, int l, int r) {
        if(!vis[D][x]) return;
        vis[D][x] = false;
        if(l == r) return;
        int mid = (l + r) >> 1;
        clear(x << 1, l, mid), clear(x << 1 | 1, mid + 1, r);
    }
    void roll(int x, int l, int r) {
        if(!vis[D][x]) return;
        mx[x] = mx_bak[D][x], hmx[x] = hmx_bak[D][x];
        tag[x] = tag_bak[D][x], htag[x] = htag_bak[D][x];
        vis[D][x] = false;
        if(l == r) return;
        int mid = (l + r) >> 1;
        roll(x << 1, l, mid), roll(x << 1 | 1, mid + 1, r);
    }
}

using SMT::update;
using SMT::query;
using SMT::clear;
using SMT::roll;
using SMT::D;

void solve(int _x, int vL, int vR, int dep) {
    if(vL > vR || !qs[_x].size()) return;
    int mid = (vL + vR) >> 1; NODE cur;
    for(auto x : qs[_x]) {
        if(x.r1 < mid) qs[_x << 1].pb(x);
        if(x.l1 > mid) qs[_x << 1 | 1].pb(x);
        if(x.l1 <= mid && mid <= x.r1) {
            qp[x.l1].pb(info(x.l2, x.r2, x.id));
            qp[x.r1].pb(info(x.l2, x.r2, x.id));
        }
    }
    for(auto x : mdf[_x]) {
        if(x.r1 < mid) {
            mdf[_x << 1].pb(x), add[x.r1].pb(info(x.l2, x.r2, x.x));
            if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x));
        } else if(x.l1 > mid) {
            mdf[_x << 1 | 1].pb(x), add[x.l1].pb(info(x.l2, x.r2, x.x));
            if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x));
        } else if(x.l1 <= mid && mid <= x.r1) {
            add[mid].pb(info(x.l2, x.r2, x.x));
            if(vL < x.l1) add[x.l1 - 1].pb(info(x.l2, x.r2, -x.x));
            if(x.r1 < vR) add[x.r1 + 1].pb(info(x.l2, x.r2, -x.x));
        }
    } D = dep; clear(1, 1, n);
    for(int i = mid; i >= vL; --i) {
        sort(add[i].begin(), add[i].end());
        for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x);
        for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r));
    } roll(1, 1, n);
    for(int i = mid; i <= vR; ++i) {
        sort(add[i].begin(), add[i].end());
        for(auto x : add[i]) update(1, 1, n, x.l, x.r, x.x);
        for(auto x : qp[i]) Ans[x.x] = max(Ans[x.x], query(1, 1, n, x.l, x.r));
    } roll(1, 1, n);
    for(int i = vL; i <= vR; ++i) add[i].clear(), qp[i].clear();
    for(auto x : mdf[_x]) {
        if(x.l1 < mid && mid <= x.r1) {
            if(x.l1 <= vL) update(1, 1, n, x.l2, x.r2, x.x);
            else { cur = x; cur.r1 = mid - 1; mdf[_x << 1].pb(cur); }
        }
    } solve(_x << 1, vL, mid - 1, dep + 1); D = dep; roll(1, 1, n);
    for(auto x : mdf[_x]) {
        if(x.l1 <= mid && mid < x.r1) {
            if(x.r1 >= vR) update(1, 1, n, x.l2, x.r2, x.x);
            else { cur = x; cur.l1 = mid + 1; mdf[_x << 1 | 1].pb(cur); }
        }
    } solve(_x << 1 | 1, mid + 1, vR, dep + 1); D = dep; roll(1, 1, n);
}

signed main () {
#ifdef FILE
    freopen("P6109.in", "r", stdin);
    freopen("P6109.out", "w", stdout);
#endif
    read(n), read(m), read(q); mdf[1].resize(m), qs[1].resize(q);
    for(int i = 0; i < m; ++i) mdf[1][i].read(i), read(mdf[1][i].x);
    for(int i = 0; i < q; ++i) qs[1][i].read(i + 1);
    solve(1, 1, n, 0);
    for(int i = 1; i <= q; ++i) printf("%lld\n", Ans[i]);
    return 0;
}
添加新评论