首页 > 代码库 > BZOJ 2584: [Wc2012]memory（扫描线+线段树）
BZOJ 2584: [Wc2012]memory（扫描线+线段树）
题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=2584
题意：给出平面n个线段，任意两个线段严格不相交，且每个线段不平行于坐标轴。移走所有线段。每次移走一个线段，移n次，移走时只能竖直向下、向上或水平向左向右移走。每次移动时不能与当前还有的其他线段相交（顶点与顶点相交允许）。要求解决两个问题：
（1）题目给出了一种移走的序列，但是这个序列是不合法的。找出这个序列中最早的不合法的移动是第几个；
（2）要求你给出一种合法的移动序列。
思路：首先，我们来解决第二个问题。我们发现，只向一个方向移动是可以找到一个解的，这其实是一个拓扑图，我们的目标就是确定这个拓扑关系。比如竖直向上移动。我们可以用扫描线+set维护的方法来解决。
对于第一个问题，我们可以把移走的过程倒着进行，变为添加的过程。假如我们找到了竖直向上移走的拓扑关系。那么对于一个移走时是向上的线段，添加时是从上向下添加的，只要当前已经添加的所有里面的线段在拓扑图上都不是当前要添加的线段的前驱，当前添加就是合法的。其他的添加类似。
因此，我们可以为拓扑图重新标号，然后用线段树维护区间最大最小值即可。
const int INF=1000000007;const int N=100005;int a[N][4],b[N][2];int n;int e[2][N][2],Max[2];vector<int> g[2][N];int mp[2][N];int c[N*2],cNum;int curX;struct node{ int id; double k,b; int x,flag; int operator<(const node &p) const { double xMin=k*curX+b; double pxMin=p.k*curX+p.b; return xMin>pxMin; } int operator==(const node &p) const { return id==p.id; }};node f[N*2];int fNum;int cmp(node a,node b){ if(a.x!=b.x) return a.x<b.x; return a.flag>b.flag;}set<node> S;int ind[N];void cal(int t){ cNum=0; for(int i=1;i<=n;i++) { c[++cNum]=a[i][0]+1; c[++cNum]=a[i][2]; } sort(c+1,c+cNum+1); cNum=unique(c+1,c+cNum+1)-(c+1); Max[t]=cNum; fNum=0; for(int i=1;i<=n;i++) { fNum++; f[fNum].id=i; f[fNum].k=1.0*(a[i][3]-a[i][1])/(a[i][2]-a[i][0]); f[fNum].b=a[i][1]-f[fNum].k*a[i][0]; f[fNum].x=lower_bound(c+1,c+cNum+1,a[i][0]+1)-c; f[fNum].flag=1; e[t][i][0]=f[fNum].x; fNum++; f[fNum].id=i; f[fNum].k=1.0*(a[i][3]-a[i][1])/(a[i][2]-a[i][0]); f[fNum].b=a[i][1]-f[fNum].k*a[i][0]; f[fNum].x=lower_bound(c+1,c+cNum+1,a[i][2])-c; f[fNum].flag=-1; e[t][i][1]=f[fNum].x; } sort(f+1,f+fNum+1,cmp); S.clear(); set<node>::iterator it; int cur=1; clr(ind,0); for(int i=1;i<=cNum;i++) { curX=c[i]; while(cur<=fNum&&f[cur].x==i) { if(1==f[cur].flag) { S.insert(f[cur]); it=S.find(f[cur]); if(it!=S.begin()) { it--; g[t][it->id].pb(f[cur].id); ind[f[cur].id]++; } it=S.find(f[cur]); it++; if(it!=S.end()) { g[t][f[cur].id].pb(it->id); ind[it->id]++; } } else S.erase(f[cur]); cur++; } } queue<int> Q; int curId=0; for(int i=1;i<=n;i++) { if(!ind[i]) Q.push(i),mp[t][i]=++curId; } while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<SZ(g[t][u]);i++) { int v=g[t][u][i]; if(0==--ind[v]) Q.push(v),mp[t][v]=++curId; } }}struct SegNode{ int L,R,Min,Max; int detMin,detMax; void add(int x) { if(x<Min) Min=x; if(x>Max) Max=x; if(x<detMin) detMin=x; if(x>detMax) detMax=x; }};struct SegTree{ SegNode A[N*8]; void build(int t,int L,int R) { A[t].L=L; A[t].R=R; A[t].Max=-INF; A[t].Min=INF; A[t].detMax=-INF; A[t].detMin=INF; if(L==R) return; int M=(L+R)>>1; build(t<<1,L,M); build(t<<1|1,M+1,R); } void pushDown(int t) { if(A[t].L==A[t].R) return; if(A[t].detMax!=-INF) { A[t<<1].add(A[t].detMax); A[t<<1|1].add(A[t].detMax); A[t].detMax=-INF; } if(A[t].detMin!=INF) { A[t<<1].add(A[t].detMin); A[t<<1|1].add(A[t].detMin); A[t].detMin=INF; } } void pushUp(int t) { A[t].Min=min(A[t<<1].Min,A[t<<1|1].Min); A[t].Max=max(A[t<<1].Max,A[t<<1|1].Max); } void add(int t,int L,int R,int x) { if(A[t].L==L&&A[t].R==R) { A[t].add(x); return; } pushDown(t); int M=(A[t].L+A[t].R)>>1; if(R<=M) add(t<<1,L,R,x); else if(L>M) add(t<<1|1,L,R,x); else { add(t<<1,L,M,x); add(t<<1|1,M+1,R,x); } pushUp(t); } pair<int,int> get(int t,int L,int R) { if(A[t].L==L&&A[t].R==R) return MP(A[t].Min,A[t].Max); pushDown(t); int M=(A[t].L+A[t].R)>>1; if(R<=M) return get(t<<1,L,R); if(L>M) return get(t<<1|1,L,R); pair<int,int> aa=get(t<<1,L,M); pair<int,int> bb=get(t<<1|1,M+1,R); if(bb.first<aa.first) aa.first=bb.first; if(bb.second>aa.second) aa.second=bb.second; return aa; }}A[2];int get(){ A[0].build(1,1,Max[0]); A[1].build(1,1,Max[1]); int ans=-1; for(int i=n;i>=1;i--) { int t=b[i][0]; int d=b[i][1]; if(0==d||2==d) { int L=e[1][t][0]; int R=e[1][t][1]; pair<int,int> p=A[1].get(1,L,R); if(0==d&&p.second>mp[1][t]||2==d&&p.first<mp[1][t]) ans=i; } else { int L=e[0][t][0]; int R=e[0][t][1]; pair<int,int> p=A[0].get(1,L,R); if(3==d&&p.second>mp[0][t]||1==d&&p.first<mp[0][t]) ans=i; } A[0].add(1,e[0][t][0],e[0][t][1],mp[0][t]); A[1].add(1,e[1][t][0],e[1][t][1],mp[1][t]); } return ans;}int h[N];int main(){ n=myInt(); for(int i=1;i<=n;i++) { a[i][0]=myInt(); a[i][1]=myInt(); a[i][2]=myInt(); a[i][3]=myInt(); } for(int i=1;i<=n;i++) { b[i][0]=myInt(); b[i][1]=myInt(); } for(int i=1;i<=n;i++) if(a[i][0]>a[i][2]) { swap(a[i][0],a[i][2]); swap(a[i][1],a[i][3]); } cal(0); for(int i=1;i<=n;i++) { swap(a[i][0],a[i][1]); swap(a[i][2],a[i][3]); } for(int i=1;i<=n;i++) if(a[i][0]>a[i][2]) { swap(a[i][0],a[i][2]); swap(a[i][1],a[i][3]); } cal(1); int ans=get(); printf("%d\n",ans); for(int i=1;i<=n;i++) h[mp[0][i]]=i; for(int i=1;i<=n;i++) printf("%d 1\n",h[i]);}
BZOJ 2584: [Wc2012]memory（扫描线+线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。