主席树

 
Online Judge	Online Exercise	Online Teaching	Online Contests	Exercise Author
F.A.Q
Hand In Hand
Online Acmers	
Forum | Discuss
Statistical Charts
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
Virtual Contests 
    DIY | Web-DIY beta
Recent Contests
Author 1504010705
Mail Mail 0(0)
Control Panel Control Panel 
Sign Out Sign Out
点击查看详情——《IJCAI 2017 口碑商家客流量预测大赛》
View Code

Problem : 5919 ( Sequence II )     Judge Status : Accepted
RunId : 19705448    Language : G++    Author : 1504010705
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define L long long
const int maxn = 200050 ;
int root[maxn] ;
struct node {
    int l , r , sum ;
}T[maxn * 40];
int cnt ;
int n , m ;
int a[maxn];
void build(int l, int r){
    T[++cnt].sum = 0 ;
    T[cnt].l = T[cnt].r = 0;
    if(l == r) return ;
    int mid = (l + r) / 2 ;
    int x = cnt ;
    T[x].l = cnt + 1;
    build(l, mid) ;
    T[x].r = cnt + 1;
    build(mid+1,r) ;
}
int sc[maxn * 2] ;
void upda(int l , int r , int &x , int y , int i , int j ) {
    T[++cnt] = T[y] ;
    x = cnt ;
    if(i >= l && i <= r)
        T[cnt].sum ++;
    if(j != -1 && j >= l && j <= r) T[cnt].sum -- ;
    if(l == r)return ;
    int mid = (l + r) / 2 ;
    if((i >= l && i <= mid) || (j != -1 && j >= l && j <= mid)) {
        upda(l,mid,T[x].l , T[y].l , i , j ) ;
    }
    if((i >= mid+1 && i <= r) || (j != -1 && j >= mid+1 && j <= r)) {
        upda(mid+1,r,T[x].r , T[y].r , i , j ) ;
    }
}

int ans[maxn] ;

int query(int l,int r,int ro,int ll , int rr) {
    if(l <= ll && r >= rr) {
        return T[ro].sum ;
    }
    int mid = ( ll + rr ) / 2 ;
    if(r <= mid) {
        return query(l,r,T[ro].l , ll,mid) ;
    }
    else if(l >= mid + 1) {
        return query(l,r,T[ro].r , mid+1, rr) ;
    }
    else {
        return query(l,r,T[ro].l,ll,mid) + query(l,r,T[ro].r,mid+1,rr) ;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    int cas = 1 ;
    while(t-- ){
        scanf("%d%d",&n,&m) ;
        for(int i = 1; i <= n ;i ++ ){
            scanf("%d",&a[i]);
        }
        root[n+1] = 1;
        cnt = 0 ;
        build(1,n);
        memset(sc , -1 , sizeof(sc)) ;
        for(int i = n ; i >= 1 ; i -- ){
            int x = a[i] ;
            int j = sc[a[i]] ;
            upda(1,n,root[i] ,root[i+1], i , j ) ;
            sc[a[i]] = i ;
        }
        ans[0] = 0 ;
        for(int i = 1; i <= m ; i ++ ) {
            int ll, rr ;
            scanf("%d%d",&ll,&rr);
            int l = min((ll + ans[i-1])%n+1 ,(rr + ans[i-1])%n+1) ;
            int r = max((ll + ans[i-1])%n+1 ,(rr + ans[i-1])%n+1) ;
            int sum = query(l,r,root[l],1,n) ;
            int k = sum / 2;
            if(sum %2 != 0) k ++ ;
            int ro = l ;
            while(l <= r) {
                if(l == r) {
                    ans[i] = l ;
                    break ;
                }
                int mid = (l + r) / 2 ;
                int z = query(l,mid,root[ro],1,n) ;
                if(z >= k ) {
                    r = mid ;
                }
                else {
                    l = mid + 1 ;
                    k -= z ;
                }
            }
        }
        printf("Case #%d: ",cas++ ) ;
        for(int i = 1 ; i <= m ; i ++ ){
            printf("%d",ans[i]);
            if(i == m)printf("\n");
            else printf(" ") ;
        }
    }
}