求助,死活wa3##,但是把st表开大一点就AC了,求助原因
查看原帖
求助,死活wa3##,但是把st表开大一点就AC了,求助原因
676619
finalSTian楼主2023/4/10 12:23
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
int y[50005];
int n;

template<typename T,bool isMin>
struct SpareTable{
      int n,m;
      vector<vector<T>> f;
      SpareTable(int n): n(n),m(__lg(n)),f(m+1,vector<T>(n+1)){ }
      /*
      把这里n+1,开成n+1e5就过了。没懂啊
  
      */
      SpareTable(vector<T> init):SpareTable((int)init.size()){
      	for(int i=1;i<=n;i++) f[0][i]=init[i-1];
      	for(int j=1;j<=m;j++){
      		for(int i=1;i+(1<<j)-1<=n;i++){
      			if(isMin) f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
      			else f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
      		}
      	}
      }
      T query(int l,int r){
      	if(l>r) return 0;
      	int k=__lg(r-l+1);
      	if(isMin) return min(f[k][l],f[k][r-(1<<k)+1]);
      	else return max(f[k][l],f[k][r-(1<<k)+1]);
      	      }
};
int fl(int x)//二分出第一个不大于x的位置
{
	int L=0,R=n+1,mid;
	while(L<R)
	{
	int mid=(L+R+1)>>1;
		if(y[mid]<x)
		  L=mid;
		else R=mid-1;
	}
	return L;
}
void solved(){
	cin>>n;
	vector<int> a(n+1),b(n+1),init(n);
	map<int,int> mp;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		y[i]=a[i];
		mp[a[i]]=i;
		init[i-1]=b[i];
	}
	int m;
	cin>>m;
	SpareTable<int,false> st(init);
	while(m--){
		int l,r;
		cin>>l>>r;
		if(mp.find(r)==mp.end()){
			if(mp.find(l)==mp.end()){
				cout<<"maybe"<<endl;
				continue;
			}
		    //int idx=lower_bound(a.begin()+1,a.end(),r)-a.begin();
		    //if(a[idx]>r) idx--;
			if(st.query(mp[l]+1,fl(r))<b[mp[l]]){
				cout<<"maybe"<<endl;
				continue;
			}
			cout<<"false"<<endl;
            continue;
		}
		else if(mp.find(l)!=mp.end()){
			if(b[mp[l]]<b[mp[r]]){
				cout<<"false"<<endl;
				continue;
			}
			if(st.query(mp[l]+1,mp[r]-1)>=b[mp[r]]){
                cout<<"false"<<endl;
                continue;
			}
			if(r-l==mp[r]-mp[l]){
				cout<<"true"<<endl;
				continue;
			}
			cout<<"maybe"<<endl;
			continue;
		}
		else{
			 //int idx=lower_bound(a.begin()+1,a.end(),r)-a.begin();
			 //if(a[idx]>l) idx--;
			if(st.query(fl(l)+1,mp[r]-1)>=b[mp[r]]){
				cout<<"false"<<endl;
				continue;
			}
			cout<<"maybe"<<endl;
		}

	}
}
signed main(){
	ios::sync_with_stdio(false );
	cin.tie(0);
	cout.tie(0);

		solved();

}
2023/4/10 12:23
加载中...