题解：P11286 [COTS 2017] 盗道 Krimošten

首先我们考虑一个简化的问题：求出对于所有初始钱数，偷完前 x 座房子后小偷会有多少钱。

从西到东扫描房子，扫描过程中维护一个序列，序列的第 i 项表示若小偷初始有 i 库纳，他现在会有多少钱。

例如，假设从西到东有三座房子，每座房子内部分别有 5,2,8 库纳。 一开始，序列的值为：

偷完第一座房子（有 5 库纳），序列变成：

偷完第二座房子（有 2 库纳），序列变成：

偷完第三座房子（有 8 库纳），序列变成

我们发现，这个序列一定是单调不降的。

为了维护这个序列，我们需要一个支持以下操作的数据结构：

1. 找到某个数在序列中第一次出现的位置；
2. 对序列上某个区间中的数全部 +1/-1。
3. 查询序列中某个位置上的数。

容易用树状数组实现。具体地，用树状数组维护序列的差分，那么操作 2 转化为单点加，操作 3 转化为查询前缀和。因为原序列单调不降，所以操作 1 可以用树状数组上二分实现。

回到原问题。为了回答询问 (l,r,c)，在处理第 l 座房子对答案的贡献之前，先找到序列中 c 的位置 p。处理完第 r 座房子之后，序列中位置 p 上的数就是这个询问的答案。

最后，我们要保证每个询问的 c 都能在序列中找到。显然，序列中每个数的变化量都不会超过 n，所以只需一开始往序列中填入 -n 到 V+n 之间的所有整数即可，其中 V 是询问的 c 的最大值。

时间复杂度 O((n+m) \log(n+V))。

#include<bits/stdc++.h>
using I=int;
template<class T>using V=std::vector<T>;
template<class T,I N>using A=std::array<T,N>;
int main(){
  std::cin.tie(0)->sync_with_stdio(0);
  I n,m;std::cin>>n>>m;
  V<I>a(n);for(I&e:a)std::cin>>e;
  V<V<A<I,2>>>ql(n);V<V<I>>qr(n);I lim=0;
  for(I i=0;i<m;i++){
    I l,r,c;std::cin>>l>>r>>c;l--;r--;lim=std::max(lim,c);
    ql[l].push_back({i,c});qr[r].push_back(i);
  }
  V<I>fw(lim+2*n+2);
  auto add=[&](I p,I v){for(p++;p<fw.size();p+=p&-p)fw[p]+=v;};
  auto sum=[&](I p){I w=0;for(p++;p;p-=p&-p)w+=fw[p];return w;};
  auto lwb=[&](I v){
    I p=0,s=0;
    for(I i=31-__builtin_ctz(fw.size());i>=0;i--)
      if((p|1<<i)<fw.size()&&s+fw[p|1<<i]<v)s+=fw[p|=1<<i];
    return p;
  };
  add(0,-n);for(I i=1;i<=lim+2*n;i++)add(i,1);
  V<I>pos(m),ww(m);
  for(I i=0;i<n;i++){
    for(auto[i,c]:ql[i])pos[i]=lwb(c);
    I x=lwb(a[i]),y=lwb(a[i]+1);
    add(0,1);add(x,-1);add(y,-1);
    for(I x:qr[i])ww[x]=sum(pos[x]);
  }
  for(I e:ww)std::cout<<e<<'\n';
  return 0;
}