The Famous ICPC Team Again

時間制限:5 Secメモリ制限:128 MB
タイトル記述When Mr.B,Mr.G and Mr.M were preparing for the 2012 ACM-ICC World Final Conttest,Mr.B had colleced a large set of contest problems for their daily trining.When they decided to Tate trining,When theMr.B would chose one of the m from the problem set.All the problems in the problem set had been sorted by their time of publish.Each time Prof.S,their coach,would them to chorose one prom blem blem Prote blocess.twoultimeeach time they would chose one of them from a specified segment of the line.
Moreover,when collecting the probles,Mr.B had also known n n estimation of each problem’s difficultness.When he was to chose a problem,if he chorse the ease one,Mr.G would coplanthat.Hey trable!eifhecheei the hadest one、Mr.M would grumble that t t t t took too muctime to finish it.To address this dilemma、Mr.B deded to Tae the one with the medifficulty. Threfore、heeeeedied a theinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininstststststststststststininininininininininininininininininininininngle integer n(1<=n==100,000)indicating the total number of probles.The second line contains n integers xi(0==1,000,000,000,000,000,000,000,000,000)separated by single space,denoting the difficultss of each problem.ingline.specifying number of queries.The n m lineas follow、each line contains a pair of integers、A and B(1<=A==B==n)、denoting that Mr.B need to chose a problem between positions A and B(clivefielpotions)2.It isgaranteteteed that the number of items between A and B is odd.For each queryを出力し、output a single line containininteat denotes the difficultnes of the problem that Mr.B Shououuld chose 3サンプル3 3例5 5 Copse 3 3サンプル3 3 3 3例3 3 3 3サンプル3 3例5 5 5 ppse 3サンプル3 3 3 3例5 5サンプル3.Copse 3.Copse 3 3.Copse 3 3 3.Copse 3.Copse 3.Copse 3 3.Copse 3 3 3.Copse 3 3 3 3.Copse 3 3 3 3 3意味:あげ始めるn個の数を出してから、いくつかの質問があります.毎回一つの区間を与えて、与えられた区間の中の中央の桁数を解きほぐすことを要求します.入力したデータの中でこの区間の奇数個の数の問題点があることを保証します.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
typedef int itn;
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
const int mod = 1e9+7;
 
inline ll read() {
     
    ll c = getchar(), Nig = 1, x = 0;
    while (!isdigit(c) && c != '-')c = getchar();
    if (c == '-'){
     
        Nig = -1;
        c = getchar();
    }
    while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
    return Nig * x;
}
///typedef read() read;
#define read read()
int maxx = -1;
int minn = 0x3f3f3f3f;
 
int a[40][maxn];
int b[maxn];
int cnt[40][maxn];/// cnt[a][b]   a , 1 b         
 
void build(int l,int r,int flor){
     
    ///        
    if(l == r) return ;///            
    int mid = (l + r) / 2;///            
    int equ_mid = (mid - l + 1);///            
    for(int i = l;i <= r; i ++){
     
        if(a[flor][i] < b[mid]) equ_mid --;///          ，       1
    }
    int t_l = l;///    
    int t_r = mid + 1;///      
    /**
           mid + 1   ，       ，             ，   ++
        
    **/
 
    for(int i = l;i <= r;i ++){
     
        ///            
        if(a[flor][i] < b[mid]) a[flor + 1][t_l ++] = a[flor][i];
        ///       ，             0，                   
        else if(a[flor][i] == b[mid] && equ_mid){
     
            a[flor + 1][t_l ++] = a[flor][i];
            equ_mid --;///     
        }///               
        else{
     
            a[flor + 1][t_r ++] = a[flor][i];
        }
        cnt[flor][i] = cnt[flor][l - 1] + t_l - l;
    }
    build(l ,mid ,flor + 1);///        
    build(mid + 1 , r , flor + 1);///        
 
}
 
int _findAns(int L,int R,int l,int r,int flor,int K){
     
    ///      L   R     ，      l   r      flor      K    
    if(l == r) return a[flor][r];///        
    int mid = (L + R) / 2;
    int num = cnt[flor][r] - cnt[flor][l - 1];
    ///                posl-1        ，      
    if(num >= K) ///     k
    {
     
        int n_l = L + cnt[flor][l - 1] - cnt[flor][L - 1];
        int n_r = n_l + num - 1;
        return _findAns(L,mid,n_l,n_r,flor + 1,K);
    }
    else{
     
        int n_r = r + cnt[flor][R] - cnt[flor][r];
        int n_l = n_r - (r - l - num);///           
        return _findAns(mid + 1,R,n_l,n_r,flor + 1,K - num);
    }
}
int main(){
     
    int n; int cnt = 0;
    while(cin >> n){
     
        memset(a,0,sizeof(a));
        for(int i = 1;i <= n; i ++){
     
            a[0][i] = read;
            b[i] = a[0][i];///       
        }///       
        sort(b + 1,b + 1 + n);
        build(1 , n , 0);///  1 -> n      
        printf("Case %d:
",++cnt);
        int q = read;
        while(q--){
     
            int l=read,r=read;
            int k = (r - l) / 2 + 1;
            printf("%d
",_findAns(1,n,l,r,0,k));
        }
    }
    return 0;
}
/**
5
5 3 2 4 1
3
1 3
2 4
3 5
5
10 6 4 8 2
3
1 3
2 4
3 5
 
Case 1:
3
3
2
Case 2:
6
6
4
**/
 
/**************************************************************
    Problem: 10968
    Language: C++
    Result:   
    Time:595 ms
    Memory:33668 kb
****************************************************************/