【BZOJ4942】[NOI2017]整数（分块）
题面
题解
暴力就是真正的暴力，直接手动模拟进位就好了。
此时复杂度是模拟的复杂度加上单次询问的\(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;
}