#include <set>
#include <iostream>
using namespace std;
using ll = long long;

// kW=30: 每块存储30位; kB=2^30: 块的基数
constexpr int kW = 30, kB = 1 << kW;

int _, q;
// s 存储稀疏的「块索引 -> 块值」映射，只存非零块
// pair 比较规则：先比 first(索引)，再比 second(值)
set<pair<int, int>> s;

/**
 * @brief 从块索引 i 开始，添加值 v（支持负数，自动处理进位/借位）
 * @param i 起始块索引（每块 30 位）
 * @param v 要添加的值（范围约 ±2^30）
 */
void A(int i, ll v) {
  // 找到第一个索引 >= i 的块（lower_bound 按 pair 字典序比较）
  // {i, -kB} 确保匹配到所有 first==i 的元素（因 second >= -kB 恒成立）
  auto j = s.lower_bound({i, -kB});
  
  // 逐块处理进位：每次循环处理当前块，v 右移 30 位进入下一块
  for (; v; v /= kB, ++i) {
    // 🎯 关键：如果当前位置已有块，合并值并删除旧块
    if (j != s.end() && j->first == i) {
      v += j->second;        // 合并旧值
      j = s.erase(j);        // ✅ 删除旧块，j 自动跳到下一个元素
    }
    
    // 🎯 如果当前块有非零余数，插入新块
    // v % kB 可能为负（C++11 起，负数取模结果符号与被除数相同）
    if (v % kB) {
      s.emplace(i, v % kB);  // 插入 {索引, 余数}
      // 注意：插入后 j 仍指向原位置（可能已失效），但下一轮循环会重新计算
    }
    // v /= kB: 处理进位到更高块（相当于右移 30 位）
  }
}

/**
 * @brief 查询块索引 i 的实际值（考虑负数借位）
 * @return 块值归一化到 [0, kB) 范围
 */
int Q(int i) {
  auto j = s.lower_bound({i, -kB});
  
  // 获取当前块的值（不存在则为 0）
  int v = (j == s.end() || j->first != i ? 0 : j->second);
  
  // 🎯 负数借位处理：如果前一个块是负数，当前块需借 1（即减 1）
  // 例如：-1 表示为 {..., {0, -1}}，查询块 0 时需返回 kB-1
  if (j != s.begin() && prev(j)->second < 0) {
    --v;
  }
  
  // 归一化到 [0, kB)：处理负数取模
  return (v + kB) % kB;
}

int main() {
  // 加速 IO
  cin.tie(0)->sync_with_stdio(0);
  
  // 读入操作数 q，忽略三个无用参数（题目格式要求）
  cin >> q >> _ >> _ >> _;
  
  for (int o, x, y; q--; ) {
    cin >> o >> x;
    if (o == 1) {
      // 🎯 操作 1：在位位置 x 处添加/删除值
      cin >> y;
      // 计算：值 = ±|x| * 2^(y%30)，块索引 = y/30
      ll v = (ll)abs(x) << (y % kW);  // x 左移 (y%30) 位
      if (x < 0) v = -v;              // 处理符号
      A(y / kW, v);                   // 从块 y/30 开始添加
    } else {
      // 🎯 操作 2：查询位位置 x 的值（0 或 1）
      // 1. Q(x/kW): 获取块值 [0, 2^30)
      // 2. >> (x%kW): 右移到最低位
      // 3. & 1: 取最低位
      cout << (Q(x / kW) >> (x % kW) & 1) << '\n';
    }
  }
  return 0;
}

参考资料：https://codeforc.es/blog/entry/115626。代码实现上比文中示例更加精细，从而得到了更优的复杂度。

这是一个只需要 std::map 的低门槛单 $\log$ 代码不到 1k 的做法，作为代价，常数会略巨大。

