用线段树来模拟加减法过程,维护连续一段中是否全为0/1。

因为数字很大,我们60位压一位来处理。

 #include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define maxn 505050
#define base 60
#define ll long long
using namespace std;
inline ll read() {
ll x=,f=;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
ll n,m,S=(1ll<<)-;
struct Seg {
int al[];
ll tag,val;
}t[maxn*];
void put(int o,ll tmp) {
if(tmp!=-) t[o].val=tmp;
if(tmp==) {t[o].al[]=;t[o].al[]=;t[o].tag=tmp;}
else if(tmp==S) {t[o].al[]=;t[o].al[]=;t[o].tag=tmp;}
else {t[o].al[]=t[o].al[]=;t[o].tag=tmp;}
}
void pushdown(int o) {
int ls=o<<,rs=ls+;
if(t[o].tag!=-) {put(ls,t[o].tag);put(rs,t[o].tag);t[o].tag=-;}
}
void pushup(int o) {
int ls=o<<,rs=ls+;
t[o].al[]=t[ls].al[]&t[rs].al[];
t[o].al[]=t[ls].al[]&t[rs].al[];
}
void build(int l,int r,int o) {
t[o].tag=-,t[o].al[]=;t[o].al[]=;t[o].val=;
if(l==r) return;
int mid=l+r>>,ls=o<<,rs=ls+;
build(l,mid,ls);build(mid+,r,rs);
}
ll query(int l,int r,int o,int x) {
if(l==r) return t[o].val;
pushdown(o);
int mid=l+r>>,ls=o<<,rs=ls+;
if(x<=mid) return query(l,mid,ls,x);
else return query(mid+,r,rs,x);
pushup(o);
}
void change(int l,int r,int o,int L,int R,ll tmp) {
if(L<=l&&R>=r) {put(o,tmp);return;}
pushdown(o);
int mid=l+r>>,ls=o<<,rs=ls+;
if(L<=mid) change(l,mid,ls,L,R,tmp);
if(R>mid) change(mid+,r,rs,L,R,tmp);
pushup(o);
}
int find(int l,int r,int o,int pos,int k) {
if(t[o].al[!k]) return -;
if(l==r) return l;
int mid=l+r>>,ls=o<<,rs=ls+;
pushdown(o);
if(pos<=mid) {
ll tmp=find(l,mid,ls,pos,k);
if(tmp!=-) return tmp;
}
return find(mid+,r,rs,pos,k);
pushup(o);
}
void add(int pos,ll ad) {
ll tmp=query(,n,,pos);change(,n,,pos,pos,(tmp+ad)&S);
if(tmp+ad>S) {
int l=find(,n,,pos+,);
tmp=query(,n,,l);
change(,n,,l,l,tmp+);
if(pos+<=l-) change(,n,,pos+,l-,);
}
}
void del(int pos,ll ad) {
ll tmp=query(,n,,pos);
if(tmp-ad<) change(,n,,pos,pos,(S+tmp-ad+)&S);
else change(,n,,pos,pos,(tmp-ad)&S);
if(tmp-ad<) {
int l=find(,n,,pos+,);
tmp=query(,n,,l);
change(,n,,l,l,tmp-);
if(pos+<=l-) change(,n,,pos+,l-,S);
}
}
int main() {
m=read();read();read();read();n=;build(,n,);
for(int i=;i<=m;i++) {
int tp=read();
if(tp==) {
ll a=read(),b=read();
if(a>) {
ll p=b/base,q=b%base;
ll x=(a<<q)&S;add(p,x);
a>>=base-q;add(p+,a);
}
else {
a=-a;ll p=b/base,q=b%base;
ll x=(a<<q)&S;del(p,x);
a>>=base-q;del(p+,a);
}
}
else {
ll a=read();
printf("%lld\n",(query(,n,,a/base)>>(a%base))&);
}
}
}
/*
10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15
*/

最新文章

  1. 如何同时运行两个tomcat?
  2. CEGUI环境配置
  3. Elasticsearch——Rest API中的常用用法
  4. OMG点菜系统
  5. Python迭代器:捕获Generator的返回值
  6. oracle-3-子查询和常用函数
  7. POJ题目分类(按初级\中级\高级等分类,有助于大家根据个人情况学习)
  8. 设置drawable图片
  9. 使用spool导出数据
  10. 1038: [ZJOI2008]瞭望塔 - BZOJ
  11. HDMI相关知识
  12. 201521123065《java程序设计》第11周学习总结
  13. android HTTP镜像
  14. centos6.7环境半虚拟化软件xen及xm配置工具使用详解
  15. Mac如何找到从AppStore下载的正版Xcode安装包、以及Xcode清理缓存
  16. [Node.js] 04 - Event and Callback
  17. Java基础——String类(二)
  18. Python 判断文件是否存在的三种方法
  19. 【介绍+安装】Nginx的介绍和安装详解
  20. Python Web学习笔记之SOCK_STREAM和SOCK_DGRAM

热门文章

  1. bzoj3205 [Apio2013]机器人
  2. [USACO12DEC] 逃跑的BarnRunning Away From…(主席树)
  3. 利用StringUtils可以避免空指针问题
  4. 安装好dashboard 登录出现错误
  5. apk签名验证机制
  6. mysql命令修改登录用户密码
  7. Chocolatey - Windows Software Management Automation
  8. 用js实现千位分隔符
  9. word2vec 和 doc2vec 词向量表示
  10. webpack4.0.1安装问题及解决方法