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?

「P4198」楼房重建

#### 题解 ❓

HDU 6406 有单$log$做法，这里我两题都用的双$log$做法

#### 代码

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;
}