Pre
我不服我不服我就不服。
调了两天，最后发现是因为题目上面
(x=(x+lastans-1)\%mod+1)
括号里面的(-1)我没有加入代码。
我的眼镜估计要换了。
Solution
李超线段树模板题目。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5, M = 39989 + 10, mod1 = 39989, mod2 = 1e9;
struct Node {
int xl, xr, id;
double yl, yr;
Node (int x1 = 0, int x2 = 0, int i = 0, double y1 = 0, double y2 = 0) {
xl = x1, xr = x2, yl = y1, yr = y2, id = i;
if (xl == xr) yl = yr = max (yl, yr);
}
inline double k () {return (yr - yl) / (xr - xl);}
inline double f (int x) {return xl == xr ? yl : k () * (x - xl) + yl;}
}id[N << 1];
int tot, l[N << 1], r[N << 1], ch[N << 1][2], lastans, cnt;
bool eql (double x, double y) {return fabs(x - y) < 1e-8;}
bool hei (Node a, Node b, int x) {return eql(a.f (x), b.f (x)) ? a.id < b.id : a.f (x) > b.f (x);}
inline int build (int u, int v) {
int now = ++tot;
l[tot] = u, r[tot] = v;
if (u == v) {return now;}
int mid = (u + v) / 2;
ch[now][0] = build (u, mid);
ch[now][1] = build (mid + 1, v);
return now;
}
inline void update (int p, Node a) {
if (a.xl < l[p]) {a.yl = a.f(l[p]); a.xl = l[p];}
if (a.xr > r[p]) {a.yr = a.f(r[p]); a.xr = r[p];}
int mid = (l[p] + r[p]) / 2;
if (a.f(mid) > id[p].f(mid) || (eql(a.f(mid), id[p].f(mid)) && a.id < id[p].id)) swap (a, id[p]);
if (min (id[p].yl, id[p].yr) >= max (a.yl, a.yr)) return ;
if (l[p] == r[p]) return ;
if (a.k() >= id[p].k()) update (ch[p][1], a);
else update (ch[p][0], a);
}
inline void insert (int p, Node a) {
if (a.xl > r[p] || a.xr < l[p]) return ;
if (a.xl < l[p]) {a.yl = a.f(l[p]); a.xl = l[p];}
if (a.xr > r[p]) {a.yr = a.f(r[p]); a.xr = r[p];}
if (eql(a.xl, l[p]) && eql(a.xr, r[p])) {update (p, a); return ;}
if (l[p] == r[p]) return ;
insert (ch[p][0], a), insert (ch[p][1], a);
}
inline void query (int p, int k, int&la, double&nw) {
if ((la == 0 || id[p].f(k) > nw) || (eql(id[p].f(k), nw) && id[p].id < id[la].id)) {la = p; nw = id[p].f(k);}
if (l[p] == r[p]) return ;
int mid = (l[p] + r[p]) / 2;
if (k <= mid) query (ch[p][0], k, la, nw);
else query (ch[p][1], k, la, nw);
}
int main () {
int t;
scanf ("%d", &t);
build (1, mod1);
for (int z = 1; z <= t; ++z) {
int opt;
scanf ("%d", &opt);
if (!opt) {
int k;
double xx = 0;
scanf ("%d", &k);
k = (k + lastans - 1) % mod1 + 1;
lastans = 0;
query (1, k, lastans, xx);
lastans = id[lastans].id;
printf ("%d
", lastans);
}
else {
++cnt;
int x0, y0, x1, y1;
scanf ("%d%d%d%d", &x0, &y0, &x1, &y1);
x0 = (x0 + lastans - 1) % mod1 + 1;
x1 = (x1 + lastans - 1) % mod1 + 1;
y0 = (y0 + lastans - 1) % mod2 + 1;
y1 = (y1 + lastans - 1) % mod2 + 1;
if (x0 > x1) {swap (x0, x1), swap (y0, y1);}
insert (1, (Node) {x0, x1, cnt, (double) y0, (double) y1});
}
}
return 0;
}
Conclusion
认真看题。。。