https://codeforces.com/contest/1080/problem/F

题意

有k个区间，区间的种类有n种，有m个询问（n,m<=1e5,k<=3e5),每次询问a,b,x,y，代表对于种类编号为[a,b]的每一种区间，是否都存在一个区间x<=l,r<=y，输出yes or no

思路

• 现将区间按左端点从小到大排序，对于每一个询问首先找出第一个左端点大于x的区间，然后看[a,b]中最大的右端点是否>y即可
• 需要一颗以种类编号为下标，右端点为权值的主席树，维护种类[a,b]的最大右端点值
• 假如找出了第一个左端点大于x的区间，怎么知道后面的区间的左端点一定<=y?
  • 因为每个种类上的点记录的是本种类点的最小右端点，假如左端点>y,则这个区间的右端点一定大于>y,所以不用担心这一类区间会被计算在内
• 怎么保证本种类左端点>=x的区间，最小的右端点一定>=x？
  • 排好序后，反着建树

#include<bits/stdc++.h>

#define M 300005

#define inf 0x3f3f3f3f

using namespace std;

int st[M],ma[M],rt[M*40],ls[M*40],rs[M*40],vl[M*40];

int pos,n,m,k,i,a,b,x,y,cnt,ans;

struct N{

    int l,r,p;

}p[M];

bool cmp(N a,N b){

    return a.l<b.l;

}

void ud(int pre,int &o,int l,int r,int pos,int val){

     if(pre==o){o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre];}

     if(l==r){vl[o]=val;return;}

     int mid=(l+r)/2;

     if(pos<=mid)ud(ls[pre],ls[o],l,mid,pos,val);

     else ud(rs[pre],rs[o],mid+1,r,pos,val);

     vl[o]=max(vl[ls[o]],vl[rs[o]]);

}

int qy(int o,int l,int r,int L,int R){

    int mid=(l+r)/2;

    if(!o)return inf;

    if(L<=l&&r<=R)return vl[o];

    if(R<=mid)return qy(ls[o],l,mid,L,R);

    if(L>mid)return qy(rs[o],mid+1,r,L,R);

    return max(qy(ls[o],l,mid,L,R),qy(rs[o],mid+1,r,L,R));

}

int main(){

    cin>>n>>m>>k;

    memset(ma,inf,sizeof(ma));vl[0]=inf;

    for(i=1;i<=k;i++)scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].p);

    sort(p+1,p+k+1,cmp);

    for(i=1;i<=k;i++)st[i]=p[i].l;

    st[k+1]=inf;

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

        rt[i]=rt[i+1];

        if(ma[p[i].p]>p[i].r){

           ud(rt[i+1],rt[i],1,n,p[i].p,p[i].r);

           ma[p[i].p]=p[i].r;

        }

    }  

    for(i=0;i<m;i++){

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

        pos=lower_bound(st+1,st+k+2,x)-st;

        if(pos==k+1)ans=inf;

        else ans=qy(rt[pos],1,n,a,b);

        if(ans<=y)printf("yes\n");else printf("no\n");

        fflush(stdout);

    }

}