[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;
}
}