CDQZ Challenge 20

앞에서 말 했 듯 이 "CDQZ" 시리즈 의 제목 데 이 터 는 절대 양심 (심혈 을 기울 여 233) 입 니 다. 인터넷 주 소 를 제출 할 때 필요 하 다 면 개인 편지 본 을 보 내 주세요.1020: Challenge 20 보기 제출 통계 질문 총 시간 제한: 10000 ms 단일 테스트 포인트 시간 제한: 1500 ms 메모리 제한: 512000 kB 설명 은 n 의 수열 ai (1 ≤ i ≤ n), m 회 문의 구간 [L, R] 에서 한 번 만 나타 난 수의 최대 치 는 얼마 입 니까?
첫 줄 두 개의 정수 n 과 m 를 입력 하 십시오. 두 번 째 줄 n 개의 정수 ai. 다음 m 줄 마다 두 개의 정수 L, R. 출력 은 각 질문 출력 에 대한 답 입 니 다. 샘플 입력 5, 3, 1, 4, 3, 5, 3, 3, 4, 5, 4, 5, 4, 4, 4, 4, 5, 4 개의 출력 2 알림 n, m, ai ≤ 3 * 10 ^ 5 본 문 제 는 난동 문제 로 기본 데이터 가 모두 랜 덤 입 니 다.
실측 데 이 터 는 음수 가 없고 모두 [1, n] 범위 내 에 있다.문제 풀이: 각 수가 답 에 기여 하 는 구간 (지난번 에 위치 pr [i] + 1 에서 이번에 나타 난 위치 i) 을 현재 위치 i 의 가중치 선분 트 리 에 삽입 한 다음 query 는 가능 한 한 오른쪽 하위 트 리 로 내 려 가면 됩 니 다.P. S. 구조 체 를 사용 하여 선분 수 를 만 들 면 20% 정도 빠 를 수 있 습 니 다.

#include
#include
#include
#include
#include
using namespace std;
const int MAXN=3e5+4;
int n,m,a[MAXN];
int lc[MAXN*20],rc[MAXN*20],mn[MAXN*20],mx[MAXN*20],root[MAXN],tim=0;
int mp[MAXN],pr[MAXN];
inline void pushup(int rt) {
    mn[rt]=min(mn[lc[rt]],mn[rc[rt]]);
    mx[rt]=max(mx[lc[rt]],mx[rc[rt]]);
}
void Insert(int pre,int &cur,int l,int r,int pos,int v1,int v2) {
    cur=++tim;
    mn[cur]=mn[pre],mx[cur]=mx[pre],lc[cur]=lc[pre],rc[cur]=rc[pre];
    if (l==r) {mn[cur]=v1,mx[cur]=v2;return ;}
    int mid=l+r>>1;
    if (pos<=mid) Insert(lc[pre],lc[cur],l,mid,pos,v1,v2);
    else Insert(rc[pre],rc[cur],mid+1,r,pos,v1,v2);
    pushup(cur);
}
int query(int rt,int l,int r,int v) {
    if (l==r) return v<=mx[rt]&&v>=mn[rt]?l:0;
    int ret=0,mid=l+r>>1;
    if (v<=mx[rc[rt]]&&v>=mn[rc[rt]]) {
        ret=query(rc[rt],mid+1,r,v);
        if (ret) return ret;
    }
    return query(lc[rt],l,mid,v);
}
inline int read() {
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int main() {
//  freopen("Challenge 20.in","r",stdin);
    memset(mn,0x3f3f3f3f,sizeof(mn));
    memset(mx,-0x3f3f3f3f,sizeof(mx));
    n=read(),m=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    for (register int i=1;i<=n;++i) {
        pr[i]=mp[a[i]],mp[a[i]]=i;
        Insert(root[i-1],root[i],1,n,a[i],pr[i]+1,i);
    }
    for (register int i=0;i<m;++i) {
        int L=read(),R=read();
        printf("%d
",query(root[R],1,n,L));
    }
    return 0;
}