【线段树压位、压位+SET】BZOJ4942 [Noi2017]整数

题面在这里

​

好像线段树压位可以直接暴艹过去……

​

考虑只有加法，那么暴力加1均摊复杂度是\(O(1)\)的

因为每次加法都只会产生1个1，而1只能在加法中产生

所以每次进位变成0的1都对应着一次加法，均摊复杂度\(O(1)\)

​

然后这个有减法，我们就分别存加操作和减操作的绝对值

把\(a\)拆分成\(\sum 2^k\)，于是修改直接压位处理是\(O(1)\)的

每次询问两个数相减的二进制第k位

考虑两个串在\([0,k-1]\)的大小，显然 加串\(\ge\)减串 时，答案是第k位的异或值

否则是第k位的同或值

直接用set维护两个\(unsigned\ int\)串不同的位置

比大小就是lower_bound找到第一个不等的位置比较

然后就好了……代码贼短

​

示例程序：

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
typedef unsigned int uint;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=1000005;
int q;
uint a[2][maxn];
set<int> S;
void ist(int x,int d){
	uint i=x/32,j=x%32;
	while (1){
		uint t=a[d][i];
		a[d][i]+=(1<<j);
		if (a[d][i]==a[d^1][i]) S.erase(i);else S.insert(i);
		if (a[d][i]>t) return;
		i++;j=0;
	}
}
bool check(int k){
	uint i=k/32,j=k%32;
	if ((a[0][i]&(1<<j)-1)!=(a[1][i]&(1<<j)-1)) return (a[0][i]&(1<<j)-1)<(a[1][i]&(1<<j)-1);
	set<int>::iterator it=S.lower_bound(i);
	if (it==S.begin()) return 1; it--;
	return a[0][*it]<a[1][*it];
}
int main(){
	q=red();red(),red(),red();
	while (q--)
	 if (red()==1){
	 	int x=red(),k=red(),d=(x>0?1:(x=-x,0));
	 	for (int i=0;i<=30;i++)
	 	 if (x&(1<<i)) ist(i+k,d);
	 }else{
	 	int k=red(); uint i=k/32,j=k%32;
	 	if (check(k)) putchar((((a[0][i]>>j)^(a[1][i]>>j))&1)+48);
	 	 else putchar((((a[0][i]>>j)^(a[1][i]>>j)^1)&1)+48);
	 	putchar('\n');
	 }
	return 0;
}