我的思路是这样的：可以把 Rating 的值域分成一段段区间，每段区间参加 $N$ 场比赛之后上的分相同。于是可以分治，分讨一下当前 Rating 和比赛 Rating 范围这两个区间的相交情况，可以写出如下代码：

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,q,L[N],R[N],res[N];
void dfs(int k,int l,int r,int add)//分治，枚举到第i场比赛，当前等级分为[l,r]，加了add分，一个区间内加分的信息相同
{
  if(l>r) return;
  if(k>n)
  {
    for(int i=l-add;i<=r-add;i++) res[i]=i+add;
    return;
  }
  if(R[k]<l||L[k]>r) dfs(k+1,l,r,add);//和当前区间不相交
  else if(L[k]<=l&&l<=R[k]&&r>=R[k]) dfs(k+1,l+1,R[k]+1,add+1),dfs(k+1,R[k]+1,r,add);//和当前区间左端点相交
  else if(L[k]<=r&&r<=R[k]&&l<=L[k]) dfs(k+1,L[k]+1,r+1,add+1),dfs(k+1,l,L[k]-1,add);//和当前区间右端点相交
  else if(L[k]<=l&&r<=R[k]) dfs(k+1,l+1,r+1,add+1);//比赛包含当前区间
  else if(l<=L[k]&&R[k]<=r) dfs(k+1,l,L[k]-1,add),dfs(k+1,L[k]+1,R[k]+1,add+1),dfs(k+1,R[k]+1,r,add);//当前区间包含比赛
  return;
}
int main()
{
  ios::sync_with_stdio(0);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>L[i]>>R[i];
  dfs(1,1,500000,0);
  cin>>q;
  while(q--)
  {
    int x;
    cin>>x;
    cout<<res[x]<<"\n";
  }
  return 0;
}

但是实则 TLE 了，发现是区间没有相交的情况很多，导致效率很低，本蒟蒻不会分析复杂度也想不到方法优化，有没有大佬帮忙一下？感激不尽。