https://anoth3r.top/solution/nkwk116/

牛客周赛 Round 116 题解，C++ version

A 小红的区间

判断一下即可。

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

B 小红的区间判断

同 ，判断一下即可。

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

C 小红的区间查询

二分左端点，查询是否在这个区间内即可，注意边界。

void solve() {
    int n, q;
    cin >> n >> q;
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1], a[i][2] = i + 1;
    sort(all(a), [&](auto a, auto b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    });
 
    vector<ll> l(n);
    for (int i = 0; i < n; ++i) l[i] = a[i][0];
 
    while (q--) {
        ll x;
        cin >> x;
        int pos = upper_bound(all(l), x) - l.begin() - 1;
        if (pos >= 0) {
            auto [l, r, id] = a[pos];
            if (l <= x && x <= r) {
                cout << id << "\n";
                continue;
            }
        }
        cout << -1 << "\n";
    }
}

D 小红的区间相交

考虑反做，只需要排除存在相离的一对或存在严格包含的一对即可。

• 相离：等价于所有区间交集为空，判断一下 和 的大小关系即可。

• 严格包含：

  • 按 升序排序；对相同 的区间一起处理（因为 不构成严格包含）。

  • 维护到当前为止（只考虑 更小的区间）的 。对于当前组中每个区间，如果 （严格大），说明存在某个 更小且 更大的区间，发生严格包含 —— 输出 。

  • 组内检查完毕后再把该组的 更新到 中。

如果两个检查都通过，则输出 。

void solve() {
    int n, mx = -inf, mn = inf;
    cin >> n;
    vector<PII> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].fi >> a[i].se;
        mx = max(mx, a[i].fi);
        mn = min(mn, a[i].se);
    }
    if (mx > mn) {
        cout << "No" << "\n";
        return;
    }
    sort(all(a), [&](auto a, auto b) {
        if (a.fi != b.fi) return a.fi < b.fi;
        return a.se < b.se;
    });
    mx = -inf;
    bool ok = false;
    int i = 0;
    while (i < n && !ok) {
        int j = i;
        while (j < n && a[j].fi == a[i].fi) ++j;
        for (int k = i; k < j; ++k) {
            if (mx > a[k].se) {
                ok = true;
                break;
            }
        }
        for (int k = i; k < j; ++k) {
            mx = max(mx, a[k].se);
        }
        i = j;
    }
    if (ok) cout << "No" << "\n";
    else cout << "Yes" << "\n";
}

E 小红的区间构造

设 为点 被覆盖次数。可发现相邻差分决定了每个位置需要多少区间开始或结束：

• 结束数 。
• 起始数 ​ 。

通过调节 总和使其恰为 ​ ，再用栈模拟（区间开始入栈、区间结束出栈）即可构造出合法方案。

void solve() {
    int n, m;
    ll sum = 0;
    cin >> n >> m;
    vector<ll> a(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    a[n + 1] = 0;
 
    vector<ll> d(n + 1, 0);
    ll diff = 0;
    for (int i = 1; i <= n; i++) {
        d[i] = max(0LL, a[i] - a[i + 1]);
        diff += d[i];
    }
    if (m < diff || m > sum) {
        cout << -1 << "\n";
        return;
    }
    ll extra = m - diff;
    vector<ll> e(n + 1, 0);
    for (int i = 1; i <= n; i++) e[i] = d[i];
    for (int i = 1; i <= n && extra > 0; i++) {
        ll cap = a[i] - e[i];
        if (cap <= 0) continue;
        ll use = min(cap, extra);
        e[i] += use;
        extra -= use;
    }
    vector<ll> s(n + 1, 0);
    s[1] = a[1];
    for (int i = 2; i <= n; i++) {
        s[i] = (a[i] - a[i - 1]) + e[i - 1];
        if (s[i] < 0) {
            cout << -1 << "\n";
            return;
        }
    }
    ll S = 0;
    for (int i = 1; i <= n; i++) S += s[i];
    if (S != m) {
        cout << -1 << "\n";
        return;
    }
 
 
    vector<PII> ans;
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        for (ll t = 0; t < s[i]; ++t) stk.pb(i);
        for (ll t = 0; t < e[i]; ++t) {
            if (stk.empty()) {
                cout << -1 << "\n";
                return;
            }
            int l = stk.back(); stk.pop_back();
            ans.eb(l, i);
        }
    }
    if (ans.size() != m) {
        cout << -1 << "\n";
        return;
    }
    for (auto [u, v] : ans) cout << u << " " << v << "\n";
}

