非常好P12699 [KOI 2022 Round 2] 红蓝，使我的线段树旋转

Forgotten_freopen · 2025-07-17 16:00:33 · 题解

神人题目，写死人

提供一个线段树+离散化+类似双指针或者说，两根扫描线的做法。

我们先将横坐标和纵坐标离散化，然后用一上一下两根线夹住一个高度差不超过 H 的矩形（底自然是无限长啦），在块内加入所有的红点和蓝点，加入红点时在线段树上右端点为 x_i 离散化后的值，左端点为 x_i + W 离散化后的值这段区间加 1（因为这段区间上的点作为答案矩形右下角的点时都可以覆盖到这个点），而蓝点则在这段区间上 -1。

随后，我们在线段树上维护最大值和最小值，这样查询时我们只要得到全局的最大值和最小值的绝对值，就可以算出两种颜色之差的最大值了。

进一步我们可以发现：因为矩形规定了高度为 H ，所以下线向上移动时上线可以同时向上移动。这个过程像极了双指针。

所以，我们可以先把下线放在最底部，逐步向上移动上线直到和下线的距离即将超过 H，并在向上移动上线的同时加入上线扫过的点；接下来，使用线段树维护答案以及取得该答案的位置，并更新答案；最后，将在下线上的点删除，并将下线上移一个位置。反复操作直到扫完所有的点，即可得到答案。

最后两个要注意的点：

1. 上下线可能出现的位置有 3(n + m) 个，数组别开小了。
2. 我们得到的取到答案的点在矩形的右下角，所以输出时横坐标要减去 W。如果不想减的话，可以把上面提到的区间 [x_i,x_i + W] 改成 [x_i - W,x_i]，这样就可以得到左下角的点。

