HDU5124：lines（线段树+离散化）或（离散化思想）

http://acm.hdu.edu.cn/showproblem.php?pid=5124

Problem Description

John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.

Input

The first line contains a single integer

Output

For each case, output an integer means how many lines cover A.

Sample Input

1 2

2 2

2 4

3 4

5 1000

2 2

3 3

4 4

5 5

Sample Output

题目解析：

题意：给定 n 个区间，问最多重复的子区间？

题解：（离散化思想）讲所有的数都排个序，将区间的左值定为 1 ，右值定为 -1 ，这样对所有的数搜一遍过去找最大的值即可；或者用线段树+离散化。

一：线段树

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define N 100010
using namespace std;
struct  li
{
    int x,y;
}line[N];
struct node
{
    int l,r;
    int lz;
}q[8*N];
int n,tt,X[2*N];
int maxx;
void build(int l,int r,int rt)
{
    q[rt].l=l;
    q[rt].r=r;
    q[rt].lz=0;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    return ;
}
void pushdown(int rt)
{
    if(q[rt].lz)
    {
        q[rt<<1].lz+=q[rt].lz;
        q[rt<<1|1].lz+=q[rt].lz;
        q[rt].lz=0;
    }
}
void update(int lf,int rf,int l,int r,int rt)
{
    if(lf<=l&&rf>=r)
    {
        q[rt].lz+=1;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(lf<=mid) update(lf,rf,l,mid,rt<<1);
    if(rf>mid) update(lf,rf,mid+1,r,rt<<1|1);
    return ;
}
void query(int l,int r,int rt)
{

    if(l==r)
    {
       maxx=max(maxx,q[rt].lz);
       return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    query(l,mid,rt<<1);
    query(mid+1,r,rt<<1|1);
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tt=0;
        maxx=-1;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&line[i].x,&line[i].y);
            X[tt++]=line[i].x;
            X[tt++]=line[i].y;
        }
        sort(X,X+tt);
        int sum=unique(X,X+tt)-X;
        build(1,sum,1);
        for(int i=0;i<n;i++)
        {
            int le=lower_bound(X,X+sum,line[i].x)-X+1;
            int re=lower_bound(X,X+sum,line[i].y)-X+1;
            if(le<=re)  update(le,re,1,sum,1);
        }
        query(1,sum,1);
        printf("%d
",maxx);
    }
    return 0;
}

二：离散化：思路：可以把一条线段分出两个端点离散化，左端点被标记为-1，右端点被标记为1，然后排序，如果遇到标记为-1，cnt++，否则cnt--;找出cnt的最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200010
using namespace std;

struct node
{
    int x,c;
    bool operator<(const node &a)const
    {
        return (x<a.x)||(x==a.x&&c<a.c);
    }
}p[maxn];

int t;
int n;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            int s,e;
            scanf("%d%d",&s,&e);
            p[i*2].x=s;
            p[i*2].c=-1;
            p[i*2+1].x=e;
            p[i*2+1].c=1;
        }
        sort(p,p+2*n);
        int cnt=0; int ans=0;
        for(int i=0; i<2*n; i++)
        {
            if(p[i].c==-1)
            {
                cnt++;
            }
            else
                cnt--;
            ans=max(ans,cnt);
        }
        printf("%d
",ans);
    }
    return 0;
}

可惜做BC时，这两种方法都没想出来，悲催！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#define PI acos( -1.0 )
using namespace std;
typedef long long ll;

const int NO = 1e5 + 10;
struct ND
{
    int x, y;
}st[NO<<1];
int n;

bool cmp( const ND &a, const ND &b )
{
    if( a.x == b.x ) return a.y > b.y;
    return a.x < b.x;
}

int main()
{
    int T;
    scanf( "%d",&T );
    while( T-- )
    {
        scanf( "%d", &n );
        int cur = 0;
        for( int i = 0; i < n; ++i )
        {
            scanf( "%d", &st[cur].x );
            st[cur++].y = 1;
            scanf( "%d", &st[cur].x );
            st[cur++].y = -1;
        }
        sort( st, st+cur, cmp );
        int ans = 0;
        int Max = 0;
        for( int i = 0; i < cur; ++i )
        {
            ans += st[i].y;
            Max = max( ans, Max );
        }
        printf( "%d
", Max );
    }
    return 0;
}

View Code