No.59 鉄道の旅 - yukicoder
- 典型的な RMQ っぽい問題。
- 蟻本で BIT の存在はしっていたけど使うのは初めてだった。
- この問題では sum は a[i]+...+a[maxW] なんだけど BIT では逆で a[1] + ... + a[i] 。それゆえに a[i] = sum[i]-sum[i+1] となる。これをうっかり逆にしてしまい WA した。
class RailroadTrip {
public:
void solve(void) {
int N,K;
cin>>N>>K;
int maxW = (1<<(int)ceil(log2(1E+6)));
vector<ll> bits(maxW+1,0);
auto add = [&](int i, int x) {
assert(i>0);
while (i <= maxW)
{
bits[i] += x;
i += (i & -i);
}
};
auto sum = [&](int i) {
ll s = 0;
--i;
while (i > 0)
{
s += bits[i];
i -= (i & -i);
}
return bits[maxW] - s;
};
REP(i,N)
{
ll w, aw;
cin>>w;
aw = abs(w);
if (w > 0 && sum(w) < K)
add(w,1);
else if (w < 0 && sum(aw)-sum(aw+1) > 0)
add(aw,-1);
}
cout<<sum(1)<<endl;
}
};