70pts,求调
查看原帖
70pts,求调
531811
luoguo0921楼主2024/7/15 08:55
#include<bits/stdc++.h>
using namespace std;
const int N=4000000;
int tr[N];
int a[N],b[N];//a大于的数,b小于的数 
int c[64],d[64];
int n,m;
void f(int x,int dep){
	if(dep==n)
	{
		if(tr[x]==1){
			a[x]=1;
			b[x]=2;
		}
		else{
			b[x]=1;
			a[x]=2;
		} 
		c[n-dep+2]=min(c[n-dep+2],a[x]);
		d[n-dep+2]=min(c[n-dep+2],b[x]);
		return;
	}
	f(x*2,dep+1);
		f((x*2)+1,dep+1);
	if(tr[x]==1)
	{
		b[x]=b[x*2]+b[x*2+1];
		a[x]=min(a[x*2],a[x*2+1]);
	}
	else{
		a[x]=a[x*2]+a[(x*2)+1];
		b[x]=min(b[x*2],b[x*2+1]);
	}
	c[n-dep+2]=min(c[n-dep+2],a[x]);
	d[n-dep+2]=min(d[n-dep+2],b[x]);
}
int main(){
	cin>>n>>m;

	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,61,sizeof(c));
	memset(d,61,sizeof(d));
	c[0]=0;d[0]=0;
	for(int i=1;i<=(1<<n)-1;i++){
		cin>>tr[i];
	}
	f(1,1);
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(y==1||x<=(1<<n)-c[y]+1&&d[y]<=x)
			cout<<"Yes"<<endl;
		else
		cout<<"No"<<endl;
	}
}
2024/7/15 08:55
加载中...