洛谷 P4125 [WC2012]记忆中的水杉树【扫描线+set+线段树】

洛谷 P4125 [WC2012]记忆中的水杉树【扫描线+set+线段树】

我没有找到能在bzojAC的代码……当然我也WA了……但是我在洛谷过了，那就假装过了吧
minmax线段树一开始写的只能用min更新min，max更新max，实际上是可以互相更新的……
首先看第二问，注意到因为没有相交，所以可以全都按某种顺序像同一个方向移动来完成游戏，这个顺序通过扫描线找到，用set维护经过当前x坐标的的线段的y坐标，具体用y=kx+b的形式维护，因为不相交，所以随着x的变化，线段的y点的大小关系不会改变；每次插入一个点的时候，找一下它的前驱后继，分别连边（这里的前驱后继就相当于向上和向下第一个撞上的线段），然后得到一张有向图，拓扑序就是游戏的操作顺序
然后看第一问，对横向和纵向都做一遍拓扑，记录点在拓扑序中的出现的时间，然后用两个线段树分别维护对于横向/纵向点的出现时间的最大最小值，然后倒着做，每次查询线段树里就相当于查询游戏中剩下的线段的出现时间，判一下合法即可

#include<iostream>
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=300005;
int n,p[N],q[N],d[N],r[2][N],hs[2][N],ht[2][N],c[N],wi,h[N],cnt,tp[N],ans;
struct dian
{int x,y;
}a[N],b[N];
struct bian
{int ne,to;
}e[N<<1];
struct xds
{int l,r,mn,mx,lmn,lmx;void add(int v){if(v<mn) mn=v;if(v>mx) mx=v;if(v<lmn) lmn=v;if(v>lmx) lmx=v;}
};
struct qwe
{int x,id,f;double k,b;qwe(int X=0,int ID=0,int F=0,double K=0,double B=0){x=X,id=ID,f=F,k=K,b=B;}bool operator < (const qwe &z) const{return k*wi+b<z.k*wi+z.b;}bool operator == (const qwe &z) const{return id==z.id;}
}f[N<<1];
bool cmp(const qwe &a,const qwe &b)
{return a.x&(a.x==b.x&&a.f>b.f);
}
int read()
{int r=0,f=1;char p=getchar();while(p>'9'||p<'0'){if(p=='-')f=-1;p=getchar();}while(p>='0'&&p<='9'){r=r*10+p-48;p=getchar();}return r*f;
}
void add(int u,int v)
{//cerr<<u<<"  "<<v<<endl;cnt++;e[cnt].ne=h[u];e[cnt].to=v;h[u]=cnt;d[v]++;
}
void wk(int hs[],int ht[],int r[])
{int tot=0,has=0;for(int i=1;i<=n;i++)c[++tot]=a[i].x+1,c[++tot]=b[i].x;sort(c+1,c+1+tot);for(int i=1;i<=tot;i++)if(i==1||c[i]!=c[i-1])c[++has]=c[i];tot=0;for(int i=1;i<=n;i++){hs[i]=lower_bound(c+1,c+1+has,a[i].x+1)-c,ht[i]=lower_bound(c+1,c+1+has,b[i].x)-c;f[++tot]=qwe(hs[i],i,1,(double)(b[i].y-a[i].y)/(double)(b[i].x-a[i].x),a[i].y-a[i].x*(double)(b[i].y-a[i].y)/(double)(b[i].x-a[i].x));f[++tot]=qwe(ht[i],i,-1,(double)(b[i].y-a[i].y)/(double)(b[i].x-a[i].x),a[i].y-a[i].x*(double)(b[i].y-a[i].y)/(double)(b[i].x-a[i].x));}sort(f+1,f+1+tot,cmp);memset(d,0,sizeof(d));memset(h,0,sizeof(h));cnt=0;set<qwe>s;set<qwe>::iterator it;for(int i=1,w=1;i<=has;i++){wi=c[i];while(w<=tot&&f[w].x==i){if(f[w].f==1){it=s.lower_bound(f[w]);if(it!&#d())add(f[w].id,it->id);if(it!=s.begin())add((--it)->id,f[w].id);s.insert(f[w]);}ase(f[w]);w++;}}tot=0;queue<int>q;for(int i=1;i<=n;i++)if(!d[i])q.push(i);while(!q.empty()){int u=q.front();r[u]=++tot;q.pop();for(int i=h[u];i;i=e[i].ne)if(!(--d[e[i].to]))q.push(e[i].to);}
}
struct clc
{xds t[N<<2];void build(int ro,int l,int r){t[ro].l=l,t[ro].r=r,t[ro].mx=t[ro].lmx=-1e9,t[ro].mn=t[ro].lmn=1e9;if(l==r)return;int mid=(l+r)>>1;build(ro<<1,l,mid);build(ro<<1|1,mid+1,r);}void pd(int ro){if(t[ro].lmx!=-1e9){t[ro<<1].add(t[ro].lmx);t[ro<<1|1].add(t[ro].lmx);t[ro].lmx=-1e9;}if(t[ro].lmn!=1e9){t[ro<<1].add(t[ro].lmn);t[ro<<1|1].add(t[ro].lmn);t[ro].lmn=1e9;}}void update(int ro,int l,int r,int v){if(t[ro].l==l&&t[ro].r==r){t[ro].add(v);return;}pd(ro);int mid=(t[ro].l+t[ro].r)>>1;if(r<=mid)update(ro<<1,l,r,v);else if(l>mid)update(ro<<1|1,l,r,v);elseupdate(ro<<1,l,mid,v),update(ro<<1|1,mid+1,r,v);t[ro].mn=min(t[ro<<1].mn,t[ro<<1|1].mn);t[ro].mx=max(t[ro<<1].mx,t[ro<<1|1].mx);}pair<int,int>ques(int ro,int l,int r){if(t[ro].l==l&&t[ro].r==r)return make_pair(t[ro].mn,t[ro].mx);pd(ro);int mid=(t[ro].l+t[ro].r)>>1;if(r<=mid)return ques(ro<<1,l,r);else if(l>mid)return ques(ro<<1|1,l,r);else{pair<int,int>x=ques(ro<<1,l,mid),y=ques(ro<<1|1,mid+1,r);return make_pair(min(x.first,y.first),max(x.second,y.second));}}
}t0,t1;
int main()
{n=read();for(int i=1;i<=n;i++){a[i].x=read(),a[i].y=read(),b[i].x=read(),b[i].y=read();if(a[i].x>b[i].x)swap(a[i],b[i]);}wk(hs[0],ht[0],r[0]);//cerr<<"OK"<<endl;for(int i=1;i<=n;i++){swap(a[i].x,a[i].y),swap(b[i].x,b[i].y);if(a[i].x>b[i].x)swap(a[i],b[i]);}wk(hs[1],ht[1],r[1]);// for(int i=1;i<=n;i++)// cerr<<r[0][i]<<" ";cerr<<endl;// for(int i=1;i<=n;i++)// cerr<<r[1][i]<<" ";cerr<<endl;t0.build(1,1,2*n);t1.build(1,1,2*n);for(int i=1;i<=n;i++)p[i]=read(),q[i]=read();for(int i=n;i>=1;i--){if(q[i]==1||q[i]==3){pair<int,int>nw=t0.ques(1,hs[0][p[i]],ht[0][p[i]]);if((q[i]==1&&nw.second>r[0][p[i]])||(q[i]==3&&nw.first<r[0][p[i]]))ans=i;}else{pair<int,int>nw=t1.ques(1,hs[1][p[i]],ht[1][p[i]]);//cerr<<nw.first<<"    "<<nw.second<<endl;if((q[i]==2&&nw.second>r[1][p[i]])||(q[i]==0&&nw.first<r[1][p[i]]))ans=i;}t0.update(1,hs[0][p[i]],ht[0][p[i]],r[0][p[i]]);t1.update(1,hs[1][p[i]],ht[1][p[i]],r[1][p[i]]);}printf("%dn",ans);for(int i=1;i<=n;i++)tp[r[0][i]]=i;for(int i=1;i<=n;i++)printf("%d 3n",tp[i]);return 0;
}

转载于:.html