ZOJ 3518 Unsafe Factor(区间覆盖:离散化)

ZOJ 3518 Unsafe Factor(区间覆盖:离散化)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3518

题意:

给你[0,L]的初始区间,然后依次给你n1+n2个区间,每次都会使得一个区间内所有的整点位置的值+1.问你最终连续值1的区间最长为多少?

分析:

典型的离散化问题(用线段树貌似更好理解一点). 离散化问题最关键的地方就如何把原问题的一个个大区间转化为一个个的子区间 且任意子区间不重叠且任何一个原来的大区间都可由特定的多个子区间正好构成.

假如现在有输入区间为[1,3]和[2,5]. 那么我们能简单的把子区间分为[1,2] [2,3] 和[3,5]吗? 不能,因为2,和3都代表了一个点(一小段区间),所以[1,2]和[2,3]是有重叠部分的. 所以这里我们要转换思路了.

我们首先把输入区间变成[1,4) 和[2,6)(半闭半开区间), 那么子区间由输入区间的x1和x2值排序得到为[1,2) [2,4) [4,6) 正好是3段不重叠的子区间,且完美覆盖了原始输入区间.

做完上面一部分,我们只需要一次遍历原始区间,比如[1,4),然后找出该区间能覆盖的子区间首坐标的下标(这里是0和2),然后对于0和1子区间(不含2子区间)执行覆盖操作即可.

最终我们可直接求出最长连续值为1的区间段.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400000+10;

struct Node//线段
{
    int x1,x2;
}nodes[maxn];

int n;      //线段数目
int x[maxn];//x坐标
int num;    //x坐标数目

int main()
{
    int L,n1,n2;
    while(scanf("%d%d%d",&L,&n1,&n2)==3)
    {
        n=n1+n2;
        num=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&nodes[i].x1,&nodes[i].x2);
            ++nodes[i].x2;
            x[num++]=nodes[i].x1;
            x[num++]=nodes[i].x2;
        }
        sort(x,x+num);
        num=unique(x,x+num)-x;

        bool mp[maxn];//标记每一段区间
        memset(mp,0,sizeof(mp));
        for(int i=0;i<n;++i)
        {
            int L_x=lower_bound(x,x+num,nodes[i].x1)-x;
            int R_x=lower_bound(x,x+num,nodes[i].x2)-x;

            for(int j=L_x;j<R_x;++j)
                mp[j] ^= true;
        }
        int sum=0;
        for(int i=0;i<num-1;++i)if(mp[i])
        {
            int cur=0;
            while(i<num-1 && mp[i])
            {
                cur+= x[i+1]-x[i];
                ++i;
            }
            sum=max(sum,cur);
        }
        printf("%d\n",sum);
    }
    return 0;
}