首页 > 代码库 > BZOJ 3165 Segment
BZOJ 3165 Segment
同上题。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 40000 using namespace std; long long n,m,type,a,b,c,d,root,tot=0,ls[maxn<<2],rs[maxn<<2],cnt=0; bool flag[maxn<<2]; long long ans,lastans=0; double mx=0; struct seg { long long x1,y1,x2,y2,id; seg (long long x1,long long y1,long long x2,long long y2,long long id):x1(x1),y1(y1),x2(x2),y2(y2),id(id) {} seg () {} }s[maxn<<2]; void build(long long &now,long long left,long long right) { now=++tot; if (left==right) return; long long mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } double f(seg x,long long pos) { double k=(double)(x.y1-x.y2)/(x.x1-x.x2),b=(double)(x.x1*x.y2-x.x2*x.y1)/(x.x1-x.x2); return k*pos+b; } void ask(long long now,long long left,long long right,long long pos) { if ((mx<f(s[now],pos)) && (flag[now])) {mx=f(s[now],pos);ans=s[now].id;} if (left==right) return; long long mid=(left+right)>>1; if (pos<=mid) ask(ls[now],left,mid,pos); else ask(rs[now],mid+1,right,pos); } void pushdown(long long now,long long left,long long right,seg x) { long long mid=(left+right)>>1; if (!flag[now]) {flag[now]=true;s[now]=x;return;} double r1=f(x,mid),r2=f(s[now],mid); if (left==right) {if (r1>r2) swap(x,s[now]);return;} double f1=f(x,left),f2=f(s[now],left),f3=f(x,right),f4=f(s[now],right); if ((f1<f2) && (f3<f4)) return; if ((f1>f2) && (f3>f4)) {swap(x,s[now]);return;} if (r1>r2) swap(x,s[now]); if ((f1>f2)^(r1>r2)) pushdown(ls[now],left,mid,x); else pushdown(rs[now],mid+1,right,x); } void modify(long long now,long long left,long long right,long long l,long long r,seg x) { if ((left==l) && (right==r)) { pushdown(now,left,right,x); return; } long long mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,x); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,x); else { modify(ls[now],left,mid,l,mid,x); modify(rs[now],mid+1,right,mid+1,r,x); } } int main() { scanf("%lld",&m);n=39989; build(root,1,n); for (long long i=1;i<=m;i++) { scanf("%lld",&type); if (type==0) { scanf("%lld",&a);a=(a+lastans-1)%39989+1; mx=0;ans=0;ask(root,1,n,a); lastans=ans;printf("%lld\n",lastans); } else { cnt++; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); a=(a+lastans-1)%39989+1;b=(b+lastans-1)%1000000000+1; c=(c+lastans-1)%39989+1;d=(d+lastans-1)%1000000000+1; if (a>c) {swap(a,c);swap(b,d);} modify(root,1,n,a,c,seg(a,b,c,d,cnt)); } } return 0; }
BZOJ 3165 Segment
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。