1568是3165的弱化版，发的代码是3165的
这道题完全没想出来，是看wyl大神的题解http://hi.baidu.com/wyl8899/item/2deafd3a376ef2d46d15e998
对我完全是一个思维上的突破，之前线段树打的标记基本都是代表整个区间的性质
而这道题区间上的标记只是部分优的线段，通过从叶子一步一步的走到根，得出这个点的最大值
const n=;
p=;
type node=record
k,b:double;
end; var tree:array[..*n] of longint;
a:array[..] of node;
ans,x0,x1,y0,y1,t,m,ch:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function cal(i,x:longint):double;
begin
exit(a[i].k*x+a[i].b);
end; procedure ins(i,l,r,k:longint);
var m:longint;
p:double;
begin
if tree[i]= then
begin
tree[i]:=k;
exit;
end;
if cal(k,l)>cal(tree[i],l) then swap(tree[i],k);
if (l=r) or (a[tree[i]].k=a[k].k) then exit;
p:=(a[tree[i]].b-a[k].b)/(a[k].k-a[tree[i]].k);
if (p<l) or (p>r) then exit;
m:=(l+r) shr ;
if (p<=m) then
begin
ins(i*,l,m,tree[i]);
tree[i]:=k;
end
else ins(i*+,m+,r,k);
end; procedure work(i,l,r:longint);
var m:longint;
begin
if (x0<=l) and (x1>=r) then
ins(i,l,r,t)
else begin
m:=(l+r) shr ;
if x0<=m then work(i*,l,m);
if m<x1 then work(i*+,m+,r);
end;
end; function ask(i,l,r:longint):longint;
var m,p:longint;
begin
if l=r then exit(tree[i])
else begin
m:=(l+r) shr ;
if x0<=m then p:=ask(i*,l,m)
else p:=ask(i*+,m+,r);
if cal(p,x0)>cal(tree[i],x0) then exit(p) else exit(tree[i]);
end;
end; begin
readln(m);
while m> do
begin
dec(m);
read(ch);
if ch= then
begin
readln(x0,y0,x1,y1);
x0:=(x0+ans-) mod n+;
x1:=(x1+ans-) mod n+;
y0:=(y0+ans-) mod p+;
y1:=(y1+ans-) mod p+;
if x0>x1 then
begin
swap(x0,x1);
swap(y0,y1);
end;
inc(t);
if x0<>x1 then
begin
a[t].k:=(y1-y0)/(x1-x0);
a[t].b:=y1-a[t].k*x1;
end
else begin
if y1>y0 then a[t].b:=y1 else a[t].b:=y0;
end;
work(,,n);
end
else begin
readln(x0);
x0:=(x0+ans-) mod n+;
ans:=ask(,,n);
writeln(ans);
end;
end;
end.