[ABC221] E - LEQ
[Q] https://atcoder.jp/contests/abc221/tasks/abc221_e
座標圧縮とBITはそうそうに方針立つも、77分こねくり回して死。
BITで管理するのは~以下の個数じゃなくて、
減算させる組み合わせ 2^(-1) + 2^(-2) + ... の総和
だった。
1. BITしたいので、座標圧縮する。
2. BITの中身は、
A[0]は2^0
A[1]は2^-1
A[2]は2^-2
3. もし部分列の最後が A[1] ~ A[N-1] 番目だった場合、を走査していく。
4. いったん全部とれると見込んで、ありうる組み合わせの総和modtwo[i]-1を足す。
5. そこから、取れない場合 modtwo[i-1] * dat( A[i] ~ N の総和 ) を除く。
Q. 入力例4を考える
10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
1. 座標圧縮。
2 1 9 3 10 8 7 6 5 4
2. 部分列の末端を A[1]から、A{9] まで走査していく。
0)
・A[0]がお尻は何も取れない // ans=0
・bitの準備。本来2^(i-1)通りとれるけど、X > A[i] だった場合どれだけ減らすか、を考える。
bit.add(2, modinv(2)^0) // (2, 1)
1) A[1]がお尻
・いったん全部とれるとみなす。
ans += 2^1 - 1 = 1 // ans=1
実際は取れない組み合わせを除く。 2>1 だから除きたい。
ans -= 2^(i-1) * dat( 1 ~ N の総和 ) // ans=0
・bitの準備。
bit.add(1, modinv(2)^1) // (1, 1/2)
1) A[2]がお尻
・いったん全部とれるとみなす。
ans += 2^2 - 1 = 3 // ans=3
実際は取れない組み合わせを除く。 今回は全部とれるから除くものがないはず。
ans -= 2^(i-1) * dat( 9 ~ N の総和) // ans=3
・bitの準備。
bit.add(9, modinv(2)^2) // (9, 1/4)
...実装。
struct Bit
{
ll BT;
vector<ll> dat;
Bit(ll n) : BT(n+10) {
dat.resize(BT, 0);
}
void add(ll i, ll x){
++i;
for(; i<BT; i += i&-i) dat[i] += x;
}
ll sum(ll i){
++i;
ll res = 0;
for(; i>0; i -= i&-i) res += dat[i];
return res;
}
ll rangesum(ll L, ll R){
++L, ++R;
return sum(R) - sum(L-1);
}
};
int main(){
cincout();
ll N;
cin >> N;
ll modtwo[N+10] = {}; // 事前準備
modtwo[0] = 1;
rep(i, N+1) modtwo[i+1] = modtwo[i] * 2LL %MOD;
vector<ll> A(N);
rep(i, N) cin >> A[i];
ll sz = comp(A); // 座標圧縮
Bit bits(sz);
ll ans = 0;
ll div = modinv(2);
rep(i, N){
( ans += (modtwo[i]-1+MOD)%MOD ) %=MOD; // 全部とれるとして、いったん総和とる
if (i){
ll dics = (bits.sum(sz+2) - bits.sum(A[i]) + MOD) %MOD; // 自分より大きいものを除外
ans = (( ans - modtwo[i-1]*dics%MOD)+MOD ) %MOD; //2^(i-1) * 2^(-abcde)
}
bits.add(A[i], modpow(div, i)); //0,-1,-2,...
}
cout << ans << endl;
}