题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6406
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
const int maxn =2e5+10;
const int mod=1e9+7;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：给定一个序列，已知这个序列的权值定义为是:
从1位置出发一直到最后，如果拿到比当前水果重量大的则换，如果不是就跳过，
这个序列的权重就是最后拿过的数量，
现在有q次询问，每次都是把p位置改成q，
询问这样的序列权重。明显，在尾部维护一个单调栈，
我因为是用树状数组来统计的，所以还要离散化，
空间压力也大。。。
反正思路就是倒着扫描，在尾部维护一个单调栈，
假设扫描到i位置，则先处理在i处的修改，
如果修改的值比之前维护出来的最大值大，则很简单，直接cnt[i]+查询单调栈中比
查询值大的个数，如果不大于，则需要利用之前维护出来的最大值代替下。离散化的过程代码量稍微大了点，，一些细节的地方把握好这道题还是蛮好想的*/int n,q,x;
int a[maxn],b[maxn],c[maxn];///数据存储
int cnt[maxn],val[maxn];///数据数组，计数数组，判定数组
int Sk[maxn];///前驱数组和单调栈数组
vector<pair<int,int>> qy[maxn];
///树状数组
int bit[maxn],ans[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,int d){for(;x<maxn;bit[x]+=d,x+=lowbit(x));}
int sum(int x){int ret=0;for(;x>0;ret+=bit[x],x-=lowbit(x));return ret;}int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&q);int cur=0,num=0;for(int i=0;i<=n;i++) qy[i].clear();///清空查询数组for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];///记录数据集合for(int i=n+1;i<=n+q;i++) scanf("%d%d",&c[i],&a[i]),b[i]=a[i];sort(a+1,a+1+n+q);for(int i=1;i<=n+q;i++){b[i]=lower_bound(a+1,a+1+n+q,b[i])-a+1;///数据离散化if(i>=n+1) qy[c[i]].push_back(make_pair(b[i],i-n));}for(int i=1;i<=n;i++){val[i]=cur,cnt[i]=num;///记录当前位置的最大值和最大数量if(i==1||cur<b[i]) num++,cur=b[i];}int l=0,r=-1;///单调栈memset(bit,0,sizeof(bit));for(int i=n;i>=1;i--){///先处理查询,再更新if(!qy[i].empty()){for(int j=0;j<qy[i].size();j++){int qf=qy[i][j].first,qs=qy[i][j].second;if(qf>val[i])ans[qs]=cnt[i]+sum(maxn-1)-sum(qf)+1;elseans[qs]=cnt[i]+sum(maxn-1)-sum(val[i]);}}while(r>=l&&b[i]>=Sk[r]){add(Sk[r],-1);r--;///后退}Sk[++r]=b[i];///先进去add(b[i],1);}for(int i=1;i<=q;i++) printf("%d\n",ans[i]);}return 0;
}