LOJ 6270 题解

· · 个人记录

题目大意

给定n个区间，q次询问区间[l,r]包含的长度大于等于k的区间个数

0≤n,q,l,r≤5e5

由于求的是包含关系且l,r数据在可接受范围内，考虑以长度为统计的关键量，那么我们排序后首先分别将给定区间以及询问区间由长度从小到大排序，统计上该给定区间，由于包含说明给定区间小于等于询问区间，也就是说我们这么排序不会出现漏解。

那么如何去统计？由于给定区间小于等于该询问区间，说明不会出现给定区间左边超过该询问区间左端，右边超过该询问区间右端的情况，否则该给定区间长度显然大于该询问区间，与前面排序不成立。这是一个很重要的性质，说明在左端点前出现过的一定在右端点出现过

比如![这是一个图] 不会出现这样r端点未统计过但减去l端点情况

因为这样所以可以记录到每个位置左、右端点数量，那么该询问区间包含的数量就是到该询问区间右端点的右端点数量-该询问区间左端点-1的左端点数量，我们设该询问区间左右端点分别为L,R,query_l（idx）为查询当前idx以前（包括idx）的左端点数量，query_r(idx)为查询当前idx以前（包括idx）的右端点数量,sum为[L,R]区间包含的区间个数

所以可以得到 sum=query_r(R)-query_l(L-1);

But 题目问的可是长度大于等于k的区间个数，其实在我们上面统计的时候统计的都是长度小于等于当前的区间，如果我们在询问区间里每个加入一个配套的长度为k-1的区间，答案再减去这个就可以，操作起来也不困难，读入时顺便加入，再附一个权值1/-1，每次加时候乘上权值即可

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,t,cnt;
int ans[500050],lc[500050],rc[500050];
struct aaa{
    int l,r,len;
}a[500050];
bool cmp(aaa a,aaa b){
    return a.len<b.len;
}
struct bbb{
    int l,r,len,vl,idx;
}q[1000050];
bool cmp1(bbb a,bbb b){
    return a.len<b.len;
}
int lowbit(int x){
    return x&(-x);
}
int query(int x,int c[]){
    int num=0;
    while(x){
        num+=c[x];
        x-=lowbit(x);
    }
    return num;
}
void add(int x,int c[]){
    while(x<=n){
        ++c[x];
        x+=lowbit(x);
    }
}
int main(){
    freopen("interval.in","r",stdin);
    freopen("interval.out","w",stdout);
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].len=a[i].r-a[i].l;
    sort(a+1,a+1+n,cmp);
    int x,y,z;
    for(int i=1;i<=t;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(y-x+1<z) continue;
        q[++cnt]=(bbb){x,y,y-x,1,i};//加上l-r之间区间数目 
        q[++cnt]=(bbb){x,y,z-1,-1,i};//减去l-r之间小于k区间数目
    }
    sort(q+1,q+1+cnt,cmp1);
    for(int i=1,j=1;i<=cnt;i++){
        while(j<=n&&a[j].len<=q[i].len){
            add(a[j].l,lc);
            add(a[j].r,rc);//以i为为右端点区间数 
            j++;
        }
        ans[q[i].idx]+=q[i].vl*(query(q[i].r,rc)-query(q[i].l-1,lc));
    }
    for(int i=1;i<=t;i++) cout<<ans[i]<<endl;
    cout<<endl;
    return 0;
}