二维数点

有时，我们要处理的操作有两个维度的约束条件。例如，有 \(n\) 个元素，每个元素都有两个属性 \(a_i\) 和 \(b_i\)，要求统计所有满足 \(a_i\in[l_1,r_1]\) 且 \(b_i\in [l_2,r_2]\) 的元素的贡献。这种问题被称为二维数点问题。

通常情况下，二维数点问题可以直接离线解决；若强制在线，则可以使用[主席树]解决。

整体思路

我们将所有操作（修改+查询）混合并按照其中一个维度排序，按顺序依次处理（这个过程叫做扫描线），第二个维度用数据结构维护并统计贡献。

使用二维数点的条件

如何判断约束是几个维度的，能否直接离线后二维数点解决？

在不等式形式（\(x\le r_0\) 或 \(l_0\le x\le r_0\) 的形式）的约束中，同一个不等号两侧的两个式子可以看作是在同一个维度。或：几个不等式就是几个维度。

• 只包含一个维度的约束条件可以直接 在线+一维数据结构 解决；
• 包含两个维度的约束条件通常 可以使用二维数点解决。

注意特殊情况：

• 若维护的信息不可差分（最值、gcd等），且两个维度的约束同时具有上下界（\(l_1\le x\le r_1\)，\(l_2\le y\le r_2\)），则无法通过数点转化问题（主席树也做不了，只能树套树 ——fjj）。
• 若维护的信息不可差分，但只有一个维度的约束同时具有上下界（\(x\le r_1\)，\(l_2\le y\le r_2\)），可以对另一个维度（\(x\)）排序并扫描线，该维度（\(y\)）用线段树解决（因为线段树不要求维护的信息可差分）
• 若维护的信息可以差分，则可以将一个询问拆成两个询问前缀相减直接扫描线解决。

例题

P3899 [湖南集训] 更为厉害

题目大意

给定一棵 \(n\)（\(n\le 3\times 10^5\)）个节点的有根树，根节点为 \(1\) 节点。给定 \(q\)（\(q\le 3\times 10^5\)）组询问，每组询问给定整数 \(p\) 和 \(k\)，求满足以下条件的二元组 \((a,b)\) 的数量：

• 节点 \(a\) 和节点 \(p\) 的距离不超过 \(k\)；
• 节点 \(b\) 同时是节点 \(a\) 和节点 \(p\) 的子节点；
• \(a\)、\(b\)、\(p\) 互不相同；

容易发现 \(a\) 和节点 \(p\) 总在一条返祖链上。先讨论 \(a\) 和 \(p\) 的祖孙关系：

• 若 \(a\) 是 \(p\) 的（真）祖先，则贡献为 \((sz[p]-1)\times \min(dep[p]-1,k)\)；
• 若 \(a\) 是 \(p\) 的（真）子节点，则贡献为 \(\sum\limits_{dis(a,p)\le k,\ a\in subtree(p)}sz[a]-1\)；

第一种情况可以直接计算，这里着重考虑第二种情况。我们发现，\(dis(a,p)\le k\) 且 \(a\in subtree(p)\) 可以抽象为 dfs 序的限制和深度的限制：

\[ \begin{cases} dfn[a]\in\big(dfn[p],dfn[p]+sz[p]\big)\\ dep[a]\in\big(-\infty,dep[p]+k\big] \end{cases} \]

这正是一种二维数点问题。

• 将每个节点视为一个“修改”操作， \(dep[u]\) 作为扫描线的排序关键字，在数据结构的 \(dfn[u]\) 位置单点修改，权值为 \(sz[u]-1\)；
• 将每个询问的 \(dep[p]+k\) 作为排序关键字，在数据结构上查询 \(\big[dfn[p]+1,dfn[p]+sz[p]-1\big]\) 的区间和，即为询问的答案；

我们将所有操作混合并按 key 排序，依次处理每个操作，这样就能保证满足查询操作的 \(dep\) 限制。将每个查询的结果贡献到对应的 ans 数组上，就能得到最后的答案。

关于线段树合并

本题也是线段树合并的模板题。线段树合并可以理解为：对 dfn 序扫描线，并且不要求信息对于 dfn 序可差分，同时使用线段树维护另一维度（也不要求可差分）。

