The Union of k-Segments – CodeForces 612D – 差分

来源: The Union of k-Segments – CodeForces 612D – Virtual Judge

题目大意:n个线段覆盖区间,问被覆盖>=k次的区间个数。
这些个毒瘤出题人总能把差分玩出花来。。。
你说你统计区间怎么还能统计出 1 1来,,,这不是个点么emmm
经过激烈的思考,,,我依然没能把差分调出来然后百度一搜发现。。。把区间和点分开各跑一遍就OK了。。。。
具体来讲就是用两个差分数组,一个如果覆盖a~b就在a处+1,b处-1,另一个就在a处+1,b+1处-1,这样的话右端点和边的区别就是端点处第一个数组是比第二个数组小的,那么判断这个点的a小于k且b大于k就一定是一个右端点了,再判断一下是否与前面的线段相连即可。
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l,r;
} e[1000010],out[1000010];

int a[2000010];
int mp[2000020],mpp[2000020];

bool cmp(node aa,node bb)
{
    if(aa.l==bb.l)
        return aa.r<bb.r;
    else return aa.l<bb.l;
}

int main()
{
    //ios::sync_with_stdio(false);
    unordered_map<int,int>q,qq;
    int n,k;
    scanf("%d%d",&n,&k);
    //cin>>n>>k;
    int tot=1;
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&e[i].l,&e[i].r);
        //cin>>e[i].l>>e[i].r;
        a[tot++]=e[i].l;
        a[tot++]=e[i].r;
    }
    sort(a+1,a+tot+1);
    tot=unique(a+1,a+tot+1)-a;
    for(int i=1; i<tot; i++)
    {
        q[a[i]]=i;
        qq[i]=a[i];
    }
    for(int i=0; i<n; i++)
    {
        mp[q[e[i].l]]++;
        mp[q[e[i].r]]--;
        mpp[q[e[i].l]]++;
        mpp[q[e[i].r]+1]--;
    }
    for(int i=1; i<=tot; i++)
    {
        mp[i]+=mp[i-1];
        mpp[i]+=mpp[i-1];
    }
    int ans=0,f=0,cnt=0;
    for(int i=1; i<=tot; i++)
    {
        if(f==0)
        {
            if(mp[i]>=k)
            {
                ans++;
                f=1;
                out[cnt].l=qq[i];
            }
        }
        else
        {
            if(mp[i]<k)
            {
                out[cnt++].r=qq[i];
                f=0;
            }
        }
    }
    for(int i=1;i<=tot;i++)
    {
        if(mp[i-1]<k&&mp[i]<k&&mpp[i]>=k)
        {
            out[cnt].l=qq[i];
            out[cnt++].r=qq[i];
        }
    }
    printf("%d\n",cnt);
    //cout<<cnt<<endl;
    sort(out,out+cnt,cmp);
    for(int i=0;i<cnt;i++)
    {
        printf("%d %d\n",out[i].l,out[i].r);
        //cout<<out[i].l<<" "<<out[i].r<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注