H Sequence

题意：

n个数，有两个操作，操作1是将第x位换成y
操作2是问包含第x位的序列中，x为最小数的序列有多少个

题解：

一开始想用树状数组来做，但是感觉树状数组太弱了，貌似不够用
赶紧换成线段树，（不想打线段树）
如何统计序列有多少个，比如指定第x位，在第x位之前有a个数比他大，有b个数比他小，那答案不就是a*b，但是注意，这个a和b必须分别是连续的，也就是在x之前有a个数是连续的，且与x相连的大于x的数，不然x就不是序列中最小的数了
那怎么计算a和b？
我们利用二分，第一次找x左边，第二次找x的右边
操作1好说，线段树常规操作
详细看代码

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int n,m;
int a[maxn];
int tree[maxn*4];
void bulid(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    bulid(rt*2,l,mid);
    bulid(rt*2+1,mid+1,r);
    tree[rt]=min(tree[rt*2],tree[rt*2+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*2,l,mid,x,y);
    else 
        update(rt*2+1,mid+1,r,x,y);
    tree[rt]=min(tree[rt*2],tree[rt*2+1]); 
}
int query(int rt,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r)
    {
        return tree[rt];
    }
    int mid=(l+r)>>1;
    int ans=1e9+9;
    if(ql<=mid)ans=min(ans,query(rt*2,l,mid,ql,qr));
    if(qr>mid)ans=min(ans,query(rt*2+1,mid+1,r,ql,qr));
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    bulid(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int x,y;
            cin>>x>>y;
            update(1,1,n,x,y);
            a[x]=y;
        }
        else 
        {
            int x;
            cin>>x;
            int nl,nr;
            int l=1,r=x;
            while(l<r)
            {
                int mid=(l+r)>>1;
                if(query(1,1,n,mid,x)>=a[x])r=mid;
                else l=mid+1;
            }
            nl=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--;
            nr=l-x+1;
            cout<<1ll*nl*nr<<endl;
        }
    }
}