2021-2022 ACM-ICPC Brazil Subregional Programming Contest N.No Luck 主席树

题目分析

题目大意：给定一个序列 { x i } \{x_i\} {xi​}，表示 I C P C ICPC ICPC第 i i i年获奖队伍数量(按名次排名前 x i x_i xi​名获奖)。然后给定 N N N支队伍参加比赛的年份、获得的排名以及持续关注的年数( a i , p i , f i a_i,p_i,f_i ai​,pi​,fi​)。如果某只队伍在参加的年份未能获奖，那么在之后持续观测的年数中，如果他的名词在 m m m年中获得奖项，那么这 m m m年他将感到非常后悔。现在要求求对于给定的年份序列，某一参赛队伍的数据，该队伍在给定年份中的后悔年数。

思路分析：求后悔的年数，即为求静态区间中大于等于 p i p_i pi​的数字个数。显然是主席树+二分的板子。直接打下来即可。

需要注意的是：

1. 当该队伍在参加的年份获得奖项的话，那么不需要对后悔的年份进行统计，直接输出 0 0 0即可；
2. 查询返回非法直接输出 0 0 0(区间不包含数字且数字大于区间内所有数字)；
3. 这个题卡常，输入输出要优化一下。

Accepted Code

#include 
#define ll int
using namespace std;

const int N = 3e5 + 5;
int ls[N * 40], rs[N * 40], rt[N * 40], tot;
int sum[N * 40], a[N], b[N], c[N];

void build(int l, int r, int root){
    sum[root] = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, ls[root] = ++tot);
    build(mid + 1, r, rs[root] = ++tot);
}

void update(int l, int r, int root, int last, int pos){
    ls[root] = ls[last], rs[root] = rs[last], sum[root] = sum[last] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (mid >= pos) update(l, mid, ls[root] = ++tot, ls[last], pos);
    else update(mid + 1, r, rs[root] = ++tot, rs[last], pos);
}

ll query(int l, int r, int root, int last, int pos){
    if (l == r) return sum[root] - sum[last];
    int mid = l + r >> 1;
    ll ans = 0;
    if (pos