题解

全部评论 4

• 

  I1\

  

  置顶

  #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]);
  }
  

  2026-04-21 来自 浙江

  1
• 

  元子

  

  344

  2026-04-14 来自 浙江

  1
• 

  I1\

  

  c

  2026-04-14 来自 浙江

  1
• 

  

  请输入文本.

  

  不发题解区发讨论和溢位

  2026-04-21 来自 上海

  0