ST表10pts求助
查看原帖
ST表10pts求助
752094
MornHus楼主2023/11/17 10:43
#include<bits/stdc++.h>
using namespace std;
#define maxn 50005
int n,m;
map<int,int>flat;
int st[maxn][20];

inline int query(int l,int r){
    if(r<l){
        swap(l,r);
    }
    int k=log2(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int y;
        cin>>y>>st[i][0];
        flat[y]=i;
    }
    for(int k=1;(1<<k)<=n;k++){
        for(int i=1;i+(1<<k)-1<=n;i++){
            st[i][k]=max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
        }
    }
    cin>>m;
    int y,x;
    for(int i=1;i<=m;i++){
        cin>>y>>x;
        int l=flat[y],r=flat[x];
        int temp;
        if(y>=x){
            cout<<"false\n";
        }else if(!l&&!r){
            cout<<"maybe\n";
        }else if( (l && !r) || (!l && r) ){
            if(r){
                temp=query(l+1,r-1);
                if(temp<st[r][0]){
                    cout<<"maybe\n";
                }else{
                    cout<<"false\n";
                }
            }else {
                temp=query(l+1,r-1);
                if(temp<st[l][0]){
                    cout<<"maybe\n";
                }else{
                    cout<<"false\n";
                }
            }
        }else if((l&&r)&&(x-y)!=(r-l)){
            temp=query(l+1,r-1);
            if(st[l][0]<st[r][0]){
                cout<<"false\n";
            }else if(temp<st[r][0]&&temp<st[l][0]){
                cout<<"maybe\n";
            }else{
                cout<<"false\n";
            }
        }else{
            temp=query(l+1,r-1);
            if(st[l][0]<st[r][0]){
                cout<<"false\n";
            }else if(temp<st[r][0]&&temp<st[l][0]){
                cout<<"true\n";
            }else{
                cout<<"false\n";
            }
        }
    }
    return 0;
}
/*

考虑使用st表

首先离散化

map<年份,序号>;

分情况讨论:

x,y未知,直接maybe

有一个未知,判断

全已知,中间有未知,判断

全已知,判断

*/
2023/11/17 10:43
加载中...