LOJ#2302 整数
2024-10-13 03:09:47
解：发现这苟东西是个3千万位的二进制数......毒瘤吧。
拆位考虑，如果一个地方本来是1然后+1，就会把它和它前面连续的一段1变成0，并把第一个0变成1。
如果本来是0然后-1了，就会把它和它前面连续的一段0变成1，并把第一个1变成0。
然后发现这两个操作都可以用线段树。于是得到了一个60分算法。
然后压位，线段树每一位表示30个二进制位，可以发现之前的性质没变：如果一个地方加了后超过了(1<<30)-1，就把前面的一段1变成0，第一个0变成1。减法同理。
注意加法爆了就对(1<<30)-1取&，减法爆了就加上(1<<30)，这里千万不能-1，因为是从前面借的。
有个地方坑死我了......看这里。
应该长这样...
#include <bits/stdc++.h>
inline void read(int &x) {
x = ;
char c = getchar();
bool f = ;
while(c < '' || c > '') {
if(c == '-') f = ;
c = getchar();
}
while(c >= '' && c <= '') {
x = x * + c - ;
c = getchar();
}
if(f) x = (~x) + ;
return;
}
const int N = , FULL = ( << ) - ;
inline void out(int x) {
for(int i = ; i <= ; i++) printf("%d", (x >> i) & );
return;
}
int n, tag[N], val[N], sta[N], lm;
/// tag is_same now_state
inline void pushup(int o) {
if(val[o << ] == val[o << | ] && val[o << ] != -) {
val[o] = val[o << ];
}
else val[o] = -;
return;
}
inline void pushdown(int o) {
if(tag[o] != -) {
tag[o << ] = tag[o << | ] = tag[o];
val[o << ] = val[o << | ] = tag[o];
sta[o << ] = sta[o << | ] = (tag[o] ? FULL : );
tag[o] = -;
}
return;
}
void changeAdd(int l, int r, int o) {
if(l == r) {
for(int i = ; i < ; i++) {
if(((sta[o] >> i) & ) == ) {
sta[o] |= ( << i);
break;
}
else {
sta[o] &= ~( << i);
}
}
if(sta[o] == FULL) val[o] = ;
else if(sta[o] == ) val[o] = ;
else val[o] = -;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(val[o << ] != ) {
changeAdd(l, mid, o << );
}
else {
changeAdd(mid + , r, o << | );
sta[o << ] = val[o << ] = tag[o << ] = ;
}
pushup(o);
return;
}
void changeDel(int l, int r, int o) {
if(l == r) {
for(int i = ; i < ; i++) {
if((sta[o] >> i) & ) {
sta[o] &= ~( << i);
break;
}
else {
sta[o] |= ( << i);
}
}
if(sta[o] == FULL) val[o] = ;
else if(sta[o] == ) val[o] = ;
else val[o] = -;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(val[o << ] != ) {
changeDel(l, mid, o << );
}
else {
changeDel(mid + , r, o << | );
val[o << ] = tag[o << ] = ;
sta[o << ] = FULL;
}
pushup(o);
return;
}
int add(int p, int v, int l, int r, int o) {
if(l == r) {
sta[o] += v;
int t = ;
if(sta[o] > FULL) {
sta[o] &= FULL;
t = ;
}
if(sta[o] == FULL) val[o] = ;
else if(sta[o] == ) val[o] = ;
else val[o] = -;
return t;
}
int mid = (l + r) >> ;
pushdown(o);
int t;
if(p <= mid) {
t = add(p, v, l, mid, o << );
pushup(o);
if(t && val[o << | ] != ) {
changeAdd(mid + , r, o << | );
pushup(o);
return ;
}
else if(t) {
tag[o << | ] = val[o << | ] = sta[o << | ] = ;
pushup(o);
return ;
}
else return ;
}
else {
t = add(p, v, mid + , r, o << | );
pushup(o);
return t;
}
return ;
}
int del(int p, int v, int l, int r, int o) {
if(l == r) {
sta[o] -= v;
int t = ;
if(sta[o] < ) {
sta[o] += FULL + ;
t = ;
}
if(sta[o] == FULL) val[o] = ;
else if(sta[o] == ) val[o] = ;
else val[o] = -;
return t;
}
int mid = (l + r) >> ;
pushdown(o);
int t;
if(p <= mid) {
t = del(p, v, l, mid, o << );
pushup(o);
if(t && val[o << | ] != ) {
changeDel(mid + , r, o << | );
pushup(o);
return ;
}
else if(t) {
tag[o << | ] = val[o << | ] = ;
sta[o << | ] = FULL;
pushup(o);
return ;
}
else return ;
}
else {
t = del(p, v, mid + , r, o << | );
pushup(o);
return t;
}
return ;
}
inline void Add(int p, int x) { /// node p add x
if(!x) return;
add(p, x, , lm, );
return;
}
inline void Del(int p, int x) {
if(!x) return;
del(p, x, , lm, );
return;
}
int ask(int p, int l, int r, int o) {
if(l == r) {
p -= (l - ) * ;
return (sta[o] >> p) & ;
}
int mid = (l + r) >> ;
pushdown(o);
if(p <= mid * - ) return ask(p, l, mid, o << );
else return ask(p, mid + , r, o << | );
}
void out(int l, int r, int o) {
if(l == r) {
return;
}
int mid = (l + r) >> ;
pushdown(o);
out(l, mid, o << );
out(mid + , r, o << | );
return;
}
int main() {
int t1, t2, t3;
memset(tag, -, sizeof(tag));
scanf("%d%d%d%d", &n, &t1, &t2, &t3);
lm = std::max(n + , );
for(int i = , f, x, y; i <= n; i++) {
scanf("%d%d", &f, &x);
if(f == ) {
printf("%d\n", ask(x, , lm, ));
}
else {
scanf("%d", &y);
int t, fd = ;
if(x < ) {
x = -x;
fd = ;
}
if(!fd) { /// add
t = (x << (y % )) & FULL;
Add(y / + , t);
t = x >> ( - (y % ));
Add(y / + , t);
}
else { /// dec
t = (x << (y % )) & FULL;
Del(y / + , t);
t = x >> ( - (y % ));
Del(y / + , t);
}
}
}
return ;
}
AC代码
最新文章
- asp.net dataTable转换成Json格式
- vuejs切换视图同时保持状态
- DEV柱状图----傻瓜版
- 什么是JavaScript闭包终极全解之一——基础概念
- System.getProperties()对应的key/value列表
- C#消息模拟
- SQL 有父标识的 递归查询
- andriod系统裁剪心得
- 使用php实现爬虫程序 套取网站的图片实例
- Ubuntu14 或是其他系统当中关于sublimeSFTP超时解决方法
- .Net 缓存依赖详解
- bootstrap4中文版（纯手工翻译）
- react 开发知识准备
- MyBatis(2)——MyBatis 深入学习
- 转：函数signal()
- 【转】sentry 实时事件日志聚合平台
- Mybatis逆向工程 —— ResultMaps collection already contains value for ***
- php四个常用类封装
- IT技术需求建立时需考虑的因素
- sublime text插件推荐