思路

对于全局来讲，我们维护一个 b_i 序列，其中初始时 b_i=i，表示盗贼初始有 i 块钱经过操作后所拥有的钱数。

而每一个位置上的数 a_i，对应操作为将 b 中 b_j < a_i 的变成 b_j+1，b_j>a_i 的变成 b_j-1，可以打表发现 b_i 是单调不降的，这是一个很重要的性质。

再看区间怎么做。考虑扫描线，还是维护 b_i。

对于修改操作，b_i 是单调不降的，可以拿线段树维护 b_i，转化为线段树上二分，区间加。

对于询问 (l,r,k)，现在假设我们已经扫完了 [1,l-1] 的所有 a_i 并进行了操作，那么在 b 中找一个位置满足 b_i=k，可以线段树二分。这里可以看成是找一个初始钱数为 k 的位置。再扫描到 r 时，直接询问记录位置的值即可，等价于初始钱数为 k，操作完 [l,r] 后的值。而为了让 b_i 中 [0,10^6] 的值都存在，可以让 b_i=i,i\in[-10^6,2\times10^6]。

时间复杂度是 O(n\log V) 的。

code

#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define mset(x,y) memset((x),(y),sizeof((x)))
#define mcpy(x,y) memcpy((x),(y),sizeof((y)))
#define FileIn(x) freopen(""#x".in","r",stdin)
#define FileOut(x) freopen(""#x".out","w",stdout)
#define debug(x) cerr<<""#x" = "<<(x)<<'\n'
#define Assert(x) if(!(x)) cerr<<"Failed: "#x" at line "<<__LINE__,exit(1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
const int N=5e5+10;
const int V=1e6,M=3e6+10;
bool StM;
int n,m,c[N],pos[N];
vector<int>qr[N];
vector<pair<int,int>>ql[N];
int ma[M<<2],tag[M<<2],Ans[N];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
void push_up(int x){ma[x]=max(ma[lc(x)],ma[rc(x)]);}
void addtag(int val,int x){ma[x]+=val,tag[x]+=val;}
void push_down(int x)
{
    if(!tag[x]) return;
    addtag(tag[x],lc(x)),addtag(tag[x],rc(x)),tag[x]=0;
}
void build(int l,int r,int x)
{
    if(l==r)
        return void(ma[x]=l);
    int mid=(l+r)>>1;
    build(l,mid,lc(x)),build(mid+1,r,rc(x));
    return push_up(x);
}
int query(int val,int l=-V,int r=2*V,int x=1)
{
    if(l==r) return l;
    push_down(x);
    int mid=(l+r)>>1;
    if(ma[lc(x)]>=val) return query(val,l,mid,lc(x));
    else return query(val,mid+1,r,rc(x));
}
int Query(int y,int l=-V,int r=2*V,int x=1)
{
    if(l==r)
        return ma[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(y<=mid) return Query(y,l,mid,lc(x));
    else return Query(y,mid+1,r,rc(x));
}
void modify(int p,int q,int val,int l=-V,int r=2*V,int x=1)
{
    Assert(p<=q);
    if(p<=l&&q>=r)
        return addtag(val,x);
    push_down(x);
    int mid=(l+r)>>1;
    if(p<=mid) modify(p,q,val,l,mid,lc(x));
    if(q>mid) modify(p,q,val,mid+1,r,rc(x));
    return push_up(x);
}
void Main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    build(-V,2*V,1);
    for(int id=1,l,r,k;id<=m;id++)
    {
        cin>>l>>r>>k;
        ql[l].push_back({k,id});
        qr[r].push_back(id);
    }
    for(int i=1,x,y;i<=n;i++)
    {
        for(auto [val,id]:ql[i]) pos[id]=query(val);
        x=query(c[i]),y=query(c[i]+1);modify(-V,x-1,1),modify(y,2*V,-1);
        for(auto id:qr[i]) Ans[id]=Query(pos[id]);
    }
    for(int i=1;i<=m;i++) cout<<Ans[i]<<'\n';
}
bool EdM;
int main()
{
    cerr<<fabs(&StM-&EdM)/1024.0/1024.0<<" MB\n";
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int StT=clock();
    int T=1;
    while(T--) Main();
    int EdT=clock();
    cerr<<1e3*(EdT-StT)/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}