16 청화추연마법학교(모대)

제목 링크: AcWing 1327 제목: 중국어 제목.
분명히 시간축을 모팀의 한 세트로 하면 된다.단일 이동 복잡도 l o g 2 n log2n log2 n, 모대 자체 n\sqrt n*n n\n n n n n n n n n n n n n n n n n n n n n n n n n n n n *\sqrt n*lognn∗n∗ log2n, 카드 항상.
이 코드는 정렬 방식을 변경하는 AC 코드입니다(잘 모름).

#pragma GCC optimize(2)
#include
using namespace std;

typedef long long ll;

const int maxn=5e4+7;
int Max[maxn<<2|1];
int who[maxn<<2|1];
int lazy[maxn<<2|1];

void pushdown(int l,int r,int k){
     
    if(lazy[k]){
     
        lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k];
        Max[k<<1]+=lazy[k],Max[k<<1|1]+=lazy[k];
        if(!who[k<<1]) who[k<<1]=l;
        if(!who[k<<1|1]) who[k<<1|1]=(l+r>>1)+1;
        lazy[k]=0;
    }
}

void pushup(int k){
     
    if(Max[k<<1]>=Max[k<<1|1]) Max[k]=Max[k<<1],who[k]=who[k<<1];
    else Max[k]=Max[k<<1|1],who[k]=who[k<<1|1];
}

void build(int l,int r,int k){
     
    if(l==r){
     
        who[k]=l;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,k<<1),build(mid+1,r,k<<1);
}
void upd(int l,int r,int k,int L,int R,int val){
     
    if(l>=L&&r<=R){
     
        Max[k]+=val;
        lazy[k]+=val;
        if(!who[k]) who[k]=l;
        return ;
    }
    pushdown(l,r,k);
    int mid=l+r>>1;
    if(L<=mid) upd(l,mid,k<<1,L,R,val);
    if(R>mid) upd(mid+1,r,k<<1|1,L,R,val);
    pushup(k);
}

int L[maxn],R[maxn],n,m;
void add(int id){
     
    upd(1,50000,1,L[id],R[id],1);
}

void del(int id){
     
    upd(1,50000,1,L[id],R[id],-1);
}

struct Node{
     
    int l,r,id,k;
}a[maxn];
int res[maxn],num[maxn];
int T;
bool cmp(Node a,Node b){
     
    if(a.k!=b.k) return a.k<b.k;
    return a.r<b.r;
}

/*
bool cmp(Node a,Node b){
    if(a.l / T == b.l / T){
        return (a.l/T) % 2 == 0 ? a.r < b.r : a.r > b.r;
    }
     return a.l < b.l;
}
*/

int main(){
     
    //cout<
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&L[i],&R[i]);
    scanf("%d",&m);
    T=sqrt(n);
    for(int i=1;i<=m;++i) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i,a[i].k=a[i].l/T+(a[i].l%T?1:0);
    sort(a+1,a+1+m,cmp);
    int l=1,r=0;
    build(1,50000,1);
    for(int i=1;i<=m;++i){
     
        int L=a[i].l,R=a[i].r;
        while(r<R) add(++r);
        while(r>R) del(r--);
        while(l>L) add(--l);
        while(l<L) del(l++);
        res[a[i].id]=who[1],num[a[i].id]=Max[1];
    }
    for(int i=1;i<=m;++i) printf("%d %d
",res[i],num[i]);

    return 0;
}