我们考虑直接暴力维护这个二进制数，暴力加，暴力进位，查询就直接查，那么在加法不带负数的情况下实际上复杂度是很对的——为什么？我们考虑 $a$ 恒为 1 的情况，那么唯一复杂度可能出问题的点就是触发连续进位，但问题是每次连续进位的触发会恰消耗一个二进制位上的 1，而每次暴力加会恰增加一个二进制位上的 1。换而言之，连续进位的代价摊下来仅仅是常数而已。回到 $a$ 不一定等于 1，我们发现进位的过程其实可以看成是仅仅把 $a$ 拆成了 $\log$ 个不同位上的 1 加过去了而已。复杂度一个 $\log$，非常便捷。

那么我们回到原题，$a$ 可以是负数了。我们发现退位是可以批量产生二进制位上的 $1$ 的，而消耗同样可以批量产生的 0，这会破坏我们的时间复杂度。我们希望，不要有两个可以批量产出的对象可以互相转化，那我们的做法就对了。我们考虑到原来的做法，可能并不希望 0 成为消耗品。那么我们考虑把 0 减去 1 的时候，不要对整个数的结构产生过大的影响。于是我们可以扩展一下每一位的值，从 $\{0,1\}$ 扩展到 $\{0,1,-1\}$。这个时候，我们连续进位消耗 1，连续退位消耗 -1，而这两者都是不可以批量产出的。于是我们的时间复杂度已经没有问题（指低于平方）了。

至于求给定位上的值，这个事情是显而易见的，我们只需要关心一下给定位上的数码和他的低位中最高位的那一个非 0 数码就可以了。我们可以用 std::map 维护非 0 数码集合，这样就可以快速找到前驱了。

#include <bits/stdc++.h>
using namespace std;
int n, t1, t2, t3;
map<int, int> mp;
void add(int v, int p) {
  mp[p] += v;
  while (true) {
    int d = mp[p] / 2;
    if (!(mp[p] %= 2)) mp.erase(p);
    if (!d) return;
    mp[++p] += d;
  }
}
int query(int p) {
  auto it = mp.lower_bound(p);
  int v = it != mp.end() && it->first == p ? it->second & 1 : 0;
  if (it != mp.begin()) v ^= !~prev(it)->second;
  return v;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> t1 >> t2 >> t3;
  for (int op, x, y; n; --n)
    if (cin >> op >> x, op == 1)
      cin >> y, add(x, y);
    else
      cout << query(x) << '\n';
  return cout << flush, 0;
}

现在我们发现查询的复杂度已经控制在了一个 $\log$，但修改依然是两个（或许写得好已经能过了，但我的实现太拉，搞不定）。我们注意到所有涉及到的迭代器一定都是连续的，那么我们使用迭代器的自增而不是每次重新查询来降低这一部分的复杂度（连续访问 $n$ 个迭代器的复杂度是 $O(n+\log)$ 的）。至于还涉及到可能插入原本不存在的迭代器，这个我们可以使用成员函数 emplace_hint 解决，单次插入的均摊复杂度是常数的。

于是我们的代码就优化到一个 $\log$ 了。

#include <bits/stdc++.h>
using namespace std;
int n, t1, t2, t3;
map<int, int> mp;
void add(int v, int p) {
  auto it = mp.emplace(p, 0).first;
  it->second += v;
  while (true) {
    auto [d, f] = div(it->second, 2);
    auto nit = it;
    if (d) {
      it = mp.emplace_hint(it, ++p, 0);
      it->second += d;
    }
    if (!f)
      mp.erase(nit);
    else
      nit->second = f;
    if (!d) return;
  }
}
int query(int p) {
  auto it = mp.lower_bound(p);
  int v = it != mp.end() && it->first == p ? it->second & 1 : 0;
  if (it != mp.begin()) v ^= !~prev(it)->second;
  return v;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> t1 >> t2 >> t3;
  for (int op, x, y; n; --n)
    if (cin >> op >> x, op == 1)
      cin >> y, add(x, y);
    else
      cout << query(x) << '\n';
  return cout << flush, 0;
}

建议降蓝。

先膜一波楼下用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实现的^

上代码~

#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;//拜拜程序~ 
}