P4097 【模板】李超线段树 题解

CNS_5t0_0r2 · 2024-02-03 20:01:04 · 题解

update on 2024-7-8：修正一处错误。

众所周知，线段树是维护区间的，但是这里的线段不能直接用区间维护，所以我们首先转换一下题意：（这部分是我学了 OI-wiki 上的）

• 加入一个一次函数，定义域为 [l,r]；
• 给定 k，求定义域包含 k 的所有一次函数中，在 x = k 处取值最大的那个，如果有多个函数取值相同，选编号最小的。

特别的，当一个线段不存在斜率时可以转换成斜率为 0，截距为 \max(y_0,y_1) 的直线（由题意这种情况交点取最顶部的顶点）。

这样，我们就将其转化为一个区间修改，单点查询的问题。

依照传统线段树的思路，我们还是通过分治和懒标记进行区间修改。

但是在一个区间内是没有最优线段的，只有在取一个特定的 x 时才有。所以，我们考虑每个节点维护包含对应区间所有直线在 横坐标 x 取一个一个特殊点时的最优线段。

不难想到这个特殊点为该区间的中点。

所以每个结点的懒标记维护的是横坐标 x 取该区间中点时的最优线段（但是这个懒标记无法保证任何时候都是在中点处最优的线段，原因讲到查询时会解释）。

在传统线段树中，区间修改（带懒标记应该是这样的）：

//[l,r]表示当前区间，[L,R]表示修改的区间
void update(int root,int l,int r,int L,int R,int id){
    if(out_range(l,r,L,R))//完全不在[L,R]内直接返回
        return;
    if(in_range(l,r,L,R)){//完全包含在[L,R]内更新懒标记
        make_tag(root,l,r,id);
        return;
    }
    //分别进入两子区间
    update(lchild,l,mid,L,R,id);
    update(rchild,mid + 1,r,L,R,id);
}

但是我们发现，在本题中，由懒标记的定义，当该线段的一部分（[l,r]）完全包含在修改区间 [L,R] 中时，不仅维护 [l,r] 区间结点的懒标记会发生变化，其子节点也会发生变化，所以我们还得把懒标记下传。

对于该区间，如果在中点处取值当前修改线段与该结点维护的最优线段更优，直接拿当前线段替换，并把当前线段替换成在中点处不优的线段。

然后，我们分别比较两线段在左端点 l 的取值和在右端点 r 的取值：

如果中点处不优的线段在左端点处的取值更优，那么递归到左子节点下传。

如果中点处不优的线段在右端点处的取值更优，那么递归到右子节点下传。

如果都不优，那么该线段在该区间及子区间将来无论如何都不可能最优线段，可以停止下传。

int CMP(double x,double y){//比较两浮点数 
    if(x - y > eps)
        return 1;
    if(y - x > eps)
        return -1;
    return 0;
}
bool cmp(int id1,int id2,int x){//比较线段id1在x处是否优于id2 ，用于提升代码可读性和降低编码复杂度
    int comp = CMP(calc(id1,x),calc(id2,x));
    return comp == 1 || (!comp && id1 < id2);//id1比id2在x处更优，当且仅当id1在x处的取值更优或x取值相等但id1编号更小
}
void push_down(int root,int l,int r,int id){
    if(cmp(id,t[root].id,mid))//如果当前线段比结点维护的线段更优，替换掉
        swap(id,t[root].id);
        //将不是更优的线段下传（因为此时 id 中点处不优，所以以下最多只有1个if成立）
    if(cmp(id,t[root].id,l))
        push_down(lchild,l,mid,id);
    if(cmp(id,t[root].id,r))
        push_down(rchild,mid + 1,r,id);
}

因为 push_down 函数两个 if 最多只有一个成立，所以 push_down 函数的复杂度为 O(\log V)（V 为 x 最大值）。同样的，update函数复杂度也是 O(\log V)（覆盖区间个数为 O(\log V)），每个覆盖区间又要一次 O(\log V) 的 push_down，所以修改部分的总复杂度为 O(\log^2 V)。

我们看到，查询部分显然是个单点查询问题，但真的只需要访问代表查询点的那个叶节点吗？

不是的。

上文提到，懒标记无法保证任何时候都是在中点处最优的线段，很容易构造出（去除强制在线的影响）：

1 7 2 9 2
1 2 2 10 10

我们令整个区间长度为 10。

