abc c求助
  • 板块学术版
  • 楼主HZHDCM
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/11/30 22:09
  • 上次更新2024/12/1 09:05:51
查看原帖
abc c求助
817681
HZHDCM楼主2024/11/30 22:09

rt,一开始降智写了线段树,但是不知道为什么wa了一个点,虽然后面换写法A了,但是求hack

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int b[N],n,m,a[N];
int t[N<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void Push_up(int p){
	t[p]=min(t[ls(p)],t[rs(p)]);
}
void Build(int l,int r,int p){
	if(l==r){
		t[p]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	Build(l,mid,ls(p));
	Build(mid+1,r,rs(p));
	Push_up(p);
}
int Query(int l,int r,int p,int x){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(t[ls(p)]<=x)return Query(l,mid,ls(p),x);
	if(t[rs(p)]<=x)return Query(mid+1,r,rs(p),x);
	return -1;
}
void solve(){
	cin>>n>>m;
//	memset(b,0x3f,sizeof(b));
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	Build(1,n,1);
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		cout<<Query(1,n,1,x)<<endl;
	}
}
int main(){
	solve();
	return 0;
}
2024/11/30 22:09
加载中...