【BZOJ4942】[NOI2017]整数(分块)
2024-09-08 10:09:53
【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;
}
最新文章
- JavaWeb学习总结(五十二)——使用JavaMail创建邮件和发送邮件
- JS中new到底发生了什么
- php高级研发或架构师必了解---很多问题面试中常问到!
- C++ typedef用法小结
- 速冻熟食制品的QS的申请办法
- codeforces D. Painting The Wall
- Windows7在自由的虚拟机(微软官方虚拟机)
- 解决mongodb设备mongod命令不是内部或外部的命令
- 【LeetCode】98. Validate Binary Search Tree
- jquery左右切换的无缝滚动轮播图
- grunt对象之api
- gcc创建静态库和共享库
- linux基础和vim基本使用
- webpack学习最基本的使用方式(一)
- TCP/IP OPTION字段
- Linux之grep的使用
- 微软BI 之SSAS 系列 - 多维数据集维度用法之一 引用维度 Referenced Dimension
- Go-学习之路
- easyui-datebox 只能获取当前日期以前的日期
- 如何使用gradle打jar包
热门文章
- 使用jq操作脚本生成元素的事件
- maven 学习---Maven 插件
- Java 打印HelloKitty
- Google Analytics 学习笔记三 —— GA常用术语
- 011.maven 继承与聚合
- 【PHP】关于系统性能追踪工具molten
- windows elasticsearch使用ik分词器插件后启动报错java.security.AccessControlException: access denied (";java.io.FilePermission"; ";D:...........\plugins\ik-analyzer\config\IKAnalyzer.cfg.xml"; ";read";)
- centos安装elasticsearch-rtf5.5.4
- Codeforces Round #304 (Div. 2)(CF546D) Soldier and Number Game(线性筛)
- 201871010104-陈园园 《面向对象程序设计(java)》第六——七周学习总结