题解 | #E- Red and Blue and Green#

题目关题信息：

所有区间是包络的(指一个区间被另一个区间完全覆盖)或者不交的（因此可看成树形结构进行dfs）

相关知识

交换两邻的两个数会改一个区间逆序对数量的奇偶性;
非降序的排列的逆序对儿的数量个数为 $0$ ;

思路：

将区间化成树形结构每个叶子节点包含三个值 $l, r, k$ 左，右端点的值和当前区间的奇偶性;
在转化成树形结构时让每个区间只作为长度最小的能包络它的子区间，也就是说让每个区间最多只会被算作一次子节点（孙子节点可以被算作多次）;
一个区间可能没有其被子区间完全覆盖，但并不影响计算因为在子区间之间的点是升序的不会产生逆序对儿；

每个区间初始时放入的数为 $[l, r]$ ,且子区按左端点排序，这样能保证子区间之间不会产生逆序对儿；
有升序排序的情况下交换相邻两个子区间较小和 $r$ 和较大的 $l$ 只会产生 $l, r$ 一个逆序对儿。因此做这样一个交换可以在不改变子区间的逆序对儿的个数的奇偶性的情况下改变
每次在进行修改的时候优先在交换相邻两个区间的端点的值 $l - 1, l$ 的两个数，如果存在的话；
如果父区间的逆序对数量的奇偶性与所有子区间的逆序对数量的奇偶性的和不一样时进行修改

实现技巧：

$p o s_{i}$ 记录每个整数的位置
考虑到加上一个偶数并不影响一个数的奇偶性，加上一个奇数会使奇偶性反转，因此通过子节点计算父节点的逆序对儿数量的奇偶性时可以使用异或运算；
使用 cpp 匿名函数按区间长度排序然后建树；
搜索每一个父节点 (入度为 $0$ 的点)

const int N = 1e3+7;

int pos[N];// 记录排列中每个数的位置
int a[N];// 记录每个位置上的数
// [] (参数表) {函数体} 是匿名函数

struct leaf{
    int l,r,k;
};
int deg[N];
vector<int> G[N];
vector<leaf> segs;
void oper(int k);
void dfs(int u){
    int k = segs[u].k;
   // 先对其所有子节点按左点排序
   auto &g = G[u];
   sort(g.begin(),g.end(),[&](int u,int v){
       return segs[u].l < segs[v].l;
   });
   // 遍历所有邻接点
   for(auto v : g){
       dfs(v);
       k ^= segs[v].k;
   }
   // 如果由子节点的逆序对儿的数量和与父节点的逆序对儿的和的奇偶性不一样
   // 要对子节点进行修改
   if(k){
       // 如果没有子区间
       if(g.empty()){
           oper(segs[u].l);
       }
       // 左端点最小的区间和当前区间的左端点相同
       else if(segs[g[0]].l == segs[u].l){
           // 修改相邻的两个区间
            oper(segs[g[0]].r);
       }
       else{
           oper(segs[g[0]].l-1);
       }
   }
}

void oper(int k){
    // 交换 k 和 k +1 所在位置
    swap(pos[k],pos[k+1]);
}

void solve(){
    map<pair<int, int>,int> Hash;
    int n,m; cin >> n >> m;
    for(int i =1; i <=n; i++){
        Hash[{i,i}] = 0;
        pos[i] = i;
    }
    for(int i =1; i <= m; i++){
        int l,r,k;
        cin >> l >> r >> k;
        if(Hash.count({l,r}) && Hash[{l,r}] !=k){
            // 新学的  就相当于
            /*cout << -1 << '\n;
             * return
             * */
            return cout << -1 << '\n',void();
        }
        if(Hash.count({l,r}))
            continue;
        // 出现过的区间要标记上
        Hash[{l,r}] = k;
        segs.push_back({l,r,k});
    }
    sort(segs.begin(),segs.end(),
         [](leaf a,leaf b)
         {return a.r-a.l < b.r-b.l;});
    m = segs.size();
    // 构建树
    for(int i =0; i < m; i++){
        for(int j = i+1; j < m; j++){
            if(segs[i].l >= segs[j].l && segs[i].r <= segs[j].r){
                G[j].push_back(i);
                deg[i]++;
            }
        }
    }
    for(int i =0; i < m; i++){
        if(!deg[i]){
            dfs(i);
        }
    }
    for(int i =1; i <= n; i++){
        a[pos[i]] = i;
    }
    for(int i =1; i <= n; i++){
        cout << a[i] << ' ';
    }
}