Disclaimer

This problem may be a score-based problem that somewhat lacks competitive quality. Please do not take it too seriously.
The score varies even for the same output / submission, but since judging is fairly heavy, please refrain from excessive identical submissions.

Problem Statement

Note that the time limit is $500$ ms, which is shorter than usual.
Also, note the very unusual scoring method.
Since this is a score-based problem, you cannot make another submission for 5 minutes after your last submission.

Here is the following problem. This problem is well known as 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;
}

• Read the input.
• Apply coordinate compression to $A$.
• Receive the output permutation $P$.
• Compute the inversion numbers of the intervals in the same manner as Mo's Algorithm.
• At the $i$-th step, the answer is computed for the interval of the $P_i$-th query.
• When adding / removing $1$ point at the left end / right end of the interval, a Binary Indexed Tree is used to compute the change in the inversion number.
• The time complexity of this operation is $O(\log N)$.
• If Mo's Algorithm is implemented well (in the form of sorting $P$), the time complexity can be made $O(N \sqrt{Q} \log N)$.

Scoring

In this problem, your score is determined by the result of actually running Butsurizuki-san's code $C$ with the permutation $P$ you output.
This problem contains 100 test cases.
Suppose that code $C$ takes $T$ μs of execution time on a test case.
Then, the score for that test case is determined as follows.

• If $T \le 1.5 \times 10^6$ (the execution time is at most $1500$ ms), the score is $10^{16} + (1.5 \times 10^6 - T)$ points.
• Otherwise, the score is $0$ points.

Input

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

The input is that of Static Range Inversions Query. The same input is also given to Butsurizuki-san's code when it is run.

Output

Output the permutation $P$ in the following format.

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

Input Generation

$48$ of the input cases are generated by the following method.
There are $48$ possible integer tuples $(N,Q,ST)$ satisfying $N,Q \in \{10000,20000,50000,100000\},$ and interval generation method $ST \in \{1,2,3\}$, and $1$ test case is generated for each tuple.
$A_i$ is generated independently and uniformly at random in the range $0 \le A_i \le 10^9$.

In addition, $30$ of the input cases are generated by the following method.
$N=100000,Q=100000$ are fixed.
For each number of distinct values of $A_i$, $k = 10,10^2,10^3,10^4,10^5$, $2$ cases are generated for each interval generation method $ST = 1,2,3$, for a total of $30$ cases.
Starting from $A_i=(0,1,\dots,k-1)$, append $N-k$ uniformly random numbers between $0$ and $k-1$, inclusive, to the end, then shuffle $A$, and then replace each value with a uniformly random integer between $0$ and $10^9$, inclusive, so that identical values remain identical / different values remain different.

In addition, $1$ of the input cases matches Sample 1 shown below.

In addition, $1$ of the input cases is published here. It is a case generated with $N=100000,Q=100000,ST=3$.
$A_i$ is generated independently and uniformly at random in the range $0 \le A_i \le 10^9$.

For the remaining $20$ cases, the input generation method is kept secret. Cases of any malicious intent may be given.
However, the generator is posted in the generator section. Please refer to it after the contest ends or at a similar time.

The details of each interval generation method are as follows.
Method 1:

• Intervals are always generated by the following method.
• Generate $x=$ $\rm{rnd}$$(1,N),y=$ $\rm{rnd}$$(1,N)$.
• If $x>y$, swap $x,y$.
• The generated interval is $[x,y]$.

• Intervals are always generated by the following method.
• Generate $l=$ $\rm{rnd}$$(1,N)$.
• Generate $x=$ $\rm{rnd}$$(1,N-l+1)$, and let $y=x+l-1$.
• The generated interval is $[x,y]$.

• For each interval, independently, either Method 1 or Method 2 is chosen with equal probability, and the interval is generated by that method.

Sample

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

4 2 1 3

2
0
2
3