如果一个树上问题包含二维约束，且信息不可差分，而其中一个维度是子树的限制，则无法使用扫描线+二维数点解决，但线段树合并可以实现。详见线段树合并。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 3E5 + 10;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int nn, head[N];

struct Op {
    int tp;
    int dfnl, dfnr, dep;
    int num, w;
    inline bool operator<(const Op &other) const {
        if(dep != other.dep) return dep < other.dep;
        return tp > other.tp;
    }
};

void addEdge(int u, int v) {
    pool[++nn] = {v, head[u]};
    head[u] = nn;
}

int n, q;
int dep[N], sz[N], ans[N], dfn[N], dt;

void dfs(int u, int f) {
    sz[u] = 1;
    dep[u] = dep[f] + 1;
    dfn[u] = ++dt;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

vector<Op> op;

namespace BIT {
    inline int lowbit(int x) { return x & -x; }
    int sum[N];
    void modify(int p, int v) {
        for(int i = p + 1; i <= n + 5; i += lowbit(i)) sum[i] += v;
    }
    int query(int p) {
        int res = 0;
        for(int i = p + 1; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
}

signed main() {

    cin >> n >> q;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0);
    for(int i = 1; i <= n; i++) sz[i]--;

    for(int i = 1; i <= q; i++) {
        int p, k;
        cin >> p >> k;
        ans[i] += min(dep[p] - 1, k) * sz[p];
        op.push_back({0, dfn[p] + 1, dfn[p] + sz[p], dep[p] + k, i, 1});
    }

    for(int i = 1; i <= n; i++) {
        op.push_back({1, dfn[i], dfn[i], dep[i], 0, sz[i]});
    }

    sort(op.begin(), op.end());

    for(auto i : op) {
        if(i.tp == 1) {
            BIT::modify(i.dfnl, i.w);
        } else {
            ans[i.num] += BIT::query(i.dfnl, i.dfnr) * i.w;
        }
    }

    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

二维数颜色

题目大意

给定 \(n\) 个平面上的点，第 \(i\) 个点位于 \((x_i,y_i)\)，颜色为 \(c_i\)。有 \(q\) 次询问，每次询问给出 \((a,b)\)，询问 \(x\le a,y\le b\) 的点一共包含多少种颜色。

我们可以对 \(x\) 扫描线，用树状数组维护 \(y\)。那如何维护区间颜色数量呢？注意到询问都是 2-side 矩形，因此同种颜色的所有点中只需要考虑 \(y\) 最小的产生的贡献。这样，我们用一个桶数组记录每一种颜色的 \(y\) 坐标的历史最小值，也就是当前待在树状数组里的那一个。如果发现当前点的 \(y\) 更小，则删除原来的节点，加入当前节点。查询时直接查询前缀和即可。

P11364 [NOIP2024] 树上查询

题目大意

给定一棵有根树，根结点编号为 \(1\)，每个结点 \(u\) 的深度 \(\text{dep}_ u\) 定义为 \(u\) 到 \(1\) 的简单路径上的结点数量。

除此之外，再定义 \(\text{LCA*}(l, r)\) 为编号在 \([l, r]\) 中所有结点的最近公共祖先，即 \(l, l + 1, \dots , r\) 的公共祖先结点中深度最大的结点。

你需要回答 \(q\) 个询问。每个询问给定三个参数 \(l, r, k\)，需要求出

\[\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}\]

数据量级 \(5\times 10^5\)

重要结论：编号在 \([l_1,r_1]\) 区间内的所有结点的 lca 一定是 lca(i,i+1)（\(i\in[l_1,r_1)\)）中深度最小的一个。

记 \(b_i=dep[lca(i,i+1)]\)，问题就转化为查找区间 \([l,r)\) 中[长度为 \(k-1\) 的连续子段的最小值]的最大值。而 \(k=1\) 的情况，使用 st 表预处理即可。

统计最小值的最大值，考虑每个数字作为最小值需要满足什么条件，再看当前询问是否满足这些条件，选取所有满足的数字中最大的一个。

具体的，我们先求出每个位置的 \(b_i\) 作为最小值的极大区间 \([x_i,y_i]\)（单调栈维护），分讨 \([x_i,y_i]\) 和询问 \((l,r,k)\) 的关系，有两种情况：

\[ \begin{align*} y_i>r\Rightarrow&\ x_i\le r-k+1\\ l+k-1\le y_i\le r\Rightarrow&\ y_i-x_i+1\ge k \end{align*} \]

我们发现 \([x_i,y_i]\) 区间一共有 \(n-1\) 个，时间足够处理所有区间；同时这种约束是二维的，考虑使用二维数点解决。我们将两种情况分别统计，第一种情况按 \(y_i\) 和 \(r\) 扫描线；第二种情况按 \(k\) 和 \(y_i-x_i+1\) 扫描线。因为题目是询问满足条件的最大值，区间最大值需要使用线段树维护。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int N = 5E5 + 10;
const int LOGN = 22;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v;
    int next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct Query {
    int l, r, k, ds;
} q[N]; 

struct Op {
    int tp, key, l, r, w, id;
    inline bool operator<(const Op &other) const {
        if(key != other.key) return key < other.key;
        return tp > other.tp;
    } 
};

int n, m;
int anc[N][LOGN], dep[N], st[N][LOGN], lg[N]; 
int b[N], x[N], y[N], ans[N]; 

void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    anc[u][0] = f;
    for(int i = 1; i < LOGN; i++) {
        anc[u][i] = anc[ anc[u][i - 1] ][i - 1];
    }
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs(v, u);
    } 
}

