AT_abc389_f [ABC389F] Rated Range

Kingna · 2025-01-19 10:21:29 · 题解

定义 f_i 表示初始分数为 i，经过比赛后的最终分数。初始值 f_i=i。

经过第一场比赛后，值域在 L_1\sim R_1 中的所有 f_i 都会加上 1。经过第二场比赛后，值域在 L_2\sim R_2 中的所有 更新后的 f_i 值 都会加上 1。故每次把值域在 L_i\sim R_i 中的 f_i 值加上一。

故线段树维护，每次找到大于等于 L 的左端点和小于等于 R 的右端点，再维护区间加操作即可。

#include <bits/stdc++.h>
using namespace std;

#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long
const int N = 5e5 + 5;

int n, Q;

struct edge {
    int l, r;
}ed[N]; 

struct stu {
    int ls[N << 2], rs[N << 2], maxn[N << 2], sum[N << 2], lazy[N << 2];
    void push_up(int p) {
        maxn[p] = max(maxn[p << 1], maxn[p << 1 | 1]);
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }

    void push_down(int p) {
        if (lazy[p]) {
            lazy[p << 1] += lazy[p]; maxn[p << 1] += lazy[p];
            lazy[p << 1 | 1] += lazy[p]; maxn[p << 1 | 1] += lazy[p];
            sum[p << 1] += (rs[p << 1] - ls[p << 1] + 1) * lazy[p];
            sum[p << 1 | 1] += (rs[p << 1 | 1] - ls[p << 1 | 1] + 1) * lazy[p];
            lazy[p] = 0;
        }
    } 

    void build(int p, int l, int r) {
        ls[p] = l, rs[p] = r;
        if (l == r) {
            maxn[p] = sum[p] = l;
            return;     
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        push_up(p);
    }

    void modify(int p, int L, int R, int l, int r) {
        if (l <= L && R <= r) {
            lazy[p]++;
            sum[p] += (R - L + 1); 
            maxn[p]++;
            return;
        }
        push_down(p);
        int mid = (L + R) >> 1;
        if (l <= mid) modify(p << 1, L, mid, l, r);
        if (r > mid) modify(p << 1 | 1, mid + 1, R, l, r);
        push_up(p);
    }

    int query_max(int p, int L, int R, int l, int r) {
        if (l <= L && R <= r) return maxn[p];
        push_down(p);
        int mid = (L + R) >> 1, res = 0;
        if (l <= mid) res = max(res, query_max(p << 1, L, mid, l, r));
        if (r > mid) res = max(res, query_max(p << 1 | 1, mid + 1, R, l, r));
        return res; 
    }

    int query_sum(int p, int L, int R, int l, int r) {
        if (l <= L && R <= r) return sum[p];
        push_down(p);
        int mid = (L + R) >> 1, res = 0;
        if (l <= mid) res += query_sum(p << 1, L, mid, l, r);
        if (r > mid) res += query_sum(p << 1 | 1, mid + 1, R, l, r);
        return res; 
    }
}tr;

int getl(int x) {
    int L = 1, R = N - 5;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (tr.query_max(1, 1, N - 5, 1, mid) >= x) R = mid;
        else L = mid + 1;
    }
    return L;
}

int getr(int x) {
    int L = 1, R = N - 5;
    while (L < R) {
        int mid = (L + R + 1) >> 1;
        if (tr.query_max(1, 1, N - 5, 1, mid) <= x) L = mid;
        else R = mid - 1;
    }
    return L; 
}

signed main() {
    cin >> n;
    _for(i, 1, n) cin >> ed[i].l >> ed[i].r;
    tr.build(1, 1, N - 5);
    _for(i, 1, n) {
        tr.modify(1, 1, N - 5, getl(ed[i].l), getr(ed[i].r));
    }
    cin >> Q;
    while (Q--) {
        int x;
        cin >> x;
        cout << tr.query_sum(1, 1, N - 5, x, x) << endl; 
    }        
}