提供一个来自 CF 大佬 adament 的有趣思路。
首先我们知道的是一个只增加的 \(b\) 进制整数计数器，如果 \(b\) 是常数那么复杂度是均摊 \(O(1)\) 的。证明只需要考虑将 \(b\) 进制中为 \(b-1\) 的所有位的位数当成势能，那么每一次进位一定是 \(b-1\to 0\) 一定会消耗势能函数。
但这道题有加又有减，问题出在了可能有“退位” \(0\to b-1\)，这时导致了势能函数的增加，这也是为什么均摊算法通常不能支持撤回。常规的做法是把加减分开考虑变成只加的情况。其实还有一种更简单的做法：我们不限制一个位上的值一定是 \([0,b)\) 的，而是 \((-b,b)\)。此时的进位/退位的形式都是 \(1-b\to 0\) 或 \(b-1 \to 0\)。我们将非零位的个数当成势能，这样进位/退位都会减小势能，而势能函数的总量就是 \(O(n)\) 的了。
然而现在要查询原数某一位，如何来还原原数的一位呢？我们发现进位对于下一位的影响总是 \(\pm 1\) 的，我们只需要找到我们当前查询的位的严格非零前驱，判断一下它是否为负，如果是当前位就需要 \(-1\) 然后输出。
具体到这题，我们需要将数 \(T\) 个压成一位，我实现压了 \(62\) 位。维护动态前驱用了 zkw 线段树上 finger search（只是减小常数）。输出时有个小技巧，负数的补码实际上就是它在二进制下的表示，所以提取负数的某一维可以直接跟正数一起位运算就可以了。
代码非常好写，跑得也飞快，复杂度 \(O(\frac{30n\log n}{T})\)。
#include <cstdio>
#include <bitset>
using namespace std;
int read(){
char c=getchar();int x=0;bool f=0;
while(c<48||c>57) f|=(c=='-'),c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
if(f) return -x;
return x;
}
const int lT=62,sT=30;
typedef long long ll;
const ll Base=(1ll<<lT);
int q,dlt;
namespace ds{
bitset<1<<20> f;
void ins(int x){
x+=dlt;
while(!f[x]) f[x]=1,x>>=1;
}
void del(int x){
x+=dlt;
while(f[x]){
f[x]=0;
if(f[x^1]) return;
x>>=1;
}
}
int pre(int x){
if(!x) return -1;
x+=dlt-1;
if(f[x]) return x-dlt;
while(x>1){
if((x&1)&&f[x^1]) break;
x>>=1;
}
x^=1;
if(!x) return -1;
while(x<dlt){x<<=1;if(f[x^1]) x^=1;}
return x-dlt;
}
}
ll a[500003];
void upd(int x,ll v){
if(!v) return;
if(!a[x]) ds::ins(x);
a[x]+=v;
if(!a[x]) ds::del(x);
}
void inc(int x,int t){
bool sig=0;
if(x<0) sig=1,x=-x;
int bl=t/lT,wid=lT*(bl+1)-t;
if(wid>sT) wid=sT;
if(sig){
upd(bl,-((ll)(x&((1ll<<wid)-1))<<(t-bl*lT)));
upd(bl+1,-(x>>wid));
}
else{
upd(bl,(ll)(x&((1ll<<wid)-1))<<(t-bl*lT));
upd(bl+1,(x>>wid));
}
ll tmp=0;
int fl=0;
do{
upd(bl,tmp);
tmp=a[bl]/Base;
upd(bl,-Base*tmp);
++bl;++fl;
}while(fl<2||tmp);
}
bool qry(int x){
int bl=x/lT,p=ds::pre(bl);x%=lT;
if(p>=0&&a[p]<0) return (a[bl]-1)>>x&1;
else return a[bl]>>x&1;
}
int main(){
q=read();read();read();read();
for(dlt=1;dlt<=(q>>1)+1;dlt<<=1);
while(q--){
int op=read(),x=read();
if(op==1) inc(x,read());
else printf("%d\n",qry(x));
}
return 0;
}