P3374 和线段树有关的强分类讨论

褚觅山 · 2021-05-17 18:36:07 · 个人记录

搞清楚题意后竟然一发AC。。。。。。

#include<iostream>
#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
int n,m;
struct node1{
    long long year,ruin;
}dat[50005];
bool operator<(node1 a,node1 b){
    return a.year<b.year;
}
map<long long,int> Map;
int v[50005];
void findv(){
    int p=1;
    v[1]=1;
    for(int i=2;i<=n;++i){
        if(dat[i].year==dat[i-1].year+1){
            v[i]=p;
        }else{
            p=i;
            v[i]=p;
        }
    }
    return;
}
struct node2{
    int l,r;
    long long val;
}tree[8*50005];
void build(int p,int l,int r){
    tree[p].l=l;
    tree[p].r=r;
    if(l==r){
        tree[p].val=dat[l].ruin;
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].val=max(tree[p*2].val,tree[p*2+1].val);
    return;
}
long long Ask(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r)
        return tree[p].val;
    int mid=(tree[p].l+tree[p].r)>>1;
    long long res=0;
    if(mid>=l)
        res=Ask(p*2,l,r);
    if(mid+1<=r)
        res=max(res,Ask(p*2+1,l,r));
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&dat[i].year,&dat[i].ruin);
        Map[dat[i].year]=i;
    }
    findv();
    scanf("%d",&m);
    long long y1,y2;
    build(1,1,n);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&y1,&y2);
        if(Map.find(y2)==Map.end()){
            if(Map.find(y1)==Map.end()){
                printf("maybe\n");
                continue;
            }
            node1 tt;
            tt.year=y2;
            int p2=(lower_bound(dat+1,dat+1+n,tt)-dat)-1,p1=Map[y1];
            if(p1==p2){
                printf("maybe\n");
                continue;
            }
            long long res=Ask(1,p1+1,p2);
            if(res<dat[p1].ruin)
                printf("maybe\n");
            else
                printf("false\n");
            continue;
        }else if(Map.find(y1)==Map.end()){
            int p2=Map[y2];
            node1 tt;
            tt.year=y1;
            int p1=lower_bound(dat+1,dat+1+n,tt)-dat;
            if(p1==p2){
                printf("maybe\n");
                continue;
            }
            long long res=Ask(1,p1,p2-1);
            if(res<dat[p2].ruin)
                printf("maybe\n");
            else
                printf("false\n");
            continue;
        }
        int p1=Map[y1],p2=Map[y2];
        if(p2<p1){
            printf("false\n");
            continue;
        }else if(p1==p2){
            printf("true\n");
            continue;
        }else if(p2==p1+1){
            if(dat[p2].ruin>dat[p1].ruin){
                printf("false\n");
            }else if(dat[p1].year+1==dat[p2].year)
                printf("true\n");
            else
                printf("maybe\n");
            continue;
        }
        if(dat[p2].ruin>dat[p1].ruin){
            printf("false\n");
            continue;
        }
        long long res1=Ask(1,p1+1,p2),res2=Ask(1,p1+1,p2-1);
    //  cout<<"res1 "<<res1<<" res2 "<<res2<<endl; 
        if(res1>res2){
            if(v[p2]<=p1)
                printf("true\n");
            else
                printf("maybe\n");
        }else
            printf("false\n");
    }
    return 0;
}