H

题目意思就是有两种操作

1. 将x位置的数更新为y
2. 给你一个x，问有多少个子区间 的最小值为 a[x];

思路：这个题目和上次网络赛a题的那个有异曲同工之妙。基本类似，线段树维护最小值，二分区间长度，查找第一个小于 给定值 的数的位置。

单点更新，区间查询

代码：

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const double eps = 1e-6;
ll t, n, k,m;
int a[N],tree[N<<2];
void build(int rt,int l,int r){
	if(l==r){
		tree[rt]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}

void update(int rt,int l,int r,int x,int y){
	if(l==r){
		tree[rt]=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		update(rt<<1,l,mid,x,y);
	}
	else{
		update(rt<<1|1,mid+1,r,x,y);
	}
	tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}

int query(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[rt];
	}
	int mid=(l+r)>>1;
	int ans=1e9+10;
	if(L<=mid) ans=min(ans,query(rt<<1,l,mid,L,R));
	if(R>mid) ans=min(ans,query(rt<<1|1,mid+1,r,L,R));
	return ans;
}



void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		int op,x,y;
		cin>>op;
		if(op==1){
			cin>>x>>y;
			update(1,1,n,x,y);
			a[x]=y;
		}
		else{
			cin>>x;
			int al,ar,l=1,r=x;
			while(l<r){
				//TODO
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,x)>=a[x]) r=mid;
				else l=mid+1;
			}
  			al=x-l+1;
  			l=x,r=n+1;
  			while(l<r){
			  	int mid=(l+r)>>1;
			  	if(query(1,1,n,x,mid)<a[x]) r=mid;
			  	else l=mid+1;
			}
			l--;
			ar=l-x+1;
			cout<<1ll*al*ar<<endl;
		}
	}
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    t=1;
    //cin >> t;
    while(t--) solve();
    return 0;
}