题解 P3822 【[NOI2017]整数】

先膜一波楼下用2^30，2^60,2^16进制的julao _________________ 其实我们发现有个神奇的东西叫unsinged int，通过这个神奇的东西我们可以轻而易举的绕开高精度的乱七八糟的分类讨论，那么介绍在这里介绍一个非常神奇的算法好了…… _____________ ## 本题题解 ### 前置芝士:二进制计数器的均摊复杂度 在《算法导论》的摊还分析一节举了一个小栗子，一个二进制计数器，如果暴力的每次给它加1，每次做高精度加法的话，我们会发现它的均摊复杂度是$O(1)$而不是$O(logn)$具体证明是考虑每个对于每个二的整次幂我们其实仅仅做了$O(n)$次操作，只是多了一个大概是2的常数，而一个任意数和最接近它的二的整次幂最多差2倍，因此我们可以证明n次暴力高精加1的单次复杂度是均摊$O(1)$的 _____________ ### 局限性 但是如果你对均摊的复杂度略有了解的话，会知道均摊的复杂度有一个问题，它不支持回撤……，因为均摊复杂度意味着有一步或者多步的复杂度将会很高，高出了平均复杂度，而如果我们反复回撤这几步我们就会华丽的T飞掉 但问题这道题就是让我们支持减去一个数，而这和回撤没什么区别…… 此时继续使用暴力，先不管空间的问题，我们会发现减去的数可能会让我们反复回撤几个非常高复杂度的步骤，此时我们就T飞了 或者还有更坏的情况，考虑下面这个操作，先让第$10^6$位加1，然后在第一位减1，这会立即导致我们做$10^6$个操作，如果我们接下来的$10^6$个操作里每次反复加1或者减1的话我们会反复重复这些操作……然后我们就会T的飞起 --------------------------- ## 解决 所以我们唯一的做法就是对于加法和减法分别用暴力维护它们的绝对值，这样才能保证复杂度的正确性 但是我们发现这样每一次加法需要拆成$O(log{10^9})$的加1，显然复杂度还是带一个$log$会T飞……e 所有我们需要想一些奇技淫巧来帮助我们加速…… 于是我们想到了神奇的unsigned int，我们可以将这个非常大的数使用unsigned int 每32位分成一个小块，这样原来的第b位就变成了第$b/32$个数的第$b\%32$位，然后我们发现因为a的值不是很大，因此每次最多对两个unsigned int数进行暴力的高精度加法，复杂度变成了均摊$O(1)$，或者你可以理解成进行进行了$2^{32}$进制表示也可以。 那么具体实现的时候我们直接对unsigned int进行无脑加法使其自然溢出即可，然后对于判断进位这个有一个奇技淫巧，因为加的数不超过unsigned int，因此我们直接判断加之前和之后的大小，如果越加越小就可以认为是进了一位，跳到下一个块去做加法，然后我们就可以以均摊$O(n)$的复杂度分别维护正的部分和负的部分 现在我们要处理询问了…… 显然我们是不可以无脑提取出来正的这一位01值与负的这一位01值然后无脑相减的……，因为这样我们会少考虑一个非常关键的问题，借位，如果发生了借位，那么0会变成1，1会变成0…… 是否发生借位当然也非常简单了，只需要比较这个位置之后的后缀数字是正的大还是负的大就行了…… 等等……$10^6$长度的数你让我比较大小？ 所以我们比较两个后缀的大小其实有点像比较字符串大小，找到第一个在位置b之后不等的位置然后比较大小即可了…… 问题来了，如何找到第一个不等的位置呢？ 这个问题有点像lower\_bound的查找，但是我们要支持动态的维护不等的位置 好像set就可以维护？ 因为我们修改的32位块最多O(n)个，所以我们大可以修改一个块就检查一下是否和对应的正块或者负块相等，然后在set里erase或者insert这个块的编号，然后我们查找第一个不等位置的时候直接lower\_bound出这个块的编号，然后两个unsigned int进行大小比较即可 注意我们可能需要特判一下不是整块的部分，这个时候我们直接膜一下提取出这个部分就可以啦~ 另外不知道为什么我不支持>>32这个操作……，所以我是通过>>31然后>>1实现的^ 上代码~ ```C #include<cstdio> #include<algorithm> #include<set> using namespace std;const int N=1e6+10;typedef unsigned int uit; uit inc[N];uit dec[N];set <int> s;int n;int t1;int t2;int t3; int main() { scanf("%d%d%d%d",&n,&t1,&t2,&t3);set <int>::iterator it; for(int i=1,t,a,b;i<=n;i++) { scanf("%d",&t); if(t==1) { scanf("%d%d",&a,&b);int p=b/32;int q=b%32;//先转换成块上位置 if(a>0) { uit st=(uit)a<<q;uit ic=(uit)a>>(31-q);ic>>=1;//无脑高精加 uit od=inc[p];inc[p]+=st;ic+=(od>inc[p]);//处理下set if(inc[p]^dec[p])s.insert(p);else if(s.count(p))s.erase(p);p++; while(ic!=0) { od=inc[p];inc[p]+=ic;ic=(od>inc[p]);//判断进位 if(inc[p]^dec[p])s.insert(p);else if(s.count(p))s.erase(p);p++; } } else if(a<0)//负的是一样的 { a=-a; uit st=(uit)a<<q;uit ic=(uit)a>>(31-q);ic>>=1;//这里提取不出来>>32可以>>31然后>>1 uit od=dec[p];dec[p]+=st;ic+=(od>dec[p]); if(inc[p]^dec[p])s.insert(p);else if(s.count(p))s.erase(p);p++; while(ic!=0) { od=dec[p];dec[p]+=ic;ic=(od>dec[p]); if(inc[p]^dec[p])s.insert(p);else if(s.count(p))s.erase(p);p++; } } } else { scanf("%d",&b);int p=b/32;int q=b%32;int ans=((inc[p]>>q)^(dec[p]>>q))&1;//两个位置无脑相减 uit v1=inc[p]%(1<<q);uit v2=dec[p]%(1<<q);//提取非整段部分 if(v1<v2){printf("%d\n",ans^1);}//需要借位 else if(v1>v2||s.empty()||p<=*(s.begin())){printf("%d\n",ans);}//判断下无需借位的情况 else { it=s.lower_bound(p);--it;//lower_bound出前驱(自己的不严格后继--) if(inc[*it]>dec[*it]){printf("%d\n",ans);}//比较大小 else {printf("%d\n",ans^1);}//输出 } } }return 0;//拜拜程序~ } ```