记一下模板的写法。。。

做法一：李超树
https://github.com/lychees/ACM-Training/tree/master/Archive/BZOJ/3165.%20%5BHeoi2013%5DSegment

做法二：线段树套平衡树

因为李超树的大流行，树套树反而没人再去写了。。。

const int N = int(1e5) + 9;

#define ll double
struct Line {
	mutable ll k, b, p; int id;
	Line (ll k = 0, ll b = 0, int id = 0):k(k),b(b),id(id) {
	    p = 0;
	}
	ll y(ll x) const {return k*x + b;}
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line,less<>> {
	const ll inf = 1/.0;
	ll div(ll a, ll b) {
		return a / b;
    }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->b > y->b ? inf : -inf;
		else x->p = div(y->b - x->b, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll b, int i) {
		add(Line(k,b,i));
	}
	void add(Line t) {
		auto z = insert(t), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}

	pair<ll, int> query(ll x) {
		assert(!empty());
		auto& l = *lower_bound(x);
		return {l.y(x), l.id};
	}
} H;
map<int, pair<ll,int> > M;


namespace Segtree {
    const int NN = 4 * N;
    LineContainer T[NN];
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
#define rt 1,1,39989
    void Insert(int x, int l, int r, int a, int b, Line L) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            T[x].add(L);
        } else {
            Insert(lc, a, b, L);
            Insert(rc, a, b, L);
        }
    }
    void Query(int x, int l, int r, int p, vector<LineContainer*>& L) {
        if (p < l || r < p) return;
        if (l <= p && p <= r) {
            if (!T[x].empty()) L.PB(&T[x]);
        }
        if (l != r) {
            Query(lc, p, L);
            Query(rc, p, L);
        }
    }
}

vector<LineContainer*> L;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif

    int id = 0; Rush {
        LL x0, y0, x1, y1;
        if (RD()) {
            RD(x0, y0, x1, y1);
            x0 = (x0 + last_ans - 1) % 39989 + 1;
            x1 = (x1 + last_ans - 1) % 39989 + 1;
            y0 = (y0 + last_ans - 1) % int(1e9) + 1;
            y1 = (y1 + last_ans - 1) % int(1e9) + 1;
            if (x0 > x1) {
                swap(x0, x1);
                swap(y0, y1);
            }
            if (x0 == x1) {
                auto t = pair<ll, int>(max(y0, y1), ++id);
                if (CTN(M, x0))  {
                    M[x0] = t;
                } else {
                    checkMax(M[x0], t);
                }
            } else {
                DB k = (DB)(y1-y0)/(x1-x0);
                DB b = y0 - k*x0;
                Segtree::Insert(rt, x0, x1, Line(k, b, ++id));
            }
        } else {
            RD(x0);
            x0 = (x0 + last_ans - 1) % 39989 + 1;
            pair<ll, int> z = {-OO, 0}; L.clear(); Segtree::Query(rt, x0, L);
            for (auto& l: L) checkMax(z, l->query(x0));
            if (CTN(M, x0)) checkMax(z, M[x0]);
            OT(z.se);
        }
    }
}

Posted by xiaodao
Category: 日常