想定解で必要になる知識は
・セグメント木
・包除原理
です。
[P.S]ウェーブレット行列というデータ構造を用いると簡単に解けるようです。(未知かつ非想定でした。)
そちらのverifyとしてもお使いください。他にも色々なデータ構造を用いて解けるようです。
[解説]
・テストケース/解答コードはこちらからクローンできます。
クエリの条件は
・[l1≤L≤l2,r1≤R≤r2] → [①(l1≤L)&(②L≤l2)&(③r1≤R)&(④R≤r2)]
です。
ここで、余事象を考えると、求める個数は
ans= n−not[①&②&③&④] (※)
です。
(1)=not①,(2)=not②,(3)=not③,(4)=not④
とした時、
(※) =n−[(1)or(2)or(3)or(4)]
=n−[(1)+(2)+(3)+(4)−(1&2)−(1&3)−(1&4)−(2&3)−(2&4)−(3&4)+(1&2&3)+(1&2&4)+(1&3&4)+(2&3&4)−(1&2&3&4)]
です。
ですが、よく考えると
(1)=[l1>L],(2)=[L>l2],(3)=[r1>R],(4)=[R>r2]より、
(1)&(2)=∅,(3)&(4)=∅です。
つまり上記の式は
=n−[(1)+(2)+(3)+(4)−(1&3)−(1&4)−(2&3)−(2&4)]
となります。
各クエリにおいて、(1),(2),(3),(4)の個数は、Aの閉区間[L,R]の情報をL,Rについて、累積和をとることでO(1)で答えることができるのでよいです。
(1&3),(1&4)についてですが、これはクエリそれぞれに対して
・[l1>L],[r1>R]なる閉区間の個数
・[l1>L],[R>r2]なる閉区間の個数
の個数がわかれば良いです。
これは、クエリをl1で昇順ソートし、順にl1>Lの閉区間[L,R]のRをセグメント木に足し合わせて更新をしてゆくことでクエリ全体でO((Q+N)logN)で回答できます。
(2&3),(2&4)についても同様に考えることで、こちらもクエリ全体でO((Q+N)logN)で回答できます。
以上より、クエリ全体でO((Q+N)logN)で回答をすることができました。