Filtered Records

解説

クエリ $X$ の答えは、$W_i\le X$ であり、かつ $j\lt i,\ W_j\le X$ を満たすすべての $j$ について $A_j\lt A_i$ が成り立つような $i$ の個数である。

各 $i$ について、$j\lt i$ かつ $A_j\ge A_i$ を満たす $j$ のうち、$W_j$ の最小値を $T_i$ とする。そのような $j$ が存在しない場合は $T_i=N+1$ とする。

このとき、クエリ $X$ の答えは $W_i\le X\lt T_i$ を満たす $i$ の個数となる。

したがって、各 $i$ について区間 $[W_i,T_i)$ に $1$ を加算し、各 $X$ における値を累積和で求めればよい。

$i=1,2,\ldots,N$ の順に、セグメント木の位置 $x$ で $A_j=x$ を満たす $W_j$ の最小値を管理すれば、$T_i$ は区間 $[A_i,N]$ の最小値となるので、 $O(N\log N+Q)$ でこの問題を解くことができる。