李超线段树模板(class)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#ifdef ShadowDrunk
//李超线段树实际上是维护在二维坐标系上插入线段，同时查询x == d时y最大的线段是哪个以及对应的值的变式线段树
//我们发现一个线段可以看作作用域在[x0, x1]上的一次函数，我们维护函数即可
//我们给每个节点打上标记用于懒操作，每个标记都是一个完全覆盖当前区间的线段
//当我们插入一个线段时我们把它拆分到其包含的所有区间去考虑它的影响
//考虑当前插入线段对其覆盖区间的影响，将当前线段和之前标记线段在mid处更优秀的留做懒标记
//mid处更劣的线段看在两边是否和更优线段存在交点
//显然最多左边或右边，有且只有一边可能存在交点，我们把更劣的线段递归下传继续考虑
//在处理查询时我们类似于标记永久化的思想遍历包含的所有节点（包含路径中的节点），取所有节点标记的线段中最优的
//这是因为我们标记的线段一定是最优的或是最优的是其父亲节点中的标记，但还没有下传，我们遍历了所有路径节点，最优线段一定在其中

template<class T>
class LiSegTree
{
//李超线段树
//该模板维护的是线段对应k点最大的y归属于哪个序号最小的线段
//若需要修改成y最小需要修改用pmin以及改change内部的比较逻辑

//修改O(lgn * lgn), 查询O(lgn)
private :
    static constexpr double eps = 1e-9;
    static constexpr double inf = 1e18;

    int n;  //x轴值域[1, n]
    int m;  //插入的线段的最大数量

    
    int cmp(double x, double y){
        //返回x与y的大小关系，1则x大，0相等，-1则y大
        if(x - y > eps)
            return 1;
        if(y - x > eps)
            return -1;
        return 0;
    }

    struct line{
        //记录线段斜率和截距
        double k, b;
        line(double _k, double _b){
            k = _k; b = _b;
        }
        line(){
            k = 0; b = -inf;
            //b == inf; //维护y最小时
        }
    };

    std::vector<line> p;    //记录插入的线段
    int cnt = 0;    //内部线段的数量
    std::vector<int> tag; //记录区间标记属于哪个线段, 每个标记都是一个线段

    double calc(int id, T d){
        //计算id对应线段在x == d时的值
        return  p[id].b + p[id].k * d;
    }

    void add(T x0, T y0, T x1, T y1){
        //插入线段, (x0, y0), (x1, y1) 为线段两个端点
        cnt += 1;
        if(x0 == x1){
            p[cnt].k = 0;
            p[cnt].b = std::max(y0, y1);
        }
        else{
            p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0);
            p[cnt].b = y0 - p[cnt].k * x0;
        }
    }

    void change(int root, T pl, T pr, int u){
        //修改被完全覆盖的区间的标记
        int &v = tag[root];
        T mid = (pl + pr) >> 1;
        int bmid = cmp(calc(u, mid), calc(v, mid));
        if(bmid == 1 || (!bmid && u < v))
            std::swap(u, v);    //确保u线段在mid处小于等于v线段

        int bl = cmp(calc(u, pl), calc(v, pl));
        int br = cmp(calc(u, pr), calc(v, pr));
        //判断那边的区间存在交点
        if(bl == 1 || (!bl && u < v))
            change(root << 1, pl, mid, u);
        if(br == 1 || (!br && u < v))
            change((root << 1) | 1, mid + 1, pr, u);
        
        //上面两个if最多只会触发一个这保证了修改的复杂度
        /*
            //y最小代码
            if(bmid == -1 || (!bmid && u < v))
                std::swap(u, v);    //确保u线段在mid处大于等于v线段
            if(bl == -1 || (!bl && u < v))
                change(root << 1, pl, mid, u);
            if(br == -1 || (!br && u < v))
                change((root << 1) | 1, mid + 1, pr, u);
        */
    }

    void update(int root, T pl, T pr, T l, T r, int u){
        if(l <= pl && pr <= r){
            change(root, pl, pr, u);
            return;
        }
        T mid = (pl + pr) >> 1;
        if(l <= mid)
            update(root << 1, pl, mid, l, r, u);
        if(r > mid)
            update((root << 1) | 1, mid + 1, pr, l, r, u); 
    }

    std::pair<double, int> pmax(std::pair<double, int> x, std::pair<double, int> y){
        //ff for val, ss for id
        if(cmp(x.ff, y.ff) == -1)
            return y;
        else if(cmp(x.ff, y.ff) == 1)
            return x;
        else
            return (x.ss < y.ss ? x : y);
    }

    std::pair<double, int> pmin(std::pair<double, int> x, std::pair<double, int> y){
        //ff for val, ss for id
        if(cmp(x.ff, y.ff) == -1)
            return x;
        else if(cmp(x.ff, y.ff) == 1)
            return y;
        else
            return (x.ss < y.ss ? x : y);
    }

    std::pair<double, int> query(int root, T l, T r, T d){
        //查询x == d时的答案
        if(r < d || l > d)
            return {-inf, 0};  //维护y最小 return {inf, 0};
        T mid = (l + r) >> 1;
        double res = calc(tag[root], d);
        if(l == r)
            return {res, tag[root]};
        return pmax({res, tag[root]}, pmax(query(root << 1, l, mid, d),
        query((root << 1) | 1, mid + 1, r, d)));
        /*
            //维护y最小时使用
            return pmin({res, s[root]}, pmin(query(root << 1, l, mid, d),
            query((root << 1) | 1, mid + 1, r, d)));
        */
    }

public :

    void addline(T x0, T y0, T x1, T y1){
        if(x0 > x1){
            std::swap(x0, x1);
            std::swap(y0, y1);
        }
        add(x0, y0, x1, y1);
        update(1, 1, n, x0, x1, cnt);
    }

    std::pair<double, int> query(T d){
        return query(1, 1, n, d);
    }

    LiSegTree(int _n, int _m){
        n = _n, m = _m;
        cnt = 0;
        tag.assign(n << 2, 0);
        p.assign(m + 1, line());
    }

    LiSegTree(){
        n = 5e5, m = 5e5;
        cnt = 0;
        tag.assign(n << 2, 0);
        p.assign(m + 1, line());
    }
};

#endif