UOJ

分析

把所有操作离线，按下标从大到小扫描线，并维护一棵以时间为下标的和后缀 $\min$ 有关的线段树。

那么每个操作相当于对某段时间内取 $\min$，一个位置的后缀最小值个数就是它被取 $\min$ 的次数。

用 Segment Tree Beats 维护即可。

具体的，我们只需要维护最大值、严格次大值和最大值被取 $\min$ 的次数，如果最大值 $\leq$ 要取 $\min$ 的值直接返回，如果严格次大值 $\leq$ 要取 $\min$ 的值就把最大值被取 $\min$ 次数 $+1$ 并修改最大值。

复杂度据说是 $\mathcal{O}(n\log n)$ 的，但是我不会证。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int inf=0x3f3f3f3f;

int n,Q,a[N],lst[N],ans[N];
int qhead[N],mhead[N],nxt[N],lb[N],val[N];

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],smaxv[N<<2],tagv[N<<2];
void pushup(int o) {
    maxv[o]=max(maxv[ls],maxv[rs]);
    smaxv[o]=max(maxv[ls]==maxv[o]?smaxv[ls]:maxv[ls],
                 maxv[rs]==maxv[o]?smaxv[rs]:maxv[rs]);
}
void pushdown(int o) {
    if (tagv[o]) {
        if (maxv[o]<maxv[ls]) maxv[ls]=maxv[o],tagv[ls]+=tagv[o];
        if (maxv[o]<maxv[rs]) maxv[rs]=maxv[o],tagv[rs]+=tagv[o];
        tagv[o]=0;
    }
}

void build(int o,int l,int r) {
    maxv[o]=inf,smaxv[o]=-1;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int w) {
    if (maxv[o]<=w) return;
    if (ql<=l&&r<=qr&&smaxv[o]<=w) { maxv[o]=w,++tagv[o]; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
int query(int o,int l,int r,int p) {
    if (l==r) return tagv[o];
    int mid=(l+r)>>1; pushdown(o);
    if (p<=mid) return query(ls,l,mid,p);
    else return query(rs,mid+1,r,p);
}
#undef ls
#undef rs

int main() {
    n=read(),Q=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=Q;++i) {
        int op=read(),p=read();
        if (op==1) nxt[i]=mhead[p],mhead[p]=i,lb[i]=lst[p],lst[p]=i,val[i]=a[p],a[p]=read();
        else nxt[i]=qhead[p],qhead[p]=i;
    }
    memset(ans,-1,sizeof(ans)); build(1,0,Q);
    for (int i=n;i;--i) {
        for (int j=mhead[i];j;j=nxt[j]) modify(1,0,Q,lb[j],j-1,val[j]);
        modify(1,0,Q,lst[i],Q,a[i]);
        for (int j=qhead[i];j;j=nxt[j]) ans[j]=query(1,0,Q,j);
    }
    for (int i=1;i<=Q;++i)
        if (~ans[i]) printf("%d\n",ans[i]);
    return 0;
}