「LOJ 2302」「NOI2017」整数

发表于

在人类智慧的山巅，有着一台字长为 10485761048576 位的超级计算机，著名理论计算机科学家 P 博士正用它进行各种研究。 不幸的是，这天台风切断了电力系统，超级计算机无法工作，而 P 博士明天就要交实验结果了，只好求助于学过 OI 的你……

P 博士将他的计算任务抽象为对一个整数的操作。

具体来说，有一个整数 xx ，一开始为 00。

接下来有 nn 个操作，每个操作都是以下两种类型中的一种：

  • 11 aa bb ：将 xx 加上整数 a⋅2ba \cdot 2 ^ b ，其中 aa 为一个整数，bb 为一个非负整数
  • 22 kk ：询问 xx 在用二进制表示时，位权为 2k2 ^ k​​ 的位的值（即这一位上的 11 代表 2k2 ^ k ）

保证在任何时候，x≥0x \ge 0 。

Constraints

$ n\leq 1000000$ ， ∣a∣≤1000000000|a| \leq 1000000000 ， 0≤b,k≤30⋅n0\leq b,k \leq 30\cdot n

Solution

数据范围提示得很明显……需要压位，每一个数字储存 3030 位。

首先开两个数组，一个储存加法，一个储存减法，修改的时候在两个数组上暴力加法暴力进位即可。

现在考虑处理询问。因为保证在任何时刻， x≥0x \ge 0 ，所以我们判断第 kk 位时其实只与加法、减法第 00 到 k−1k-1 位的数字的大小有关。根据减法的规则，稍微分一下类可得：若后面部分的数字差为负，则答案为相应位上的数字的同或，否则为异或。

判断第 00 到 k−1k-1 位的加法数字和减法数字的大小，等价于判断字典序。找到第一个不相同的位置，判断大小即可。我们使用线段树来维护，利用线段树判断 00 到 k−1k-1 的区间内最靠右的加法数组和减法数组不一样的位置。

时间复杂度 O(nlog2n)O(nlog^2 n) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define lc (x<<1)
#define rc (x<<1|1)
#define LL long long
using namespace std;
const int N=1e6+5;
const int base=1<<30;
int n,t1,t2,t3,op,pos;
LL a,b,p,q,tmp,las,nex;
bool fl;
int L[N*4],R[N*4];
LL add[N],dec[N],id[N],t[N*4];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void build(int x,int l,int r)
{
	L[x]=l;R[x]=r;
	if(l==r){id[l]=x;return;}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void change(int x,LL val)
{
	x=id[x];t[x]^=val;
	while(x!=1){x>>=1;t[x]=max(t[lc],t[rc]);}
}
void modify(LL a,int pos,LL *x)
{
	las=x[pos];nex=x[pos+1];
	while(a)
	{
		x[pos]+=a%base;
		if(x[pos]>=base)
		{
			x[pos+1]+=x[pos]/base;
			x[pos]%=base;
		}
		change(pos,las^x[pos]);
		pos++;a/=base;
		las=nex;nex=x[pos+1];
	}
	if(x[pos]>=base)
	{
		x[pos+1]+=x[pos]/base;
		x[pos]%=base;
	}
	change(pos,las^x[pos]);
}
void find(int x)
{
	x=id[x];
	while(x!=1)
	{
		if((x&1)&&t[x-1]){x--;break;}
		x>>=1;
	}
	if(x==1)return;
	while(L[x]!=R[x])
	{
		if(t[rc])x=rc;
		else x=lc;
	}
	t3=L[x];return;
}
int main()
{
	n=read();t1=read();t2=read();t3=read();
	build(1,1,n+2);
	for(int i=1;i<=n;i++)
	{
		op=read();a=read();
		if(op==1)
		{
			b=read();pos=b/30+1;b%=30;
			if(a==0)continue;
			if(a>0)fl=true;
			else a=-a,fl=false;
			a<<=b;
			if(fl)modify(a,pos,add);
			else modify(a,pos,dec);
		}
		else
		{
			pos=a/30+1;a%=30;
			p=add[pos]%(1<<a);
			q=dec[pos]%(1<<a);
			t1=(add[pos]>>a)&1;
			t2=(dec[pos]>>a)&1;
			if(p!=q)
			{
				if(p>q)printf("%d\n",t1^t2);
				else printf("%d\n",t1==t2);
				continue;
			}
			t3=0;find(pos);
			if(add[t3]>=dec[t3])printf("%d\n",t1^t2);
			else printf("%d\n",t1==t2);
		}
	}
	return 0;
}