おことわり

この問題は、それなりに競技性に欠くスコア問題である可能性があります。どうか、あまりムキにならないでください。
同一の 出力 / 提出 に対してスコアが変動しますが、ジャッジがそこそこ重いため過度な同一提出はお控えください。

問題文

実行時間制限が通常より短い $500$ ms であることに注意してください。
また、非常に特殊な採点方法に注意してください。
スコア問題であるため、最後の提出から5分間は次の提出を行うことができません。

ここに、以下のような問題があります。この問題は Static Range Inversions Query としてよく知られています。

数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
以下の $Q$ 個の問い合わせに答えてください:
$i$ 番目の問い合わせでは $l_i,r_i$ が与えられる。連続部分列 $(A_{l_i},A_{l_i+1},\dots,A_{r_i})$ の転倒数を求めよ。
制約
・入力は全て整数
・$1 \le N,Q \le 10^5$
・$0 \le A_i \le 10^9$
・$1 \le l_i \le r_i \le N$

実行時間制限: $2$ s

#include <bits/stdc++.h>
#include <sys/time.h>

using namespace std;

long long start_time;

void start_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  start_time=(tv.tv_sec*1000000+tv.tv_usec);
}

long long current_clock(){
  struct timeval tv;
  gettimeofday(&tv, NULL);
  long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
  // cout << current_time-start_time << "(us)\n";
  return current_time-start_time;
}

int bit[111111]={0};
int bsize;

int BIT_sum(int i){
  int s=0;
  while(i>0){
    s+=bit[i];
    i-=i&(-i);
  }
  return s;
}

void BIT_add(int i,int x){
  while(i<=bsize){
    bit[i]+=x;
    i+=i&(-i);
  }
}

int N,Q;
int A[111111];
int l[111111],r[111111];
int P[111111];

int whole=0;
long long result=0;
void add(int i,bool isLeft){
  if(isLeft){
    result+=BIT_sum(A[i]-1);
  }
  else{
    result+=whole;
    result-=BIT_sum(A[i]);
  }
  BIT_add(A[i],1);
  whole++;
}

void rem(int i,bool isLeft){
  BIT_add(A[i],-1);
  whole--;
  if(isLeft){
    result-=BIT_sum(A[i]-1);
  }
  else{
    result-=whole;
    result+=BIT_sum(A[i]);
  }
}

int cur_l,cur_r;

long long mo_work(int l,int r){
  while(l < cur_l){cur_l--;add(cur_l,true);}
  while(cur_r < r){cur_r++;add(cur_r,false);}
  while(cur_l < l){rem(cur_l,true);cur_l++;}
  while(r < cur_r){rem(cur_r,false);cur_r--;}
  return result;
}

long long output[111111];

int main(){
  // 入力処理
  cin >> N >> Q;
  bsize=N;
  for(int i=1;i<=N;i++){
    cin >> A[i];
  }
  for(int i=1;i<=Q;i++){
    cin >> l[i] >> r[i];
  }

  // 座標圧縮
  map<int,int> mp;
  for(int i=1;i<=N;i++){
    mp[A[i]]=1;
  }
  int comp=1;
  for(auto &nx : mp){
    nx.second=comp;
    comp++;
  }
  for(int i=1;i<=N;i++){
    A[i]=mp[A[i]];
  }

  // 順列 P をうまく定める
  for(int i=1;i<=Q;i++){
    P[i] = ( 出力された P_i );
  }

  // 計時開始
  start_clock();
  for(int i=1;i<=Q;i++){
    if(i==1){
      cur_l=l[P[i]];
      cur_r=l[P[i]];
      add(l[P[i]],true);
    }
    output[P[i]]=mo_work(l[P[i]],r[P[i]]);

    if(i%100==0){
      // TLEノックアウト
      if(current_clock()>1500000){break;}
    }
  }

  // 計時終了
  long long exe_time=current_clock();

  // 出力
  for(int i=1;i<=Q;i++){
    cout << output[i] << "\n";
  }
  return 0;
}

