trick : Trygub num-Toy模板网

这篇具有很好参考价值的文章主要介绍了trick : Trygub num。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

trick大意

我对于这个trick的理解为：支持位运算的高精度
维护一个以 \(b\)为基数的大数 \(N\)，并支持以下功能：

给定（可能是负）整数 \(|x|, |y| \leqslant n\)，将 \(x b^y\)加到 \(N\)。
\(N \geqslant 0\)时，给定\(k\)，打印\(N\)的第\(k\)位数字（指以\(b\)为基底意义下的）。
检查\(N\)是正值、负值还是等于\(0\)。

操作 \(O(\log n)\)均摊时间复杂度和 \(O(q)\)内存。并且只需要map进行实现，相比于线段树等数据结构维护非常的好写。

例题及实现： [NOI2017] 整数

题意简述：一个整数\(x\)，进行\(n\)次操作，分为两种：

将 \(x\) 加上整数 \(a\cdot 2^b\)，其中 \(a\) 为一个整数，\(b\) 为一个非负整数
询问 \(x\) 在用二进制表示时，位权为 \(2^k\) 的位的值（即这一位上的 \(1\) 代表 \(2^k\)）

保证在任何时候，\(x\geqslant 0\)。

对于所有测试点，满足 \(|a| \leqslant 10^9\)；
对于所有测试点，满足 \(0 \leqslant b, k \leqslant 30n\)；
对于所有测试点，满足 \(n \leqslant 1000000\)

这里我们的基底为\(2^{30}\)，感性理解一下：把\(x\)的二进制表示分为若干段，每一段长是\(30\)位，这样每次我们只需要改动最多两段，分别对这两段将原数字位运算为相应位后直接加到数中，多于\(2 ^ {31}\)的进行进位操作，发现其实很像一个\(2^{30}\)进位制，这也是以\(b\)为基底的真正含义。

如果仅有加法的话，时间复杂度均摊是\(O(\log n)\)的。

但是因为我们有减法操作，会在时间复杂度上出现一些问题，如果存在这样一段\(\left[2^{30} - 1, 2^{30} - 1, 2^{30} - 1...\right]\)，对应实际数的二进制位全为 1 。然后有这样一段操作，\(\left\{+1, -1, +1, -1, +1...\right\}\)，也就是说，会不断的进行进位，借位，进位，借位操作，会花费大量的时间。

该trick的应对方法是，将每一块的取值范围由\(\left[0,+base\right)\)转换为\(\left(-base, +base\right)\)，即平衡\(base\)进制 (类比平衡三进制）。

也就是说，只有当大于 \(base\) 或小于 -base。

为什么会想到这样呢，像加法一样，减法其实不需要一为负数就借位，因为不管低位是负的多少，只要绝对值不大于 \(base\) ，只需要借高位的一个，就能把它回满，因此当绝对值大于 \(base\) 时，才进行进位或借，这样均摊复杂度也是\(O(\log n)\)的，而当询问的时侯，才对不满 \(base\) 的借位进行处理。

关于均摊时间复杂度

其实我不是很能证明，但是再次感性理解，就是假设一些段内的数为\([2^{30} - 1,2^{30} - 1,2^{30} - 1,2^{30} - 1...]\) 即对应二进制内全为\(1\)。
显然加一次，他就会往后进很多位花大量时间，虽然这一次花了很多时间，但是呢，需要进位的次数其实是很少的，而不需要进位的时候，直接加又很快，这样下来我们的均摊时间就不是那么慢了。

具体证明看这里

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, t1, t2, t3;

struct Num
{
    const ll base = 1 << 30;
    map<ll,ll> num;
    
    void add(ll a, ll b)
    {
        num[b] += a;
        ll t;
        do
        {
            t = num[b] / base;
            num[b + 1] += t;//进位操作
            num[b] -= t * base;
            if(num[b] == 0)
                num.erase(b);//只关心有数值的数，因此若为0则删去
            b++;
        } while(t);
        if(num[b] == 0)
            num.erase(b);
    }
    
    ll get(ll k)
    {
        auto to = num.lower_bound(k);
        ll res = (to == num.end() || to->first > k) ? 0 : to->second;//若这一位为空，先设为0
        
        if(to != num.end() && prev(to)->second < 0)//若存在比k高的位，并且比k低的位上有负数，则需要借位
            res--;
        return (res + base) % base;//这一步，如果res是负数，则需要向前借位，如果是正数，取模后无影响
    }
} s;

int main()
{
    cin >> n >> t1 >> t2 >> t3;
    while(n--)
    {
        int flag;
        cin >> flag;
        if(flag == 1)
        {
            ll a, b;
            cin >> a >> b;
            s.add(a * (1ll << (b % 30)), b / 30);//在b/30块加a * (1ll << (b % 30))
        }
        else 
        {
            ll k;
            cin >> k;
            cout << ((s.get(k / 30) >> (k % 30)) & 1ll) << "\n";//get得到k/30块内实际的数
        }
    }
    
    
    return 0;
}