首页 > 其他分享 >Solution -「NOI 2017」「洛谷 P3822」整数

Solution -「NOI 2017」「洛谷 P3822」整数

时间:2022-08-14 14:45:56浏览次数:95  
标签:洛谷 NOI int rint dig Solution return mathcal bit

\(\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

相关文章

  • 20220814 idea_SpringBoot_启动 jpa 启动 Access to DialectResolutionInfo canno
    1问题AccesstoDialectResolutionInfocannotbenullwhen'hibernate.dialect'notset 2解决方案2.1未解决直接用这个问题搜索,使用了很......
  • [2011年NOIP提高组] 铺地毯
    [2011年NOIP提高组]铺地毯分析:根据题意,用for循环n张地毯,用if语句判断题目给出的点是否在地毯范围内(地毯左下角的坐标到加上地毯长度后的坐标就是整个地毯的范围),如果在su......
  • [2001年NOIP普及组] 最大公约数和最小公倍数问题
    输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件:1.P,A是正整数2.要求P,Q以x0为最大公约数,以y0为最小公倍数.试求:满足条件的所有可......
  • [2001年NOIP普及组] 最大公约数和最小公倍数问题
    [2001年NOIP普及组]最大公约数和最小公倍数问题分析:根据题意,求最大公约数和最小公倍数,其中有一个点是两数乘积等于两数的最大公约数乘最小公倍数。知道这一点后,用for循......
  • [NOIP2001 提高组] 一元三次方程求解
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ doublea,b,c,d,x1,x2,x3; scanf("%lf%lf%lf%lf",&a,&b,&c,&d); for(doublei=-100;i<=100;i+=0.001)//枚举每个......
  • P1008 [NOIP1998 普及组] 三连击
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ for(inta=123,b,c;a<=329;a++) { b=2*a;c=3*a; if((a%10)*(a/10%10)*(a/100)*(b%10)*(b/10%10)*(b/100)*(c%1......
  • [2011年NOIP提高组] 铺地毯
    首先想到用二维数组,但是内存太大会爆;因为题目说的是最上面的那块地毯,所以暗示我们应该用for循环倒着推,又给了我们每个地毯的大小和位置,那我们直接从后看这块地毯包不包含(x,......
  • [2001年NOIP普及组] 最大公约数和最小公倍数问题
    算法分析:先求出x的所有倍数和这个数是x的多少倍,这样最大公约数的问题解决,再去找能构成符合题意的最小公倍数的数,看是否是最大公约数注意:洛谷上提交需优化,数组范围要够,不能......
  • [2016年NOIP普及组] 回文日期
    试题分析:本题是一道暴力枚举题,我们可以直接从输入的date1开始遍历到date2,其余的我们只需要判断是否超出日期即可。注意:没有00月与00日,这里需要单独判断。代码如下: ......
  • [2001年NOIP普及组] 最大公约数和最小公倍数问题
    试题分析:题目输入x为最大公因数,y为最小公倍数,所以我们可以直接从x开始遍历,运用了<algorithm>库中的__gcd(i,j)函数(求i与j的最大公因数的函数),再根据“两个数最大公约数与最小公......