[ABC237] G - Range Sort Query

[Q] https://atcoder.jp/contests/abc237/tasks/abc237_g

bitsetで7116ms/8000msAC。bitset処女作。
範囲の更新なので、遅延セグ、BIT、をエスパーするも至らず。遅延セグなら300msくらいで通るぽい。

Q. bitset？
(コンテスト中に初めて使い方を調べる。今時点で勝手にもっているイメージ。)
A. 1bitを1つの配列として扱うデータ構造

bitset<10> a; // a:0000000000
      ~~~~ ここは数字の生入れじゃないとだめ。

// N=10;
// bitset<N> a; これはerror

加算したり、
a |= 1;   // a:0000000001
a |= 8;   // a:0000001001

ずらしたり、
a <<= 1   // a:0000010010

立っているbitの数を数えたり、
a.count(); // a=2

01を反転させたり、
a.flip(); // a:1111101101
a.count(); // a=8

基本的なことが、高速にできる。

考察。
1. Pについて、数字を持つ必要はなくて
X以上をtrue、X未満をfalseにもつ
だけでよさそう。
2. クエリの区間について。立っているbitの本数を数えて、
C==1 なら昇順なので1を右によせればいい。000...111...
C==2 なら降順なので1を左によせればいい。111...000...
3. 答えは？
a) X以上をtrue、x未満をfalseにもったbitset0と
b) X超過をtrue、x以下をfalseにもったbitset1について実施して、差分index位置が解答。

Q
N=5 Q=2 X=1
P[]:1 4 5 2 3
1 3 5
2 1 3


1. Pをtrue/falseにしちゃう
  P[]:1 4 5 2 3
bit0 :1 1 1 1 1
bit1 :0 1 1 1 1

2. クエリしていく。
a)1 3 5
昇順ソートなので
  bit0 :1 1[1 1 1]
->bit0 :1 1[1 1 1]
  bit1 :0 1[1 1 1]
->bit1 :0 1[1 1 1]
になる。かわらないな。

b)2 1 3
降順ソートなので
  bit0 :[1 1 1] 1 1
->bit0 :[1 1 1] 1 1
  bit1 :[0 1 1] 1 1
->bit1 :[1 1 0] 1 1

3. 解答
bit0 : 1 1 1 1 1
bit1 : 1 1 0 1 1
           ~ 5-2index = 3が解答。

Q. bitのquery操作をどうしよう
A. bitシフトで、行って戻って、をすれば0にできるのを利用。

Q. L=3, R=5
 bs[]: 1 1[1 1 1]1 1 1

まず、Lで区切ったものとRで区切ったものを用意。
 bsr : 1 1 1 1 1 0 0 0
 bsl : 1 1 0 0 0 0 0 0
           ~~~~~ = 3bit
count()の差をとれば、何本立ってるかがわかる。
3本のbitを用意して、
 add : 0 0 0 0 0 1 1 1
昇順クエリなら右よせする。
 add : 0 0[1 1 1]0 0 0
             <-|ここから3bit
あとは、Lより左と、Rより右を用意して、合算させればOK
 bsl : 1 1 0 0 0 0 0 0
 add : 0 0 1 1 1 0 0 0
right: 0 0 0 0 0 1 1 1

合算したもの
left|add|right : 1 1[1 1 1]1 1 1
がクエリ処理。

Q. 高速化するコンパイル？
A. これを書かなかったらTLE。書いたら3倍くらい早くなってギリAC

 #pragma  GCC target("avx2")
 #pragma  GCC optimize("O3")
 #pragma  GCC optimize("unroll-loops")

実装

ll N, Q, X;
#define HIGH 200010

// 昇順
bitset<HIGH> query1(bitset<HIGH> bs, ll L, ll R) {
 bitset<HIGH> bsl, bsr, ret, add, rig;
 bsl = bs;
 bsr = bs;           // 1 1[1 1 1]1 1 1
 bsl >>= N - R;      // 1 1 1 1 1 0 0 0
 bsl <<= N - R;
 bsr >>= N - L + 1;  // 1 1 0 0 0 0 0 0
 bsr <<= N - L + 1;
 ll cnts = bsl.count() - bsr.count();
 add.flip();
 add >>= HIGH - cnts;// cntsの数だけ111
// 右によせる
 add <<= N - R;      // 0 0 1 1 1 0 0 0
 rig = bs ^ bsl;     // 0 0 0 0 0 1 1 1
 ret = bsr | add | rig;
 return ret;
}

// 降順
bitset<HIGH> query2(bitset<HIGH> bs, ll L, ll R) {
 bitset<HIGH> bsl, bsr, ret, add, rig;
 bsl = bs;
 bsr = bs;                  // 1 1[1 1 1]1 1 1
 bsl >>= N - R;
 bsl <<= N - R;             // 1 1 1 1 1 0 0 0
 bsr >>= N - L + 1;
 bsr <<= N - L + 1;         // 1 1 0 0 0 0 0 0
 ll cnts = bsl.count() - bsr.count();
 add.flip();
 add >>= HIGH - cnts;       // cntsの数だけ111
// 左によせる
 add <<= N - L + 1 - cnts;  // 0 0 1 1 1 0 0 0
 rig = bs ^ bsl;            // 0 0 0 0 0 1 1 1
 ret = bsr | add | rig;
 return ret;
}

int main() {
 cincout();
 cin >> N >> Q >> X;
 bitset<HIGH> bs0;
 bitset<HIGH> bs1;
 rep(i, N) {
   ll p;
   cin >> p;
   bs0 <<= 1;
   bs1 <<= 1;
   if (p > X) {
     bs0 |= 1;
   }
   if (p >= X) {
     bs1 |= 1;
   }
 }

 rep(i, Q) {
   ll C, L, R;
   cin >> C >> L >> R;
   if (C == 1) {
     bs0 = query1(bs0, L, R);
     bs1 = query1(bs1, L, R);
   } else {
     bs0 = query2(bs0, L, R);
     bs1 = query2(bs1, L, R);
   }
 }
 rep(i, N + 1) {
   if (bs0[i] == bs1[i]) continue;
   cout << N - i << endl;
   return 0;
 }
}

https://atcoder.jp/contests/abc237/submissions/28966075