F 小红的区间创建

每个已有区间把区间轴划分为若干相交与非相交段。 对每个位置 ：

• 设 为覆盖到 的区间最小右端点；新区间若包含 ，其右端点需 。
• 设 为覆盖到 的区间最大左端点；若包含 ，其左端点需 。

再排除已有区间端点，统计所有满足左右限制的不相交区间对数即可。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<PII> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].fi >> a[i].se;

    vector<vector<int>> mna(m + 3), mnr(m + 3);
    for (auto [l, r] : a) {
        if (l + 1 <= m) mna[l + 1].pb(r);
        if (r + 1 <= m) mnr[r + 1].pb(r);
    }
    multiset<int> ms;
    vector<int> mr(m + 1, m + 1);
    for (int x = 1; x <= m; x++) {
        for (int v : mna[x]) ms.insert(v);
        for (int v : mnr[x]) {
            auto it = ms.find(v);
            if (it != ms.end()) ms.erase(it);
        }
        if (ms.empty()) mr[x] = m + 1;
        else mr[x] = *ms.begin();
    }


    vector<vector<int>> mxa(m + 2), mxr(m + 2);
    for (auto [l, r] : a) {
        mxa[l].pb(l);
        if (r <= m) mxr[r].pb(l);
    }
    multiset<int> ms2;
    vector<int> ml(m + 1, 0);
    for (int x = 1; x <= m; x++) {
        for (int v : mxa[x]) ms2.insert(v);
        for (int v : mxr[x]) {
            auto it = ms2.find(v);
            if (it != ms2.end()) ms2.erase(it);
        }
        if (ms2.empty()) ml[x] = 0;
        else ml[x] = *ms2.rbegin();
    }

    vector<bool> vis(m + 2, 0);
    for (auto [l, r] : a) {
        vis[l] = 1;
        vis[r] = 1;
    }

    vector<vector<int>> bucket(m + 3);
    for (int i = 1; i <= m; i++) {
        int T = ml[i] + 1;
        if (T < 1) T = 1;
        if (T > m + 1) T = m + 1;
        if (i >= 1 && i <= m) bucket[T <= m + 1 ? T : m + 1].pb(i);
    }

    BIT<int> bit(m);
    ll ans = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j : bucket[i]) {
            if (!vis[j]) bit.add(j, 1);
        }
        if (vis[i]) continue;
        int mx = (mr[i] == m + 1 ? m : mr[i] - 1);
        if (mx < i) continue;
        ans += bit.ask(i, mx);
    }
    cout << ans << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

树状数组

template<class Int>
struct BIT {
    vector<Int> a;
    int n;

    BIT() {}
    BIT(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        a.resize(n + 1);
    }

    void add(int x, int k) {
        for (; x <= n; x += x & -x) {
            a[x] += k;
        }
    }

    void add(int x, int y, Int k) {
        add(x, k), add(y + 1, -k);
    }

    Int ask(int x) {
        Int ans = 0;
        for (; x; x -= x & -x) {
            ans += a[x];
        }
        return ans;
    }

    Int ask(int x, int y) {
        return ask(y) - ask(x - 1);
    }

    Int kth(int k) {
        Int ans = 0;
        for (int i = __lg(n); i >= 0; i--) {
            Int val = ans + (1 << i);
            if (val < n && a[val] < k) {
                k -= a[val];
                ans = val;
            }
        }
        return ans + 1;
    }
};