可持久化线段树（cf1080F）

大佬博客 https://www.cnblogs.com/zinthos/p/3899565.html

题目：https://codeforces.com/problemset/problem/1080/F

题目大意：

　　给你k个线段，每个线段属于一个集合（n），每次查询a,b,x,y，求[a,b]的集合是否都存在一个区间[l,r]使得l<=x&&r>=y

解法：

　　题目等同于，对于[a,b]中的每一个集合，左端点大于x的线段中最小的右端点，的最大值是否<=y；

　　对线段排序（根据左端点l值），根据线段左端点值l由大到小依次插入更新线段树（插入时维护最小值），线段树维护[1,n]上的最大的区间右端点值（所有的集合的最小右端点的最大值），每次更新需要复制的节点数最多为log个，端点数最多为nlogn

#include<bits/stdc++.h>

using namespace std;

#define freread freopen("input.txt","r",stdin);

#define frewrite freopen("output.txt","w",stdout);

typedef long long ll;

const int maxn=3e5+;

const int inf=(1LL<<)-;

int n,m,k,ar[maxn];

struct node{

    int l,r,mx;

}no[];

struct data{

    int l,r,v;

    operator < (const data& other){

        return l<other.l;

    }

    void prin(){

        cout<<"da = "<<l<<" "<<r<<" "<<v<<endl;

    }

}da[maxn];

int root[maxn],tot=;

void newNode(int& u,int p){

    u=++tot;

    no[u]=no[p];

}

void push(int x){

    no[x].mx=max(no[no[x].l].mx , no[no[x].r].mx);

}

void build(int l,int r,int &o){

    newNode(o,);

    if(l==r){

        no[o].mx=inf;

        return ;

    }

    int mid=l+r>>;

    build(l,mid,no[o].l);

    build(mid+,r,no[o].r);

    push(o);

}

void ensert(int l,int r,int& o,int pre,int a,int b){

    newNode(o,pre);

    if(l==r){

        no[o].mx=min(no[o].mx, b);

        return ;

    }

    int mid=l+r>>;

    if(a<=mid)ensert(l,mid,no[o].l,no[o].l,a,b);

    else ensert(mid+,r,no[o].r,no[o].r,a,b);

    push(o);

}

int que(int l,int r,int o,int a,int b){

    if(l==a && r==b){

        return no[o].mx;

    }

    int mid=l+r>>;

    int ans=;

    if(a<=mid)ans=max(ans, que(l,mid,no[o].l,a,min(b,mid)));

    if(b>mid)ans=max(ans, que(mid+,r,no[o].r,max(a,mid+),b));

    return ans;

}

int findpos(int x){

    int l=,r=k+;

    while(l<r){

        int mid=(l+r)>>;

        if(da[mid].l>=x)r=mid;

        else l=mid+;

    }

    return l;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=k;i++){

        scanf("%d%d%d",&da[i].l,&da[i].r,&da[i].v);

    }

    sort(da+,da+k+);

    build(,n,root[k+]);

    for(int i=k;i>=;i--){

        ensert(,n,root[i],root[i+],da[i].v,da[i].r);

    }

    da[k+].l=1e9+;

    while(m--){

        int a,b,x,y;

        scanf("%d%d%d%d",&a,&b,&x,&y);

        int ans=que(,n,root[findpos(x)],a,b);

        puts(ans<=y? "yes":"no");

        fflush(stdout);

    }

    return ;

}

巴特西

可持久化线段树（cf1080F）

最新文章

热门文章