题目分析

这是一个环上的双色覆盖问题：需要在环上分配 $M$ 条线段的颜色（红/蓝），使得每个位置都被两种颜色覆盖。

算法思路：贪心 + 树状数组优化

核心思想

• 将环展开为 $2N$ 的线性区间处理跨越问题
• 使用树状数组维护区间覆盖关系
• 通过贪心策略选择主线段和附属线段

关键步骤

1. 区间预处理

for(int i=1; i<=m; i++) {
    p[i].x = read();
    p[i].y = read() + 1;  // 转为左闭右开
    if(p[i].x >= p[i].y) p[i].y += n;  // 处理跨越
}

2. 线段分类

按长度降序排序，用树状数组判断覆盖关系：

• 如果当前线段被已有线段覆盖，标记为附属线段
• 否则加入主线段集合

sort(t+1, t+m+1, cmp1);  // 按长度降序

for(int ii=1; ii<=m; ii++) {
    int i = t[ii];
    if(tr.query(p[i].x).x >= p[i].y) {
        fa[i] = tr.query(p[i].x).y;  // 记录父线段
        // 标记为被覆盖区间
    } else {
        e.push_back(i);  // 加入主线段集合
        tr.add(p[i].x, make_pair(p[i].y, i));
    }
}

3. 可行性检查

扫描环上每个位置：

for(int i=1; i<=n; i++) {
    if(!vis[i] && !vis[i+n] && tag[i]+tag[i+n] < 2) {
        puts("impossible");  // 该位置未被双色覆盖
        return 0;
    }
}

4. 颜色分配

• 主线段交替染色
• 附属线段与父线段颜色相反

void go(int x) {
    bool color = 0;
    for(int i=0; i<e.size(); ++i) {
        col[e[i]] = color;
        if(i != x) color ^= 1;  // 交替染色
    }
    
    for(int i=1; i<=m; ++i) {
        if(fa[i]) col[i] = col[fa[i]] ^ 1;
    }
}

特殊情况处理

当主线段数量为奇数时，需要找到合适的断点：

if((int)e.size() & 1) {
    // 寻找可行的断点位置
    for(int i=0; i<e.size()-1; i++) {
        if(pre[p[e[i+1]].x-1] == pre[p[e[i]].y-1]) {
            go(i);  // 在此处断开
            return 0;
        }
    }
    puts("impossible");
}

复杂度分析

• 排序：$O(M \log M)$
• 树状数组操作：$O(M \log N)$
• 总复杂度：$O(M \log N)$，满足数据范围要求

算法优势

• 高效处理环：通过展开为 $2N$ 区间
• 贪心优化：优先处理长线段简化问题
• 完备检查：确保每个位置都被双色覆盖

该解法通过巧妙的线段分类和树状数组维护，高效解决了环上的双色覆盖问题。