\(\mathscr{Description}\)
Link.
初始有整数 \(x=0\), 给出 \(n\) 次操作, 每次操作为 \(x\gets x+a\cdot2^b\) 或询问 \(x\) 的第 \(k\) bit.
\(n\le10^6\), \(|a|\le10^9\), \(b,k\le30n\). 保证时刻 \(x\ge0\).
\(\mathscr{Solution}\)
注意到单纯的二进制加 bit 是均摊 \(\mathcal O(1)\) 的, 为了避免摊还分析的失效, 我们分开维护仅有 \(a>0\) 是的 \(x_+\) 和仅有 \(a<0\) 时的 \(x_-\).
此时询问转变为求 \(x_+-x_-\) 的第 \(k\) bit. 通过 set 维护 \(x_+\) 和 \(x_-\) 的差异 bit, 判断后缀大小关系即可实现. 但这又带来一个问题: 修改的复杂度会带上一个 \(\log\), 如果再对 \(|a|\) 暴力拆 bit 就寄了. 所以还需要用 unsigned
之类的东西压位存储. 最终复杂度为 \(\mathcal O(n\log n)\) (\(a\) 拆为 unsigned
的数量为 \(\mathcal O(1)\)).
\(\mathcal{Code}\)
/* Clearink */
#include <set>
#include <cstdio>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread( p = buf, 1, 1 << 17, stdin ), p == q )
? EOF : *p++;
}
inline int rint() {
int x = 0, f = 1; char s = fgc();
for ( ; s < '0' || '9' < s; s = fgc() ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = fgc() ) x = x * 10 + ( s ^ '0' );
return x * f;
}
typedef unsigned long long ULL;
const int MAXD = 468751, W = 6;
int q;
ULL dig[2][MAXD + 5];
std::set<int> dif;
inline void add( const bool id, const int k ) {
int b = k >> W, p = k - ( b << W );
ULL tmp = dig[id][b];
if ( ( dig[id][b] += 1ull << p ) < tmp ) add( id, b + 1 << W );
if ( dig[id][b] == dig[id ^ 1][b] ) dif.erase( b );
else dif.insert( b );
}
inline bool query( const int k ) {
int b = k >> W, p = k - ( b << W );
bool f = ( dig[0][b] >> p & 1 ) != ( dig[1][b] >> p & 1 );
ULL u0 = dig[0][b] & ( ( 1ull << p ) - 1ull );
ULL u1 = dig[1][b] & ( ( 1ull << p ) - 1ull );
if ( u0 != u1 ) return f ? u0 >= u1 : u0 < u1;
std::set<int>::iterator it( dif.lower_bound( b ) );
if ( it == dif.begin() ) return f;
--it;
return f ? dig[0][*it] >= dig[1][*it] : dig[0][*it] < dig[1][*it];
}
int main() {
q = rint(), rint(), rint(), rint();
for ( int op, a, b; q--; ) {
op = rint(), a = rint();
if ( op == 1 ) {
b = rint();
bool f = a < 0;
if ( f ) a = -a;
for ( int i = 0; 1 << i <= a; ++i ) if ( a >> i & 1 ) {
add( f, b + i );
}
} else {
putchar( '0' ^ query( a ) ), putchar( '\n' );
}
}
return 0;
}
标签:洛谷,NOI,int,rint,dig,Solution,return,mathcal,bit
From: https://www.cnblogs.com/rainybunny/p/16585402.html