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

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

hdu 5124 lines （线段树+离散化）

lines