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
");else printf("no
");
fflush(stdout);
}
}