【HDU - 5124】 lines 【樹狀數組+離散化】

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)T(1≤T≤100)(the data for N>100N>100 less than 11 cases),indicating the number of test cases.

Each test case begins with an integer N(1≤N≤105)N(1≤N≤105),indicating the number of lines.

Next N lines contains two integers XiXi and Yi(1≤Xi≤Yi≤109)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

題意 ：給n個線段，問被覆寫次數最多的點，它被覆寫的次數。

首先資料大，我們可以用離散化。

想一下，被覆寫次數最多的點，一定是區間的端點處，然後，區間的更新（加減），查詢每一個端點，取最大就好。

線段樹也可以區間更新+維護區間最大值 做到，但是明顯樹狀數組更好用。

樹狀數組的常用操作

代碼

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define first fi
#define second se
#define  LL long long
#define fread() freopen("in.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define CLOSE() ios_base::sync_with_stdio(false)

const int MAXN = +;
const int MAXM = ;
const int mod = +;
const int inf = ;

struct BIT{
    int n;
    int c[MAXN<<];
    inline int lowbit(int x) { return x&(-x);}
    void add(int x,int val){
        for(int i=x;i<=n;i+=lowbit(i))
            c[i]+=val;
    }
    int sum(int x){
        int ans=;
        for(int i=x;i>;i-=lowbit(i)) 
            ans+=c[i];
        return ans;
    }
}bit;  
int le[MAXN],ri[MAXN];
int X[MAXN<<],size;

int main(){
    CLOSE();
//  fread();
//  fwrite();
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);size=;
        for(int i=;i<=n;i++){
            scanf("%d%d",&le[i],&ri[i]);
            X[size++]=le[i];X[size++]=ri[i];
        }
        sort(X,X+size); size=unique(X,X+size)-X;
        memset(bit.c,,sizeof(bit.c)); bit.n=size+;
        for(int i=;i<=n;i++){
            int l=lower_bound(X,X+size,le[i])-X+;
            int r=lower_bound(X,X+size,ri[i])-X+;
            bit.add(l,);bit.add(r+,-);
        }
        int ans=-;
        for(int i=;i<size;i++){  //周遊X數組就好，正好是所有的端點，同時還去重過了，很友善。
            int t=lower_bound(X,X+size,X[i])-X+;
            ans=max(ans,bit.sum(t));
        }
        printf("%d\n",ans);
    }   
    return ;
}