题解

#include<bits/stdc++.h>
using namespace std;
const int N=50005,M=200005,B=230;
int n,m,blk,a[N],c[N],ans[M];
struct query{int id,m,k;}q[M];
bool cmp(query a,query b){return a.m<b.m;}
void upd(int x,int d){while(x<=n)c[x]+=d,x+=x&-x;}
int qry(int x){int y=0;while(x)y+=c[x],x-=x&-x;return y;}
struct Yang{
	int f,a[B][N];
	void insert(int x,int y,int v){
		if(x>blk)return;
		int l=1,r=min(y,a[x][0]+1),mid;
		while(l<r){
			mid=l+r>>1;
			if(f^(a[x][mid]<v))r=mid;
			else l=mid+1;
		}
		swap(a[x][l],v),a[x][0]=max(a[x][0],l);
		if(v)insert(x+1,l,v);
		else if(f&&l>blk)upd(l,1);
		else if(!f)upd(x,1);
	}
}mx,my;
int main(){
	my.f=1;
	scanf("%d%d",&n,&m),blk=sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].m,&q[i].k),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	for(int i=1,j=1;i<=m;i++){
		while(j<=q[i].m)mx.insert(1,n+1,a[j]),my.insert(1,n+1,a[j]),j++;
		ans[q[i].id]=qry(q[i].k);
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}