题解：AT_abc389_f [ABC389F] Rated Range

yy0707 · 2025-01-19 07:50:08 · 题解

题目大意：

有 n 场比赛，第 i 场所有分数在 l_i 到 r_i 之间的人可以加 1 分。然后给你 q 个询问，问如果一个人的初始分数是 x 那么在这 n 场比赛之后它的分数是多少。

Solution：

我们可以将所有询问排好序，存进树状数组里，然后模拟 n 场比赛，每次利用树状数组倍增求出第一个大于等于 l_i 的位置以及最后一个小于等于 r_i 的位置（觉得麻烦也可以用二分，但是时间是 \log^2q），然后区间加把这一段区间加上 1，前面几步都可以用树状数组维护差分数组来解决，最后把答案取出来输出就行了。
时间复杂度 O((q+n)\log q)。

Code

#include<bits/stdc++.h>
using namespace std;
int n,q,l[200001],r[200001],ans[300001];
struct query{int x,id;}p[300001];
struct fenwick{
    private:
        int tr[300001];
        void add(int p,int x){for(;p<=q;p+=p&-p)tr[p]+=x;}
    public:
        void add(int l,int r,int x){add(l,x);add(r+1,-x);}
        int query(int p){
            int ans=0;
            for(;p;p-=p&-p)ans+=tr[p];
            return ans;
        }int first_ge(int x){
            int p=0,v=0;
            for(int i=20;i>=0;i--){
                if(p+(1<<i)<=q&&v+tr[p+(1<<i)]<x)p+=(1<<i),v+=tr[p];
            }return p+1;
        }int last_le(int x){
            int p=0,v=0;
            for(int i=20;i>=0;i--){
                if(p+(1<<i)<=q&&v+tr[p+(1<<i)]<=x)p+=(1<<i),v+=tr[p];
            }return p;
        }
}tr;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    cin>>q;
    for(int i=1;i<=q;i++)cin>>p[i].x,p[i].id=i;
    sort(p+1,p+q+1,[](query a,query b){return a.x<b.x;});
    for(int i=1;i<=q;i++)tr.add(i,i,p[i].x);
    for(int i=1;i<=n;i++){
        int x=tr.first_ge(l[i]);
        int y=tr.last_le(r[i]);
        tr.add(x,y,1);
    }for(int i=1;i<=q;i++)ans[p[i].id]=tr.query(i);
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}