【BZOJ4942】[NOI2017]整数（分块）

题面

BZOJ

洛谷

题解

暴力就是真正的暴力，直接手动模拟进位就好了。

此时复杂度是模拟的复杂度加上单次询问的\(O(1)\)。

所以我们需要优化的是模拟的复杂度。

首先如果一位位单位加入，这个复杂度是均摊\(O(1)\)的。因为是均摊，所以我们不能支持撤销（即减法操作），所以加法减法必须分开处理。

对于位运算加法我们考虑压位（或者说分块也是一样的啦）

那么加法就很容易处理了，只需要压位之后找到对应的块，然后直接暴力加上去就行了。

这里稍微注意一下进位的细节。

减法类似处理。

那么最后这样子又变的不好查询了。

而查询的方法就是考虑这一位要不要退位。

退位的话就是加法的和减去减法的和，等价于比较两个后缀大小，比较两个后缀大小可以用\(set\)维护哪些块不相同，完全相同的没有必要比，只需要找到第一个不同的块的就行了。

写法上的话，看到洛谷题解里用\(unsigned\ int\)压\(32\)位，这样子就不需要自己手动取模了，挺方便的。

#include<iostream>

#include<cstdio>

#include<set>

using namespace std;

#define ui unsigned int

#define MAX 1000100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

ui A[MAX],B[MAX];

int n;

set<int> S;

int main()

{

	n=read();read();read();read();

	while(n--)

	{

		int opt=read();

		if(opt==1)

		{

			int a=read(),b=read();

			int p=b/32,r=b%32;

			if(a>0)

			{

				ui s0=(ui)a<<r,s1=r?((ui)a>>(32-r)):0;

				ui lst=A[p];A[p]+=s0;s1+=(lst>A[p]);

				if(A[p]^B[p])S.insert(p);

				else if(S.find(p)!=S.end())S.erase(p);

				++p;

				while(s1)

				{

					lst=A[p];A[p]+=s1;s1=(lst>A[p]);

					if(A[p]^B[p])S.insert(p);

					else if(S.find(p)!=S.end())S.erase(p);

					++p;

				}

			}

			else

			{

				a=-a;

				ui s0=(ui)a<<r,s1=r?((ui)a>>(32-r)):0;

				ui lst=B[p];B[p]+=s0;s1+=(lst>B[p]);

				if(A[p]^B[p])S.insert(p);

				else if(S.find(p)!=S.end())S.erase(p);

				++p;

				while(s1)

				{

					lst=B[p];B[p]+=s1;s1=(lst>B[p]);

					if(A[p]^B[p])S.insert(p);

					else if(S.find(p)!=S.end())S.erase(p);

					++p;

				}

			}

		}

		else

		{

			int a=read();

			int p=a/32,r=a%32;

			int ans=((A[p]>>r)&1)^((B[p]>>r)&1);

			ui va=A[p]&((1<<r)-1),vb=B[p]&((1<<r)-1);

			if(va<vb)ans^=1;

			else if(va>vb||S.empty()||p<=*S.begin());

			else

			{

				set<int>::iterator it=S.lower_bound(p);--it;

				if(A[*it]<B[*it])ans^=1;

			}

			printf("%d\n",ans);

		}

	}

	return 0;

}

【BZOJ4942】[NOI2017]整数（分块）的相关教程结束。