2023牛客暑期多校训练营5 E Red and Blue and Green

题目大意：构造一个长度为$nn$的排列，使得满足$mm$个约束条件： 区间逆序对个数是奇数或偶数。满足这些约束条 件的区间包含或不相交.$(1\le n,m\le 10^3)(1\backslash le\; n,m\backslash le\; 10^3)$ 分析：关注其保证区间不相交，即：

所有的区间不相交或包含意味着这些区间可以构成一个树形结构。将区间视为一个点，可发现区间构成了一棵树。不妨建立一个$00$号区间作为根节点,范围$11$至$nn$（即包含所有的区间),接下来，为了使代码更为简洁，可以建立$nn$个长度为$11$的叶节点，再进行 $DFSDFS$：

由于小区间的改变更为灵活，我们的换数字可从小区间开始(起始排列为$11$至$nn$)

---1.区间长度小于$22$：由于我们建立了$nn$个长度为$11$的叶节点，对于这种情况其实本不需操作，但输入中可能存在长度为$11$的区间且逆序数对为奇数，此时无法构造序列，应输出$-1-1$
---2.区间长度大于等于$22$且不为$00$号区间($00$号区间无需操作): 由于建立了$nn$个长度为$11$的叶节点，因此区间长度大于等于$22$的节点必然是父节点(儿子数量大于等于$22$)，父节点的逆序数对的数量由儿子决定，经过手动操作发现，
--------------------------$1.1.$若所有子节点的奇偶和等于父节点的奇偶和，则无需操作
--------------------------$2.2.$若所有子节点的奇偶和不等于父节点的奇偶和，可以发现更改第一孩子区间的最大值与第二孩子区间的最小值即可满足题意 -----$ps:\mathrm{因}\mathrm{为}\mathrm{父}\mathrm{亲}\mathrm{区}\mathrm{间}\mathrm{必}\mathrm{然}\mathrm{有}\mathrm{两}\mathrm{个}\mathrm{孩}\mathrm{子}\mathrm{区}\mathrm{间}\mathrm{，}\mathrm{因}\mathrm{此}\mathrm{用}1\mathrm{号}\mathrm{和}2\mathrm{号}\mathrm{代}\mathrm{码}\mathrm{更}\mathrm{简}\mathrm{洁}ps:因为父亲区间必然有两个孩子区间，因此用1号和2号代码更简洁$
$\mathrm{如}如$: $1\mathrm{，}2\mathrm{，}3\mathrm{，}5\mathrm{，}41，2，3，5，4$与$6\mathrm{，}7\mathrm{，}9\mathrm{，}86，7，9，8$ 合并，目的逆序数对为奇数个,可交换$5\mathrm{，}65，6$，使满足题意

参考代码

 
using namespace std;
const int M=1e3+7;
struct Tree{
    int l,r,w;
}t[2*M];
int n,m,flag=0;
int fa[2*M],p[M],pos[M];
vector<int> g[2*M];
bool Cmp(Tree p,Tree q){
    if(p.l!=q.l) return p.l<q.l;
    return p.r>q.r;
}
 
 
void DFS(int u){
    int v,sum=0;
    for(int i=0;i<g[u].size();i++){
        v=g[u][i];
        DFS(v);
        sum+=t[v].w;
    }
    if((sum&1)!=t[u].w&&u){
        int p1=pos[t[g[u][0]].r];
        int p2=pos[t[g[u][1]].l];
        swap(p[p1],p[p2]);
        swap(pos[t[g[u][0]].r],pos[t[g[u][1]].l]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        cnt++;
        cin>>t[cnt].l>>t[cnt].r>>t[cnt].w;
        if(t[cnt].l==t[cnt].r&&t[cnt].w==1)flag=1;
        if(t[cnt].l==t[cnt].r) cnt--;
    }
    if(flag){
        cout<<"-1"<<"\n";
        return 0;
    }
    for(int i=1;i<=n;i++) {
        pos[i]=p[i]=i;
        t[++cnt].l=i; t[cnt].r=i; t[cnt].w=0;
    }
    fa[0]=0; t[0].l=1; t[0].r=n; t[0].w=0;
    sort(t+1,t+1+cnt,Cmp);
    for(int i=0;i<cnt;i++){
        if(t[i].l<=t[i+1].l&&t[i+1].r<=t[i].r){
            g[i].push_back(i+1);
            fa[i+1]=i;
        } else{
            int now;
            now=i;
            while(t[now].r<t[i+1].l){
                now=fa[now];
            }
            g[now].push_back(i+1);
            fa[i+1]=now;
        }
    }
    DFS(0);
    for(int i=1;i<=n;i++){
        cout<<p[i]<<" ";
    }
    cout<<"\n";
}