• 入力を受け取る。
• $A$ を座標圧縮する。
• 出力された順列 $P$ を受け取る。
• Mo's Algorithm と同じ要領で区間の転倒数を求めていく。
• $i$ 番目には $P_i$ 番目の問い合わせの区間に対して答えを求める。
• 区間の 左端 / 右端 の $1$ 点 追加 / 削除 を行う際、 Binary Indexed Tree を利用して転倒数の変動を求める。
• その際の計算量は $O(\log N)$ である。
• Mo's Algorithm を ( $P$ のソートという形で ) うまく実装すれば $O(N \sqrt{Q} \log N)$ という計算量にできる。

得点

この問題では、出力された順列 $P$ を利用して物理好きさんのコード $C$ を実際に実行した結果により得点が定められます。
この問題には 100 個のテストケースが含まれます。
コード $C$ が各テストケースに対して $T$ μs の実行時間を要したとします。
すると、各テストケースに対する得点は以下のように定められます。

• $T \le 1.5 \times 10^6$ (実行時間が $1500$ ms 以下) である場合、得点は $10^{16} + (1.5 \times 10^6 - T)$ 点である。
• そうでない場合、得点は $0$ 点である。

入力

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

入力は Static Range Inversions Query の入力です。物理好きさんのコードにも同じものが与えられて実行されます。

出力

順列 $P$ を以下の形式で出力せよ。

$P_1$ $P_2$ $\dots$ $P_Q$

入力生成方法

入力のうち $48$ ケースは以下の方法により生成されます。
$N,Q \in \{10000,20000,50000,100000\},$ 区間生成法 $ST \in \{1,2,3\}$ を満たす整数組 $(N,Q,ST)$ は $48$ 通り考えられますが、各整数組に対応するテストケースが $1$ つずつ生成されます。
$A_i$ は $0 \le A_i \le 10^9$ の範囲で独立一様ランダムに生成されます。

それに加えて、入力のうち $30$ ケースは以下の方法により生成されます。
$N=100000,Q=100000$ で固定です。
$A_i$ の種類数 $k = 10,10^2,10^3,10^4,10^5$ であるケースが区間生成法 $ST = 1,2,3$ について各 $2$ 個ずつ、計 $30$ ケースが生成されます。
$A_i=(0,1,\dots,k-1)$ から始め、後ろに $0$ 以上 $k-1$ 以下の一様乱数を $N-k$ 個付けたのち $A$ をシャッフル、その後 同一の値が同一になる / 異なる値が異なる ように各値を $0$ 以上 $10^9$ 以下の一様ランダムな整数に付け替えます。

それに加えて、入力のうち $1$ ケースは以下で示される サンプル1 に一致します。

それに加えて、入力のうち $1$ ケースは こちらで公開されています。 $N=100000,Q=100000,ST=3$ として生成したケースです。
$A_i$ は $0 \le A_i \le 10^9$ の範囲で独立一様ランダムに生成されています。

残りの $20$ ケースにについて、入力生成方法は秘匿されます。どのような悪意を持ったケースも与えられる可能性があります。
但し、ジェネレータ欄にジェネレータを貼っています。コンテスト終了後などに参照してください。

各区間生成法の詳細は以下の通りです。
方法1:

• 区間は必ず以下の方法で生成される。
• $x=$ $\rm{rnd}$$(1,N),y=$ $\rm{rnd}$$(1,N)$ で生成する。
• もし $x>y$ なら $x,y$ を交換する。
• 生成される区間は $[x,y]$ である。

• 区間は必ず以下の方法で生成される。
• $l=$ $\rm{rnd}$$(1,N)$ で生成する。
• $x=$ $\rm{rnd}$$(1,N-l+1)$ で生成し、 $y=x+l-1$ とする。
• 生成される区間は $[x,y]$ である。

• 区間は 方法1 と 方法2 のどちらかが等確率で区間ごとに独立に選択され、その方法で生成される。

サンプル

5 4
1 0 3 2 2
1 4
2 3
2 5
1 5

4 2 1 3

2
0
2
3