[BZOJ4942][Noi2017]整数 线段树+压位
2024-08-23 03:33:36
用线段树来模拟加减法过程,维护连续一段中是否全为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
*/
最新文章
- 如何同时运行两个tomcat?
- CEGUI环境配置
- Elasticsearch——Rest API中的常用用法
- OMG点菜系统
- Python迭代器:捕获Generator的返回值
- oracle-3-子查询和常用函数
- POJ题目分类(按初级\中级\高级等分类,有助于大家根据个人情况学习)
- 设置drawable图片
- 使用spool导出数据
- 1038: [ZJOI2008]瞭望塔 - BZOJ
- HDMI相关知识
- 201521123065《java程序设计》第11周学习总结
- android HTTP镜像
- centos6.7环境半虚拟化软件xen及xm配置工具使用详解
- Mac如何找到从AppStore下载的正版Xcode安装包、以及Xcode清理缓存
- [Node.js] 04 - Event and Callback
- Java基础——String类(二)
- Python 判断文件是否存在的三种方法
- 【介绍+安装】Nginx的介绍和安装详解
- Python Web学习笔记之SOCK_STREAM和SOCK_DGRAM