在本例中，加入第 1 条使其在 x = 8 处最优。但是第二条线段在 x = 8 处显然更优，但由于第 1 条线段与与整个区间的中点无交，所以第 2 条线段不会继续下传，因此维护 [6,10] 区间节点（中点为 8）维护的“最优”还是线段 1。

所以，我们需要将所有包含 x = k 的区间对应的结点全部扫一遍，取所有结点懒标记的最优者。

在这里维护了一个 better 函数，因此这里的 query 返回值不需要用 pair。

int better(int id1,int id2,int x){//返回id1,id2在x处较优者 
    return cmp(id1,id2,x) ? id1 : id2;
}
int query(int root,int l,int r,int k){
    if(out_range(k,k,l,r))
        return 0;
    if(l == r)//递归边界
        return t[root].id;
    return better(t[root].id,better(query(lchild,l,mid,k),query(rchild,mid + 1,r,k),k),k);
}

复杂度为 O(\log V)。

AC code：

#include<iostream>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 9,MAXX = 39989,MAXY = 1e9;
const double eps = 1e-9;
struct line{//存线段的结构体
    double k,b;
} a[N];
int cnt;
void add_line(int x0,int y0,int x1,int y1){//加入一线段
    cnt++;
    if(x0 == x1){
        a[cnt].k = 0;
        a[cnt].b = max(y0,y1);
        return;
    }
    a[cnt].k = (double)(y1 - y0) / (double)(x1 - x0);
    a[cnt].b = (double)y0 - (double)(x0 * a[cnt].k);
}
double calc(int id,double x){//计算第i条直线在x处的值。 
    return a[id].k * x + a[id].b;
}
//1:x > y
//-1:x < y
//0:x = y
int CMP(double x,double y){//比较两浮点数 
    if(x - y > eps)
        return 1;
    if(y - x > eps)
        return -1;
    return 0;
}
bool cmp(int id1,int id2,int x){//比较线段id1在x处是否优于id2 ，用于提升代码可读性和降低编码复杂度
    int comp = CMP(calc(id1,x),calc(id2,x));
    return comp == 1 || (!comp && id1 < id2);
}
int better(int id1,int id2,int x){//返回id1,id2在x处较优者 
    return cmp(id1,id2,x) ? id1 : id2;
}
bool in_range(int l,int r,int L,int R){
    return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
    return l > R || r < L;
}
struct node{
    int id;//该节点维护区间最优线段编号 
} t[MAXX << 2];
void push_down(int root,int l,int r,int id){
    if(cmp(id,t[root].id,mid))//如果当前线段比结点维护的线段更优，替换掉
        swap(id,t[root].id);
        //将不是更优的线段下传（因为此时 id 中点处不优，所以以下最多只有1个if成立）
    if(cmp(id,t[root].id,l))
        push_down(lchild,l,mid,id);
    if(cmp(id,t[root].id,r))
        push_down(rchild,mid + 1,r,id);
}
void update(int root,int l,int r,int L,int R,int id){
    if(out_range(l,r,L,R))
        return;
    if(in_range(l,r,L,R)){
        push_down(root,l,r,id);
        return;
    }
    update(lchild,l,mid,L,R,id);
    update(rchild,mid + 1,r,L,R,id);
}
int query(int root,int l,int r,int k){
    if(out_range(k,k,l,r))
        return 0;
    if(l == r)
        return t[root].id;
    return better(t[root].id,better(query(lchild,l,mid,k),query(rchild,mid + 1,r,k),k),k);
}
int n,ans;
int main(){//主函数就不需要我解释了吧
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        int op;
        cin >> op;
        if(op == 0){
            int k;
            cin >> k;
            k = (k + ans - 1) % MAXX + 1;
            ans = query(1,1,MAXX,k);
            cout << ans << '\n';
        }
        if(op == 1){
            int x0,y0,x1,y1;
            cin >> x0 >> y0 >> x1 >> y1;
            x0 = (x0 + ans - 1) % MAXX + 1;
            x1 = (x1 + ans - 1) % MAXX + 1;
            y0 = (y0 + ans - 1) % MAXY + 1;
            y1 = (y1 + ans - 1) % MAXY + 1;
            if(x0 > x1){
                swap(x0,x1);
                swap(y0,y1);
            }
            //cout << x0 << ' ' << y0 << ' ' << x1 << ' ' << y1 << '\n';
            add_line(x0,y0,x1,y1);
            update(1,1,MAXX,x0,x1,cnt);
        }
    }
    return 0;
}