AtCoder Beginner Contest 158 F.Removing Robots

题目链接
大意：给你n个机器人，每个机器人在 $x_{i}$ ，位置，如果被激活了就会移动到 $x_{i} + d_{i} - 1$ ，然后被销毁，中途遇到的机器人都会被激活且移动。
有一种操作是：选择一个未被激活的机器人并激活它。
你可以执行任意次数操作（还有未激活的）
问最终会有多少种不同的全都没被激活机器人集合。
思路：显然先把每个机器人 $i$ 激活后到能影响的最远的机器人编号 $L_{i}$ 预处理出来。然后分两种情况进行dp即可。
预处理的处理方式大致上：
先把所有机器人按照坐标排序。从大到小遍历，然后二分出当前机器人的 $x_{i} + d_{i} - 1$ 最大包含的机器人 $y$ ，那么 $L_{i} = m a x_{j = i + 1}^{y} L_{j}$ ,特别的如果 $y = i$ 那么 $L_{i} = i$ 。
直接用bit维护一下后缀最大值即可。
剩下的dp部分就很显然了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n;
struct uzi{
  int a,b,i;
  bool operator <(const uzi &t)const{
    return a<t.a;
  }
}p[N];
int L[N];
LL f[N];
const LL mod=998244353;
int t[N];
void add(int p,int d){
  for(;p<N;p+=p&-p)t[p]=max(t[p],d);
}
int ge(int p,int d){
  int res=0;
  for(;p;p-=p&-p)res=max(res,t[p]);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b,p[i].i=i;
  sort(p+1,p+1+n);
  auto get=[&](int x){
    int l=1,r=n,ans=1;
    while(l<=r){
      int mid=l+r>>1;
      if(p[mid].a<=x)ans=mid,l=mid+1;
      else r=mid-1;
    }
    return ans;
  };
  for(int i=n;i>=1;i--){
    L[i]=i;
    int x=get(p[i].a+p[i].b-1);
    L[i]=max(L[i],ge(x,1));
    add(i,L[i]);
  }
  f[1]=1;
  for(int i=1;i<=n;i++){
    f[i+1]+=f[i];//不开
    f[L[i]+1]+=f[i];//开
    f[i+1]%=mod;
    f[L[i]+1]%=mod;
  }
  cout<<f[n+1]<<endl;
  return 0;
}