HDU 5124, 선분 수 가산 화

물 문제 하나, 하지만 자신 이 너무 약 하기 때문에 오랫동안 썼 습 니 다. 선분 나무의 이해 가 좋 지 않 습 니 다. 지금까지 pushdown 의 정 수 를 잘 모 르 고 고양이 에 따라 호 랑 이 를 그 릴 줄 만 알 았 습 니 다. 앞으로 며칠 동안 물 문 제 를 푸 는 동시에 데이터 구 조 를 삽입 할 계획 입 니 다.
이 문제 의 이산 화 는 매우 간단 하 다. 바로 나타 난 점 에 대해 순 서 를 매기 면 된다 는 것 이다. 맵 같은 것 으로 마음대로 해 볼 수 있다. 이 문 제 는 욕심 산법 이 있 으 니 공부 하고 싶다 고 한다.마지막 으로 시간 을 보 내 는 것 도 주로 선분 나무 가 이해 가 안 돼 서 33951 마리, 33979 마리..........................................................

#include<stdio.h>
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include <cstring>
using namespace std;
const int MAX=1000000;

int arr[500005][2];
vector<int> v;
unordered_map<int,int> mp;
struct pr {
    int sum;
    int lazy;
    int left,right;					//    ，    rr,ll
}tr[MAX+10];
int n;
inline int ll(int k) {return 2*k;} 		 //     
inline int rr(int k) {return 2*k+1;}		 //     
inline int mid(int kk1,int kk2) {return (kk1+kk2)>>1;}
void pushdown(int k) {
    if (tr[k].lazy) {							//    ，   +=
        tr[ll(k)].sum+=tr[k].lazy*(tr[ll(k)].right-tr[ll(k)].left+1);
        tr[rr(k)].sum+=tr[k].lazy*(tr[rr(k)].right-tr[rr(k)].left+1);
        tr[ll(k)].lazy+=tr[k].lazy;
        tr[rr(k)].lazy+=tr[k].lazy;
        tr[k].lazy=0;
    }
}

void build(int k,int s,int t) {
    tr[k].left=s;tr[k].right=t;
    if(s==t) {tr[k].sum=0;return;}				//        
    build(ll(k),s,mid(s,t));
    build(rr(k),mid(s,t)+1,t);
    tr[k].sum=tr[ll(k)].sum+tr[rr(k)].sum;		//       max
}

void modify(int k,int s,int t,int x) {
    int l=tr[k].left,r=tr[k].right;
    if(l==s&&r==t) {		//(l==s&&r==t)
        tr[k].lazy+=x;
        tr[k].sum+=x*(r-l+1);
        return ;
    }
    pushdown(k);
    int mi=mid(l,r);
    if(t<=mi) modify(ll(k),s,t,x);
    else if(s>mi) modify(rr(k),s,t,x);
    else {
        modify(ll(k),s,mi,x);
        modify(rr(k),mi+1,t,x);
    }
    tr[k].sum=tr[ll(k)].sum+tr[rr(k)].sum;
}

int query(int k,int s,int t) {
    int l=tr[k].left,r=tr[k].right;
    if(l==s&&r==t) return tr[k].sum;
    pushdown(k);
    int mi=mid(l,r);
    int res=0;
    if (t<=mi) res+=query(ll(k),s,t);
    else if(s>mi) res+=query(rr(k),s,t);
    else res+=query(ll(k),s,mi)+query(rr(k),mi+1,t);
    return res;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        mp.clear();
        v.clear();
        memset(tr,0,sizeof(tr));
        for(int i=0;i<n;i++){
            scanf("%d%d",&arr[i][0],&arr[i][1]);
            v.push_back(arr[i][0]);
            v.push_back(arr[i][1]);
        }
        sort(v.begin(),v.end());
        int nn=(int)(unique(v.begin(),v.end())-v.begin());
        int ans=0;
        for(int i=0;i<nn;i++){
            mp[v[i]]=i+1;
        }
        unordered_map<int,int>::iterator it=mp.begin();
        build(1,1,nn);
        for(int i=0;i<n;i++){
            modify(1,mp[arr[i][0]],mp[arr[i][1]],1);
        }
        for(int i=1;i<=nn;i++){
            ans=max(ans,query(1,i,i));
        }
        cout<<ans<<endl;
    }
    return 0;
}