RT
感觉会模板就差不多了，可用作处理一些线段或直线的问题，转化过来的也可以。比如DP的斜率优化，直线的话只用一个log,线段要两个log。
[HEOI2013] Segment
- 模板
#include<iostream>
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const double esp=1e-9;
const int N=1e5;
typedef pair<double,int> pi;
int n,s[N<<2],cnt;
struct line{
double k,b;
}li[N];
int cmp(double x,double y){
if(x-y>esp) return 1;
if(y-x>esp) return -1;
return 0;
}
double calc(int id,int d){
return li[id].k*d+li[id].b;
}
void add(int xi,int yi,int xj,int yj){
cnt++;
if(xi==xj)
li[cnt].b=max(yi,yj),li[cnt].k=0;
else
li[cnt].k=1.0*(yj-yi)/(xj-xi),li[cnt].b=yi-li[cnt].k*xi;
}
void upd(int p,int cl,int cr,int u){
int &v=s[p],mid=cl+cr>>1;
if(cmp(calc(u,mid),calc(v,mid))==1) swap(u,v);
int l=cmp(calc(u,cl),calc(v,cl)),r=cmp(calc(u,cr),calc(v,cr));
if(l==1||(!l&&u<v)) upd(p<<1,cl,mid,u);
if(r==1||(!r&&u<v)) upd(p<<1|1,mid+1,cr,u);
}
void update(int l,int r,int u,int p=1,int cl=1,int cr=mod1){
if(l<=cl&&cr<=r){
upd(p,cl,cr,u);
return;
}
int mid=cl+cr>>1;
if(l<=mid) update(l,r,u,p<<1,cl,mid);
if(mid<r) update(l,r,u,p<<1|1,mid+1,cr);
}
pi pmax(pi x,pi y){
if(cmp(x.first,y.first)==1) return x;
if(cmp(x.first,y.first)==-1) return y;
return x.second<y.second?x:y;
}
pi query(int d,int p=1,int cl=1,int cr=mod1){
if(cl>d||cr<d) return {0,0};
double res=calc(s[p],d),mid=cl+cr>>1;
if(cl==cr) return {res,s[p]};
return pmax({res,s[p]},pmax(query(d,p<<1,cl,mid),query(d,p<<1|1,mid+1,cr)));
}
int main(){
int xi,xj,yi,yj,d,op,laas=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%d%d",&xi,&yi,&xj,&yj);
xi=(xi+laas-1+mod1)%mod1+1;
xj=(xj+laas-1+mod1)%mod1+1;
yi=(yi+laas-1+mod2)%mod2+1;
yj=(yj+laas-1+mod2)%mod2+1;
if(xi>xj) swap(xi,xj),swap(yi,yj);
add(xi,yi,xj,yj);
update(xi,xj,cnt);
}
else{
scanf("%d",&d);
d=(d+laas-1+mod1)%mod1+1;
laas=query(d).second;
printf("%d\n",laas);
}
}
}