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]);
}