int getLca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = LOGN - 1; i >= 0; i--) if(dep[anc[x][i]] >= dep[y]) x = anc[x][i];
    if(x == y) return x;
    for(int i = LOGN - 1; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

int ST_query(int l, int r) {
    int d = lg[r - l + 1];
    return max(st[l][d], st[r - (1 << d) + 1][d]);
}

namespace Seg_T {
    int Max[4 * N]; 
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void push_up(int p) {
        Max[p] = max(Max[lc(p)], Max[rc(p)]); 
    }
    void build(int p, int l, int r) {
        if(l == r) {
            Max[p] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p); 
    }
    void modify(int p, int l, int r, int q, int v) {
        if(l == r) {
            Max[p] = max(Max[p], v);
            return;
        }
        int mid = (l + r) >> 1;
        if(mid >= q) modify(lc(p), l, mid, q, v);
        else modify(rc(p), mid + 1, r, q, v); 
        push_up(p); 
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) {
            return Max[p];
        }
        int mid = (l + r) >> 1;
        if(mid >= qr) return query(lc(p), l, mid, ql, qr);
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        return max(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr)); 
    }
    inline void modify(int p, int v) {
        modify(1, 1, n, p, v);
    }
    inline int query(int l, int r) {
        if(l > r) return 0;
        return query(1, 1, n, l, r);
    }
}

int sta[N], top;

vector<Op> op; 

signed main() {

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    } 

    dfs(1, 0);

    for(int i = 1; i <= n; i++) st[i][0] = dep[i];
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int j = 1; j < LOGN; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        } 
    }

    for(int i = 1; i <= n - 1; i++) {
        b[i] = dep[getLca(i, i + 1)];
    }

    for(int i = 1; i <= n - 1; i++) {
        while(top && b[sta[top]] >= b[i]) top--;
        x[i] = sta[top] + 1;
        sta[++top] = i;
    }
    top = 0;
    sta[0] = n;
    for(int i = n - 1; i >= 1; i--) {
        while(top && b[sta[top]] >= b[i]) top--;
        y[i] = sta[top] - 1;
        sta[++top] = i;
    }

    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r >> q[i].k;
        q[i].r--;
        q[i].k--;
        if(q[i].l > q[i].r) {
            ans[i] = dep[q[i].l];
            q[i].ds = 1;
        } else if(q[i].k == 0) {
            ans[i] = ST_query(q[i].l, q[i].r + 1);
            q[i].ds = 1;
        } 
    }

    Seg_T::build(1, 1, n);
    for(int i = 1; i <= n - 1; i++) {
        op.push_back({1, -y[i], x[i], -1, b[i], -1});
    }
    for(int i = 1; i <= m; i++) {
        if(!q[i].ds) op.push_back({0, -q[i].r, 1, q[i].r - q[i].k + 1, -1, i});
    }
    sort(op.begin(), op.end());
    for(Op o : op) {
        if(o.tp == 1) {
            Seg_T::modify(o.l, o.w);
        } else {
            ans[o.id] = max(ans[o.id], Seg_T::query(o.l, o.r));
        }
    }

    op.clear();
    Seg_T::build(1, 1, n);
    for(int i = 1; i <= n - 1; i++) {
        op.push_back({1, -(y[i] - x[i] + 1), y[i], -1, b[i], -1});
    }
    for(int i = 1; i <= m; i++) {
        if(!q[i].ds) op.push_back({0, -q[i].k, q[i].l + q[i].k - 1, q[i].r - 1, -1, i}); 
    }
    sort(op.begin(), op.end());
    for(Op o : op) {
        if(o.tp == 1) {
            Seg_T::modify(o.l, o.w);
        } else {
            ans[o.id] = max(ans[o.id], Seg_T::query(o.l, o.r));
        }
    }

    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    } 

    return 0;
} 