#include <bits/stdc++.h>
#define int1 int
#define N 600000
#define M 1200000
#define INF 1145141919
#define ls (d << 1)
#define rs (d << 1 | 1)
using namespace std;
int1 n,nm,m,H,W,i,l[N + 5],r[N + 5],y[N + 5],v[N + 5];
vector<int1> aty[N + 5];//把纵坐标相同的点记录在一起
int1 siz[N + 5];
int1 lth[2],lsh[2][N + 5];//离散化用的
int1 maxn[M + 5],minn[M + 5],tag[M + 5];//区间最大值/区间最小值/懒标记
int1 maxp[M + 5],minp[M + 5];//区间最大值出现的位置/区间最小值出现的位置
int1 ans,ansx,ansy;
int1 read(){
    int1 x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void uprint(int1 x){
    if(x > 9){
        uprint(x / 10);
    }
    putchar(x % 10 ^ 48);
    return ;
}
void print(int1 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    uprint(x);
    return ;
}
void ps(int1 x){
    print(x);
    putchar(' ');
    return ;
}
void pe(int1 x){
    print(x);
    putchar('\n');
    return ;
}
void push_up(int1 d){//上传，更新答案
    if(maxn[ls] >= maxn[rs]){
        maxp[d] = maxp[ls];
        maxn[d] = maxn[ls];
    }else{
        maxp[d] = maxp[rs];
        maxn[d] = maxn[rs];
    }
    if(minn[ls] <= minn[rs]){
        minp[d] = minp[ls];
        minn[d] = minn[ls];
    }else{
        minp[d] = minp[rs];
        minn[d] = minn[rs];
    }
    return ;
}
void build(int1 d,int1 l,int1 r){//建树，初始化最大值/最小值出现的位置
    if(l == r){
        maxp[d] = minp[d] = l;
        return ;
    }
    int1 mid = (l + r) >> 1;
    build(ls,l,mid);
    build(rs,mid + 1,r);
    push_up(d);
    return ;
}
void f(int1 d,int1 k){//修改节点
    maxn[d] += k,minn[d] += k,tag[d] += k;
    return ;
}
void push_down(int1 d){//标记下传
    if(tag[d]){
        f(ls,tag[d]);
        f(rs,tag[d]);
        tag[d] = 0;
    }
    return ;
}
void change(int1 d,int1 l,int1 r,int1 x,int1 y,int1 k){//区间修改
    if(x <= l && r <= y){
        f(d,k);
        return ;
    }
    push_down(d);
    int1 mid = (l + r) >> 1;
    if(x <= mid){
        change(ls,l,mid,x,y,k);
    }
    if(y > mid){
        change(rs,mid + 1,r,x,y,k);
    }
    push_up(d);
    return ;
}
void comp(int1 s,int1 x,int1 y){
    if(s > ans){
        ans = s,ansx = x,ansy = y;
    }
    return ;
}
int main(){
    n = read(),m = read(),W = read(),H = read();
    for(i = 1; i <= n; i++){
        int1 xx = read(),yy = read(),xxx = xx + W;//读入红点
        lth[0]++;
        l[i] = xx,r[i] = xxx,y[i] = yy,v[i] = 1;//并预处理点可以贡献到的位置（区间）
        lsh[0][lth[0]] = xx;
        lth[1]++;
        lsh[1][lth[1]] = yy;
        lth[0]++;
        lsh[0][lth[0]] = xxx;
        lth[1]++;
        lsh[1][lth[1]] = yy + H;//记录矩形上下边可能出现的位置
        lth[1]++;
        lsh[1][lth[1]] = yy - H;//同上
    }
    nm = n + m;
    for(i = n + 1; i <= nm; i++){//对蓝点的处理基本一样，只是贡献从1变成了-1
        int1 xx = read(),yy = read(),xxx = xx + W;
        lth[0]++;
        l[i] = xx,r[i] = xxx,y[i] = yy,v[i] = -1;
        lsh[0][lth[0]] = xx;
        lth[1]++;
        lsh[1][lth[1]] = yy;
        lth[0]++;
        lsh[0][lth[0]] = xxx;
        lth[1]++;
        lsh[1][lth[1]] = yy + H;
        lth[1]++;
        lsh[1][lth[1]] = yy - H;
    }
    sort(lsh[0] + 1,lsh[0] + lth[0] + 1);
    lth[0] = unique(lsh[0] + 1,lsh[0] + lth[0] + 1) - lsh[0];//离散化横坐标
    sort(lsh[1] + 1,lsh[1] + lth[1] + 1);
    lth[1] = unique(lsh[1] + 1,lsh[1] + lth[1] + 1) - lsh[1];//离散化纵坐标
    for(i = 1; i <= nm; i++){
        l[i] = lower_bound(lsh[0] + 1,lsh[0] + lth[0] + 1,l[i]) - lsh[0];
        r[i] = lower_bound(lsh[0] + 1,lsh[0] + lth[0] + 1,r[i]) - lsh[0];
        y[i] = lower_bound(lsh[1] + 1,lsh[1] + lth[1] + 1,y[i]) - lsh[1];
        aty[y[i]].push_back(i);//将纵坐标为y[i]的点存储起来，方便加点/删点
        siz[y[i]]++;//这里手动记录了一下aty[y[i]].size()
    }
    build(1,1,lth[0]);//建树
    for(int1 L = 1,R = 0; L <= lth[1]; ){//枚举下线离散化后的位置
        int1 limit = lsh[1][L] + H;//确定“上线”的“上限”（（（
        while(lsh[1][R + 1] <= limit && R < lth[1]){
            R++;//移动上线
            for(i = 0; i < siz[R]; i++){//同时加点
                int1 pos = aty[R][i];
                change(1,1,lth[0],l[pos],r[pos],v[pos]);
            }
        }
        if(L <= R){//如果上下线位置合法
            comp(abs(maxn[1]),lsh[0][maxp[1]],lsh[1][L]);//更新答案（注意记得把坐标离散回去）
            comp(abs(minn[1]),lsh[0][minp[1]],lsh[1][L]);           
        }
        for(i = 0; i < siz[L]; i++){//删点
            int1 pos = aty[L][i];
            change(1,1,lth[0],l[pos],r[pos],-v[pos]);
        }
        L++;//移动下线
    }
    pe(ans);
    ps(ansx - W),pe(ansy);//得到的点是右下角的，所以横坐标-W
    return 0;
}

两条线只会把每个点各遍历一遍，所以时间复杂度为 O((n + m)\log (n + m))。