[CF 513D1] Constrained Tree

只有自己想到第一個子題的作法，第二個子題正在理解官方解當中@@
就打一下大概想法好了......實做好麻煩阿=ㄦ=

首先問題就是要求一個滿足那些限制的中序走訪的序列，然後因為一個子樹裡面的數字都會是連續的，在中序走訪的序列裡也是連續的，所以考慮以下子問題：現在可以用的數字為 L 到 R，正在作的區間是中序走訪序列的 st 到 ed ，構造滿足條件的二元樹。

因為這個子樹的根一定是 L ，所以把他叫 root 。然後看那些限制，如果有一個限制是 x 要被放在 root 的左邊，那麼值 <=x 的也要被放在root 的左邊，因為一顆子樹裡面的數值都是連續的。限制在 root 右邊同理。 而如果有一個限制說 b 要在 a 的左或右子樹的話，那他們就要被一起分到 root 的左邊或右邊，也就是 a ~ b 這一坨數字都要同在 root 左邊或右邊。所以只要找到適合的切點切下去就可以分治下去了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
struct P{int a,b,type;}p[100010],tmp[100010] ;
struct pii
{
    int x,y ;
    bool operator < (const pii &rhs) const
    {
        return x==rhs.x ? y<rhs.y : x<rhs.x ;
    }
};
 
int ans[maxn] ;
pii sta[maxn],seg[maxn] ;
 
bool solve(int L,int R,int st,int ed,int evl,int evr)
{
    if(st>ed) return 1 ;
    int root=L ;
    if(st==ed) { ans[st]=root ; return 1 ; }
 
    int le=L , ri=R+1 , num=0 ;
    for(int i=evl;i<=evr;i++)
    {
        if(p[i].b==root) return 0 ;
        if(p[i].a==root)
        {
            if(p[i].type==1) le=max(le,p[i].b) ;
            else ri=min(ri,p[i].b) ;
        }
        else seg[num++]=(pii){p[i].a,p[i].b} ;
    }
    if(le>=ri) return 0 ;
    if(!num)
    {
        ans[st+le-L]=root ;
        if(!solve(L+1,le,st,st+le-L-1,1,0)) return 0 ;
        if(!solve(le+1,R,st+le-L+1,ed,1,0)) return 0 ;
        return 1 ;
    }
    sort(seg,seg+num) ;
    int sz=0 ;
    for(int i=0;i<num;i++)
    {
        if(sz && sta[sz-1].y >= seg[i].y) continue ;
        if(sz && seg[i].x<=sta[sz-1].y) sta[sz-1].y=seg[i].y ;
        else sta[sz++]=seg[i] ;
    }
 
    int lid=0 ;
    while(lid<sz && sta[lid].x<=le) lid++ ;
    if(lid && sta[lid-1].y>=ri) return 0 ;
 
    int mid= lid ? sta[lid-1].y : le ;
    int evl2=evl , evr2=evr ;
    for(int i=evl;i<=evr;i++) if(p[i].a!=root)
    {
        if(p[i].a <= mid) tmp[evl2++]=p[i] ;
        else tmp[evr2--]=p[i] ;
    }
    for(int i=evl;i<=evr;i++) p[i]=tmp[i] ;
    ans[st+mid-L]=root ;
    if(!solve(L+1,mid,st,st+mid-L-1,evl,evl2-1)) return 0 ;
    if(!solve(mid+1,R,st+mid-L+1,ed,evr2+1,evr)) return 0 ;
 
    return 1 ;
}
 
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    bool no=0 ;
    for(int i=1;i<=m;i++)
    {
        char s[10] ; scanf("%d%d%s",&p[i].a,&p[i].b,s) ;
        if(s[0]=='L') p[i].type=1 ;
        else p[i].type=2 ;
        if(p[i].b<=p[i].a) no=1 ;
    }
 
    if(no || !solve(1,n,1,n,1,m)) printf("IMPOSSIBLE\n") ;
    else for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ') ;
}