P7302 [NOI1998] 免费的馅饼

题目大意

在平面的第一象限内有 \(n\) 个点 \((p_i,h_i)\)，初始时你位于 \(x\) 轴正半轴的任意整数位置。设当前位于点 \((x,y)\)，则下一秒你可以前往 \((x+a,y+1)\)，\(a\in\{-2,-1,0,1,2\}\)。当你碰到第 \(i\) 个点可以获得 \(v_i\) 的分数。问最多获得多少分数。

值域 \(10^8\)，点数 \(10^5\)。

考虑朴素 DP。设 \(f_i\) 表示走到第 \(i\) 个点处最多可以获得多少分数。写出状态转移方程：

\[ f_i=\max_{|p_i-p_j|\le 2(t_i-t_j)}\{f_j\}+v_i \]

时间复杂度 \(O(n^2)\)，需要优化。

我们拆开绝对值

\[ \begin{cases} p_i-p_j\le 2t_i-2t_j\\ p_j-p_i\le 2t_i-2t_j \end{cases} \]

移项：

\[ \begin{cases} p_i-2t_i\le p_j-2t_j\\ p_i+2t_i\ge p_j+2t_j \end{cases} \]

这正是一种二维数点问题。我们按 \(p_i+2t_i\) 为第一关键字降序排序，\(p_i-2t_i\) 为第二关键字升序排序。依次处理所有点，用树状数组以 \(p_i-2t_i\) 为下标，维护 \(f_i\) 的前缀最大值即可。

技巧

• 带有一个绝对值的式子可以拆成两个不带绝对值的式子；

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define cint const int&
using namespace std;
const int N = 1E5 + 10;

struct Op {
    int key, pos, val;
    inline bool operator<(const Op &other) const {
        if(key != other.key) return key > other.key;
        return pos < other.pos;
    }
};

int w, n;
int num[N], nn;

vector<Op> op;

inline void lisanhua() {
    for(Op &o : op) {
        num[++nn] = o.pos;
    }
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(Op &o : op) {
        o.pos = lower_bound(num + 1, num + 1 + nn, o.pos) - num;
    }
}

namespace BIT {
    int mx[N];
    inline int lowbit(cint x) { return x & -x; }
    inline void modify(cint p, cint v) {
        for(int i = p; i < N; i += lowbit(i)) {
            if(mx[i] >= v) break;
            mx[i] = v;
        }
    }
    inline int query(cint p) {
        int res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) {
            res = max(res, mx[i]);
        }
        return res;
    }
}

int main() {

    w = read(), n = read();
    for(int i = 1; i <= n; i++) {
        int t, p, v;
        t = read(), p = read(), v = read();
        op.push_back({p + 2 * t, p - 2 * t, v});
    }

    sort(op.begin(), op.end());

    lisanhua();

    for(Op &o : op) {
        int tmp = BIT::query(o.pos);
        BIT::modify(o.pos, tmp + o.val);
    }

    cout << BIT::query(n) << endl;

    return 0;
}