题解：AT_abc389_f [ABC389F] Rated Range

· · 题解

AT_abc389_f [ABC389F] Rated Range

upd 2025/1/19：换一下链接，更改了描述。

原题传送门

更好的阅读体验

题目大意

Takahashi 计划参加 n 场 AtCoder 比赛。

在第 i 场比赛（1 \leq i \leq n）中，如果他的评分在 l_i 和 r_i 之间（闭区间），他的评分将增加 1。

总共 q 次查询，每次给出一个整数 x。假设 Takahashi 的初始评分为 x，求参加完 n 场比赛后的评分。

解题思路

首先想到暴力思路，对于每次查询做一次模拟，时间复杂度 O(nq)。

一次查询做一次模拟并不好优化，此时观察到 x 的值域不是很大。于是我们可以对于每个初始评分，计算最终评分。

这样做每个比赛就转化成了一次区间操作，二分维护区间的左右端点可以（查每个点在做完前面的操作后值是否在加分范围内），并在这段区间上加 1。区间加，单点查，可以用线段树或差分树状数组维护。每次操作时间复杂度 O(\log x)，总时间复杂度 O(n\log x)，可以通过本题。

参考代码

#include<iostream>
#define mid (L+R>>1)
#define lowbit(i) (i&(-i))
using namespace std;
const int N=5e5+10;
int n,low,high,q;
int a[N]; 
struct BIT{
    int c[N];
    void add(int x,int y){
        for(;x<N;x+=lowbit(x)) c[x]+=y;
    } 
    int ask(int x){
        int ans=0;
        for(;x;x-=lowbit(x)) ans+=c[x];
        return ans;
    }
}TR;
int main(){
    cin>>n;
    for(int i=1,l,r;i<=n;i++){
        cin>>l>>r;
        int L=1,R=5e5+5;
        while(L<R){
            int val=mid+TR.ask(mid);
            if(val>=l) R=mid;
            else L=mid+1;
        }
        low=L;
        L=1,R=5e5+5;
        while(L<R) {
            int val=mid+TR.ask(mid);
            if(val>r) R=mid;
            else L=mid+1;
        }
        high=L-1;
        if(low<=high){
            TR.add(low,1);
            TR.add(high+1,-1);
            a[low]++;
            a[high+1]--;
        }
    }
    for(int i=1;i<=5e5;i++) a[i]+=a[i-1];
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<(x+a[x])<<'\n';
    }
    return 0;
}

AC 记录