这把周赛打起来怪怪的，交一发 wa 一发。

A.小红的区间

模拟即可。

void solve(){
    int l1,r1,l2,r2;
    cin >> l1 >> r1 >> l2 >> r2;
    cout << (l2 < l1 && r1 < r2 ? "A" : "B") << "\n";
}

B.小红的区间判断

同理，模拟即可。

void solve(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if (a < c && d < b || c < a && b < d){
        cout << "A" << "\n";
    } else if (b < c || a > d) {
        cout << "B" << "\n";
    } else {
        cout << "C" << "\n";
    }
}

C.小红的区间查询

提供一种相对另类的做法，把查询离线下来，然后再求答案。

using p32 = std::pair<int,int>;
void solve(){
    int n,q;
    cin >> n >> q;
    vector<p32> nodes;
    for (int i = 1;i <= n;i ++){
        int l,r;
        cin >> l >> r;
        nodes.push_back({l,i});
        nodes.push_back({r,n+q+1});
    }
    vector<int> ans(q+1);
    for (int i = 1;i <= q;i ++){
        int x;cin >> x;
        nodes.push_back({x,i+n});
    }
    ranges::sort(nodes);
    for (int i = 0,st = -1;i < nodes.size();i ++){
        auto [x,y] = nodes[i];
        if (y == n+q+1) st = -1;
        else if (y > n) {
            ans[y-n] = st;
        } else st = y;
    }
    for (int i = 1;i <= q;i ++) cout << ans[i] << "\n";
}

D.小红的区间相交

我们对于这个区间中，只需判断 中都恰好包含其他区间的边界一次即可。

做法比较多，这里使用了异或哈希。

注意：由于相交具有特殊性，两个区间的边界占有相同位置也算相交。

mt19937_64 rnd(time(0));

using p32 = std::pair<int,int>;
void solve(){
    int n;
    cin >> n;
    vector<p32> nodes;
    vector<u64> hsh(n+1),rec1(n+1),rec2(n+1);
    set<int> L,R;
    for (int i = 1;i <= n;i ++){
        int l,r;
        cin >> l >> r;
        hsh[i] = rnd();
        nodes.push_back({l,i});
        nodes.push_back({r,i+n});
        L.insert(l);
        R.insert(r);
    }
    ranges::sort(nodes);
    u64 H = 0,G = 0;
    for (int i = 1;i <= n;i ++) G ^= hsh[i];
    for (auto [x,y] : nodes){
        if (y <= n) rec1[y] = H,H ^= hsh[y];
        else rec1[y-n] ^= H,H ^= hsh[y-n];
    }
    for (int i = 1;i <= n;i ++) {
        if (rec1[i] != G) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

E.小红的区间构造

考虑先求出来当前数组至少需要多少个区间，可以使用单调栈求。

求出之后，我们再尝试把每一个区间拆成长度为1的区间。

void solve(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n+2);
    for (int i = 1;i <= n;i ++) cin >> a[i];
    i64 mn = 0;
    vector<p32> ans;
    vector<p32> stk = {{0,0}};
    for (int i = 1;i <= n + 1;i ++){
        while(stk.size() && stk.back().first > a[i]){
            auto [x,y] = stk.back();
            stk.pop_back();
            int add = x - max(a[i],stk.back().first);
            mn += add;
            for (int j = 1;j <= add && ans.size() < m;j ++){
                // cerr << y << ' ' << i-1 << "\n";
                ans.push_back({y,i-1});
            }
            if (a[i] > stk.back().first) stk.push_back({a[i],y});
        }
        if (stk.size() && stk.back().first == a[i]) continue;
        stk.push_back({a[i],i});
    }
    if (accumulate(a.begin(),a.end(),1LL) < m || mn > m) {
        cout << -1 << '\n';
        return;
    }
    vector<p32> res;
    while(ans.size()){
        auto [x,y] = ans.back();
        for (int i = x;i < y;i ++){
            if (ans.size() + res.size() == m) break;
            res.push_back({i,i});
            x = i+1;
        }
        ans.pop_back();
        res.push_back({x,y});
    }
    for (auto [x,y] : res){
        cout << x << ' ' << y << "\n";
    }
}

F.小红的区间创建

对于每个合法区间，我们发现必须中间包含其他完整的区间。

于是我们可以枚举每一个坐标的情况，然后统计在当前坐标之前有多少个合法位置即可。

可以考虑使用 异或哈希+std::map 实现。

mt19937_64 rnd(time(0));
 
void solve(){
    i64 res = 0;
    int n,m;
    cin >> n >> m;
    vector<u64> hsh(m+1);
    vector<bool> vis(m+1);
    map<u64,int> cnt;
    for (int i = 1;i <= n;i ++){
        int l,r;cin >> l >> r;
        vis[l] = 1,vis[r] = 1;
        u64 h = rnd();
        hsh[l] ^= h,hsh[r] ^= h;
    }
    u64 val = 0;
    for (int i = 1;i <= m;i ++){
        val ^= hsh[i];
        if (vis[i]) continue;
        cnt[val] ++;
        res += cnt[val];
    }
    cout << res << "\n";
}