BZOJ 2653: middle | 주석 트 리

이 문 제 는 확실히 생각 하기 어렵다!주석 나 무 를 만 드 는 것 도 특별 해!2 분 의 답 을 고려 하여 현재 check 의 답 이 x 라면 x 와 같은 수의 공헌 은 1 이 고 나머지 공헌 은 - 1 이다. 그리고 총 공헌 > = 0 의 구간 이 존재 하 는 지 판단 하고 판단 하려 면 모든 수 에 하나의 라인 트 리 를 만 든 다음 에 MLE + TLE 를 직접 만 든 다음 에 우리 의 흑 과학기술 이 지속 가능 한 데이터 구조 주석 트 리 가 필요 하 다.먼저 모든 위 치 를 1 로 설정 한 다음 에 숫자 를 정렬 한 후에 작은 것 부터 큰 것 까지 매번 - 1 을 만 듭 니 다.아주 신의 나무 만 드 는 방식, 어 릴 때 부터 큰 삽입 수, 삽 입 된 가중치 가 이 수의 위치 입 니 다!!!마침 우리 의 정상 적 인 생각 과 는 반대로...

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
#define ll unsigned long long
#define N 20022
#define mx 1e9
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
struct W{int v,pos;}h[N];
int sum[N*500],lmx[N*500],rmx[N*500],ch[N*500][2];
int root[N],q[4];
int n,m,cnt,ans;
bool cmp(W a,W b){return a.v<b.v;}
void push_up(int x)
{
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]];
    lmx[x]=max(lmx[ch[x][0]],sum[ch[x][0]]+lmx[ch[x][1]]);
    rmx[x]=max(rmx[ch[x][1]],sum[ch[x][1]]+rmx[ch[x][0]]);
}
void build(int &x,int l,int r)
{
    if(!x)x=++cnt;
    if(l==r)
    {
        sum[x]=lmx[x]=rmx[x]=1;
        return;
    }
    int mid=l+r>>1;
    build(ch[x][0],l,mid);
    build(ch[x][1],mid+1,r);
    push_up(x);
}
void add(int pre,int &x,int l,int r,int v,int f)
{
    if(!x)x=++cnt;
    if(l==r)
    {
        lmx[x]=rmx[x]=sum[x]=f;
        return;
    }
    int mid=l+r>>1;
    if(v<=mid)
        ch[x][1]=ch[pre][1],add(ch[pre][0],ch[x][0],l,mid,v,f);
    else
        ch[x][0]=ch[pre][0],add(ch[pre][1],ch[x][1],mid+1,r,v,f);
    push_up(x);
}
int ask_all(int x,int L,int R,int l,int r)
{
    if(L==l&&R==r)return sum[x];
    int mid=L+R>>1;
    if(r<=mid)return ask_all(ch[x][0],L,mid,l,r);
    else if(l>mid)return ask_all(ch[x][1],mid+1,R,l,r);
    return ask_all(ch[x][0],L,mid,l,mid)+ask_all(ch[x][1],mid+1,R,mid+1,r);
}
int ask_left(int x,int L,int R,int l,int r)
{
    if(L==l&&R==r)return lmx[x];
    int mid=L+R>>1;
    if(r<=mid)return ask_left(ch[x][0],L,mid,l,r);
    else if(l>mid)return ask_left(ch[x][1],mid+1,R,l,r);
    return max(ask_left(ch[x][0],L,mid,l,mid),ask_all(ch[x][0],L,mid,l,mid)+ask_left(ch[x][1],mid+1,R,mid+1,r));
}
int ask_right(int x,int L,int R,int l,int r)
{
    if(L==l&&R==r)return rmx[x];
    int mid=L+R>>1;
    if(r<=mid)return ask_right(ch[x][0],L,mid,l,r);
    else if(l>mid)return ask_right(ch[x][1],mid+1,R,l,r);
    return max(ask_right(ch[x][1],mid+1,R,mid+1,r),ask_all(ch[x][1],mid+1,R,mid+1,r)+ask_right(ch[x][0],L,mid,l,mid));
}
bool check(int x,int a,int b,int c,int d)
{
    int sum=ask_left(root[x],1,n,c,d)+ask_right(root[x],1,n,a,b);
    if(b+1<c) sum+=ask_all(root[x],1,n,b+1,c-1);
    return sum>=0;
}
int main()
{
    n=sc();
    for(int i=1;i<=n;i++)
        h[i].v=sc(),
        h[i].pos=i;
    sort(h+1,h+n+1,cmp);
    build(root[1],1,n);
    for(int i=2;i<=n;i++)
        add(root[i-1],root[i],1,n,h[i-1].pos,-1);
    m=sc();
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<4;j++)
            q[j]=(sc()+ans)%n+1;
        sort(q,q+4);
        int l=1,r=n;ans=1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(check(mid,q[0],q[1],q[2],q[3]))ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d
",ans=h[ans].v);
    }
    return 0;
}