hdu 5124 lines （線段樹+離散化）

lines

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 620 Accepted Submission(s): 288


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 T(1≤T≤100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.
Output For each case, output an integer means how many lines cover A.
Sample Input

2
5
1 2 
2 2
2 4
3 4
5 1000
5
1 1
2 2
3 3
4 4
5 5

Sample Output

3
1

題意就是求區間的最大值的，可以用線段樹+離散化處理，使得坐標區間變小。

如[2,5],[3, 100]離散化後，先排序{2,3,5,100}，對應下標值可以變為{1，2,3,4} ，對應時可以去重（見代碼）。

區間變為[1,3],[2,4],區間的大小關系不變。

#include
#include
#include
#include
#include
using namespace std;
#define N 200005
#define ll __int64
struct node
{
    int l,r;
    int v,f;   //v記錄最大值，f記錄當前層累積的值
}f[N*3];
struct st     //記錄原始區間的左右端點
{
    int x,id;
}a[N];
int pos[N/2][2];  //記錄區間端點
bool cmp(st a,st b)
{
    return a.x>1;
    creat(tmp,l,mid);
    creat(tmp|1,mid+1,r);
}

void update(int t,int l,int r)
{
    int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
    if(f[t].l==l&&f[t].r==r)
    {
        f[t].v++;
        f[t].f++;
        return ;
    }
    if(f[t].f)      //下壓操作push_down,每次加上累計值
    {
        f[tmp].v+=f[t].f;
        f[tmp|1].v+=f[t].f;
        f[tmp].f+=f[t].f;
        f[tmp|1].f+=f[t].f;
        f[t].f=0;          //標記值f置為零
    }
    if(r<=mid)
        update(tmp,l,r);
    else if(l>mid)
        update(tmp|1,l,r);
    else
    {
        update(tmp,l,mid);
        update(tmp|1,mid+1,r);
    }
    f[t].v=max(f[tmp].v,f[tmp|1].v);  //上壓操作push_up
}
int main()
{
    int T,i,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i