代码

#include<cstdio>
#include<set>
using namespace std;

int read(){
  static int x, fl; static char c;
  x=fl=0; c=getchar();
  for (;!(c>='0'&&c<='9');c=getchar()) if (c=='-') fl=1;
  for (; (c>='0'&&c<='9');c=getchar()) x=x*10+c-'0';
  return fl? -x: x;
}

int n;
#define uint unsigned int
uint a[2][1001000];
set<int>S;

void gao(int who,int p,uint v){
  for (;v;++p){
    v+=a[who][p];
    a[who][p]=v&((1<<30)-1);
    v>>=30;
    if (a[0][p]!=a[1][p]) S.insert(p);
    else S.erase(p);
  }
}

void add(int who,uint v,int p){
  int bel=p/30, las=p%30;
  gao(who,bel,(v&((1<<30-las)-1))<<las);
  gao(who,bel+1,v>>30-las);
}

int lower(int p){
  if (p<0) return 0;
  int bel=p/30, las=p%30, b=(1<<las+1)-1;
  if ((a[0][bel]&b)!=(a[1][bel]&b))
    return (a[0][bel]&b)<(a[1][bel]&b);
  set<int>::iterator it=S.upper_bound(bel-1);
  if (it==S.begin()) return 0;
  --it; return a[0][*it]<a[1][*it];
}

int cal(int p){
  int bel=p/30, las=p%30;
  int res=(a[0][bel]>>las&1)^(a[1][bel]>>las&1);
  return res^lower(p-1);
}

int main(){
  n=read(); read(); read(); read();
  int t, p, v;
  for (int cas=1;cas<=n;++cas){
    t=read();
    if (t==1){
      v=read(); p=read();
      if (v>0) add(0,v,p);
      if (v<0) add(1,-v,p);
    }else{
      p=read();
      puts(cal(p)? "1": "0");
    }
  }
}

评测结果