Codeforces 38 G. Queue

問題

n人の人が以下のようなルールで列に並ぶ。

• i番目の人が来て、列の最後尾に加わる。i番目の人は重要度a[i]と、常識度c[i]を持っている。
• 一つ前の人の重要度a[i-1]が、自分の重要度より低かったら、その人前へ割り込む。
• 割り込みはc[i]回だけできる。

n人の人が全て並び終わった後、列はどうなっているか答えよ。

制約条件

n≦10^5
a[i]は1からnの順列になっている

方針

平方分割による。
列をsqrt(n)くらいずつのグループに分割して持っておき、グループごとに飛ばせるかを見ることで、
時間計算量O(n^1.5)くらいで全体のクエリを処理することができる。

グループは人数がだんだん不均一になってくるので、
挿入がsqrt(n)回くらいおこった後にグループを均等に更新してやる。

これで全体の時間計算量が最悪でもO(n^1.5)になる。

ソースコード

const int SZ=300;
int n;
vector<vi> bucket;
int mx[100000/SZ+1];
int A[100000],id[100001];

void run(){
  scanf("%d",&n);
  bucket.resize(1);
  
  rep(i,n){
    int a,c; scanf("%d%d",&a,&c);
    id[a]=i+1;
    
    int p=bucket.size()-1;
    for(;c>0&&p>0;p--){
      if(mx[p]>a||bucket[p].size()>c)break;
      c-=bucket[p].size();
    }
    int q=bucket[p].size();
    for(;c>0&&q>0;q--,c--){
      if(bucket[p][q-1]>a)break;
    }
    bucket[p].insert(bucket[p].begin()+q,a);
    mx[p]=max(mx[p],a);
    
    if(i%SZ==SZ-1||i==n-1){
      int l=0;
      rep(j,bucket.size())rep(k,bucket[j].size())A[l++]=bucket[j][k];
      bucket.clear();
      bucket.resize((l+SZ-1)/SZ);
      rep(j,(l+SZ-1)/SZ)mx[j]=0;
      rep(j,l){
        bucket[j/SZ].pb(A[j]);
        mx[j/SZ]=max(mx[j/SZ],A[j]);
      }
    }
  }
  rep(i,n)printf("%d%c",id[A[i]],i==n-1?'\n':' ');
}