There is an apple tree in front of Taotao's house. When autumn comes, n apples on the tree ripen, and Taotao will go to pick these apples.

When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple; otherwise, he will not pick.

Given the heights of these apples h1,h2,⋯,hn, you are required to answer some independent queries. Each query is two integers p,q, which asks the number of apples Taotao would pick, if the height of the p-th apple were q (instead of hp). Can you answer all these queries?


小 A 的楼房外有一大片施工工地,工地上有 NN 栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

为了简化问题,我们考虑这些事件发生在一个二维平面上。小 A 在平面上 (0,0) 点的位置,第 i 栋楼房可以用一条连接 (i,0) 和 (i,H_i) 的线段表示,其中 H_i为第 i 栋楼房的高度。如果这栋楼房上任何一个高度大于 0 的点与 (0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

施工队的建造总共进行了 M 天。初始时,所有楼房都还没有开始建造,它们的高度均为 0。在第 i 天,建筑队将会将横坐标为 X_i 的房屋的高度变为 Y_i(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小 A 数数每天在建筑队完工之后,他能看到多少栋楼房?

大致题意 📖

两题转化一下后,都大致如此,对序列上某一值进行修改,然后求该序列从左到右,最大值的更新次数

链接 🔗

「P4198」楼房重建

题解 ❓

HDU 6406 有单loglog做法,这里我两题都用的双loglog做法
线段树维护两个值,区间最大值和区间最大值更新次数(也就是题目所求)
最大值直接维护就好,更新次数主要在合并的时候注意下

如果左区间最大值 大于 右区间的左区间的最大值,则说明右区间的左区间不会有任何贡献,然后递归右区间查找

如果左区间最大值 小于 右区间的左区间的最大值,则说明右区间的右区间一定是满贡献,然后递归左区间查找

代码

const ll N = 2e5+10;
const ll mod = 998244353;
ll t[N<<4],v[N<<4];
ll query(ll p,ll l,ll r,ll s)
{
    if(v[p] <= s)return 0;
    if(l == r) return v[p] > s;
    if(v[ls] <= s) return query(rs,mid+1,r,s);
    return query(ls,l,mid,s) + t[p] - t[ls];
}
void update(ll p,ll l ,ll r,ll pos,ll s)
{
    if( l == r)
    {
        t[p] = 1,v[p] =s;
        return;
    }
    if(pos <=  mid) update(ls,l,mid,pos,s);
    else update(rs,mid+1,r,pos,s);
    v[p] = max(v[ls],v[rs]);
    t[p] = t[ls] + query(rs,mid+1,r,v[ls]);
}
ll a[N];
int main()
{
//    __IN;__OUT
    ll T;RLL(T);
    while(T--)
    {
        ll n,m;RLL2(n,m);
        FOR(i,1,n)
        {
            RLL(a[i]);
            update(1, 1, n,i,a[i]);
        }
        FOR(i,1,m)
        {
            ll x,y;RLL2(x,y);
            update(1, 1, n,x,y);
            PLN(t[1]);
            update(1, 1, n,x,a[x]);
        }
        FOR(i,1,n) update(1,1,n,i,0);
    }

    return 0;
}