这玩意儿假啊！
大清早起来突然开始yy，线段树怎么区间加一个等差数列，然后支持区间取max。yy无果，咕咕咕
后来，点开了一道雅礼集训题，哇塞，真的有这种题哎，哇塞，是弱化版哎（只要支持单点取max就好了），但我还是不会做哎，凉凉凉。
进入正文，思想主要是每个区间用一个“暴露”最多的线段进行替代，其余的线段用一个数组记下来（因为是单点最值所以可以直接比较）。然后在加入线段的时候分类讨论一下：
1、新线段完全高于旧线段，那么把旧线段丢到数组里并覆盖。
2、新线段完全低于旧线段，那么直接无视。
3、新旧线段有交点，按交点分治下去。
时间复杂度：\(O(n log^2 n)\)
/* bzoj3165 */ #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int MOD1 = 39989; const int MOD2 = 1000000000; const int maxn = 100000 + 10; const int maxt = maxn << 2; const double eps = 1e-9; struct anode{ int xa, xb, ya, yb; double k, b; anode() {} anode(int _xa, int _ya, int _xb, int _yb):xa(_xa), ya(_ya), xb(_xb), yb(_yb) { if(xa == xb) { k = 0; b = 1.0 * max(ya,yb); } else { k = (double)(yb - ya) / (xb - xa); b = (double) ya - k * xa; } } inline double f(int x) { return (double)k * x + b; } }a[maxn]; inline int sgn(double x) { return (x > - eps) - (x < eps); } inline int cross(int x, int y) { return floor((double)(a[y].b - a[x].b) / (a[x].k - a[y].k)); } //sgt int n, t[maxt], pos[maxn], tot; inline void updata(int x, int id) { if(!pos[x]) pos[x] = id; else { int tmp = sgn(a[pos[x]].f(x) - a[id].f(x)); if(tmp < 0 || (tmp == 0 && pos[x] > id)) pos[x] = id; } } void ins(int u, int l, int r, int p, int q, int id) { int ls = u << 1, rs = u << 1 | 1; if(p <= l && r <= q) { // cout << u << ' ' << l << ' ' << r << endl; if(!t[u]) { t[u] = id; return; } int L = sgn(a[t[u]].f(l) - a[id].f(l)) < 0; int R = sgn(a[t[u]].f(r) - a[id].f(r)) < 0; if(L && R) t[u] = id; else if(!L && !R) { updata(l,id); updata(r,id); } else { int mid = (l + r) >> 1, tmp = cross(t[u],id); if(tmp <= mid && L) ins(ls,l,mid,p,q,id); if(tmp <= mid && R) { ins(ls,l,mid,p,q,t[u]); t[u] = id; } if(tmp > mid && L) { ins(rs,mid + 1,r,p,q,t[u]); t[u] = id; } if(tmp > mid && R) ins(rs,mid + 1,r,p,q,id); } return; } int mid = (l + r) >> 1; if(p > mid) ins(rs,mid + 1,r,p,q,id); else if(q < mid + 1) ins(ls,l,mid,p,q,id); else { ins(ls,l,mid,p,q,id); ins(rs,mid + 1,r,p,q,id); } } inline int merge(int x, int y, int k) { if(!x || !y) return x + y; int now = sgn(a[x].f(k) - a[y].f(k)), tmp = x; if(now < 0 || (now == 0 && x > y)) tmp = y; return tmp; } int query(int u, int l, int r, int p) { int tmp = t[u]; if(l == r) return t[u]; int mid = (l + r) >> 1; if(p <= mid) { tmp = merge(tmp,query(u << 1,l,mid,p),p); return tmp; } else { tmp = merge(tmp,query(u << 1 | 1,mid + 1,r,p),p); return tmp; } } int main() { // freopen("data.out","w",stdout); scanf("%d", &n); int lastans = 0; tot = 0; for(int i = 1;i <= n;i ++) { int op, k, xa, ya, xb, yb; scanf("%d", &op); // cout << op << ' '; if(op == 0) { scanf("%d", &k); k = (k + lastans - 1) % MOD1 + 1; // cout << k << endl; int tmp = query(1,1,MOD1,k); if(pos[k]) { int now = sgn(a[tmp].f(k) - a[pos[k]].f(k)); if(now < 0 || (now == 0 && pos[k] > tmp)) tmp = pos[k]; } lastans = tmp; printf("%d\n", lastans); } if(op == 1) { scanf("%d%d%d%d", &xa, &ya, &xb, &yb); xa = (xa + lastans - 1) % MOD1 + 1; xb = (xb + lastans - 1) % MOD1 + 1; ya = (ya + lastans - 1) % MOD2 + 1; yb = (yb + lastans - 1) % MOD2 + 1; // cout << xa << ' ' << xb << ' ' << ya << ' ' << yb << endl; if(xa > xb) swap(xa,xb), swap(ya,yb); a[++ tot] = anode(xa,ya,xb,yb); ins(1,1,MOD1,xa,xb,tot); } } return 0; }转载于:https://www.cnblogs.com/ezhjw/p/10029290.html
相关资源：JAVA上百实例源码以及开源项目