听说有 polylog 做法，但是偷懒想了个根号 log 的做法，肯定有优化的空间，但一看数据范围 \(10^5\) 就摆烂了。
显然对于一次操作，我们只用关心最早什么时候这次操作加入的数全部都被 pop 掉了，求出这个之后对于 \(x\) 相同的操作我们放一起考虑，求一遍区间并即可算出贡献。
于是问题转化为如何求第 \(i\) 次插入的元素全部被 pop 掉的最早时间 \(r_i\)。对序列分块，每块 \(B\) 个元素，对于整块，我们用 two pointers 求出每个时刻 \(i\) 之后最早的时刻 \(r\)，使得对于这块中每个位置 \(j\)，都有 \((i,r]\) 中每个位置 \(j\) 被插入的次数都至少为 \(a_j\)（显然满足单调性）。处理方法就是考虑一次操作与 \([L_b,R_b]\) 的交，如果是整块就打 tag，否则暴力改，显然这部分复杂度是 \(\dfrac{nm}{B}\) 的。对于散块，扫描线 + 树状数组上二分即可，复杂度 \(mB\log^2n\)，取 \(B=\dfrac{n}{\log n}\) 即可。
const int MAXN=1e5;
const int INF=0x3f3f3f3f;
int n,m,a[MAXN+5],c[MAXN+5],tag,cmx,rit[MAXN+5];
int blk_sz,blk_cnt,L[MAXN+5],R[MAXN+5],bel[MAXN+5];
struct opt{int l,r,x;}b[MAXN+5];
void modify(int l,int r,int b,int v){
if(l==L[b]&&r==R[b])tag+=v;
else if(l<=r){
for(int i=l;i<=r;i++)c[i]+=v;cmx=-INF;
for(int i=L[b];i<=R[b];i++)chkmax(cmx,c[i]);
}
}
vector<pii>vec[MAXN+5];
int res[MAXN+5];
vector<int>qv[MAXN+5],ql[MAXN+5],qr[MAXN+5];
int t[MAXN+5];
void add(int x,int v){for(int i=x;i<=MAXN;i+=(i&(-i)))t[i]+=v;}
int query(int x){int ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
int main(){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
blk_sz=100;blk_cnt=(n-1)/blk_sz+1;
for(int i=1;i<=blk_cnt;i++){
L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,n);
for(int j=L[i];j<=R[i];j++)bel[j]=i;
}
for(int i=1;i<=blk_cnt;i++){
cmx=tag=0;
for(int j=L[i];j<=R[i];j++)c[j]=a[j]+1,chkmax(cmx,a[j]+1);
for(int j=1,k=1;j<=m;j++){
if(k<j)k=j;
while(k<=m&&cmx+tag>0){
modify(max(L[i],b[k].l),min(R[i],b[k].r),i,-1);
++k;
}
if(b[j].l<=L[i]&&R[i]<=b[j].r){
if(cmx+tag>0)rit[j]=m+1;
else chkmax(rit[j],k-1);
}
modify(max(L[i],b[j].l),min(R[i],b[j].r),i,1);
}
}
for(int i=1;i<=m;i++){
ql[b[i].l].pb(i);qr[b[i].r+1].pb(i);
qv[bel[b[i].l]].pb(i);
if(bel[b[i].l]!=bel[b[i].r])qv[bel[b[i].r]].pb(i);
}
for(int i=1;i<=n;i++){
for(int id:ql[i])add(id,1);
for(int id:qr[i])add(id,-1);
for(int id:qv[bel[i]]){
if(b[id].l<=i&&i<=b[id].r){
int l=id,r=m,p=id-1;
while(l<=r){
int mid=l+r>>1;
if(query(mid)-query(id)<a[i])p=mid,l=mid+1;
else r=mid-1;
}
chkmax(rit[id],p+1);
}
}
}
for(int i=1;i<=m;i++)vec[b[i].x].pb(mp(i,rit[i]-1));
for(int i=1;i<=MAXN;i++)if(!vec[i].empty()){
sort(vec[i].begin(),vec[i].end());
for(int l=0,r;l<vec[i].size();l=r){
r=l;int mxr=vec[i][l].se;
while(r<vec[i].size()&&vec[i][r].fi<=mxr)chkmax(mxr,vec[i][r].se),++r;
res[vec[i][l].fi]++;res[mxr+1]--;
}
}
for(int i=1;i<=m;i++)res[i]+=res[i-1];
for(int i=1;i<=m;i++)printf("%d\n",res[i]);
return 0;
}