题目

传送门 to UOJ

思路

整除操作,可以考虑暴力。问题在于,我们要怎样维护可以快速 bitand\rm bitandbitand 的结构,使得整除之后暴力 pushUp 的速度不算太慢?

很容易想到拆位,每一位记录一下,有多少个数在这一位上是 111 。那么做 bitand\rm bitandbitand 需要 O(log⁡V)\mathcal O(\log V)O(logV),整除之后修改结果也是 O(log⁡V)\mathcal O(\log V)O(logV) 。整除过程中,每个节点势能为 O(log⁡V)\mathcal O(\log V)O(logV),所以分析出上界为 O(nlog⁡2V)\mathcal O(n\log^2 V)O(nlog2V) 。而 log⁡V\log VlogV 达到了惊人的 128128128,根本过不了。

这时候,我们想到一个神奇的 “分块”,那就是 bitset\rm bitsetbitset 。同时对 ω\omegaω 位进行操作,却是 O(1)\mathcal O(1)O(1) 的时间,这是一个 bug\rm bugbug 般的存在!因为它真的是 让暴力变快,而不是减少冗余信息计算!

于是考虑将那 log⁡V\log VlogV 个二进制位,用 bitset\rm bitsetbitset 实现 “变为零” 的操作。但是 bitset\rm bitsetbitset 又只针对 0,10,10,1 啊!所以我们对 值(因变量) 进行拆位。有一种比较形象的说法是,将第 xxx 个 bit\text{bit}bit 的出现次数 cxc_xcx​ 用二进制写出来(写在一列上),那么原本我们是按照列存储,现在变为按照行存储,因为行数更少。

用 rxr_xrx​ 状压存储出现次数的 x-bitx\text{-bit}x-bit 为 111 的比特位。bitand\rm bitandbitand 操作就是对每个 rxr_xrx​ 进行按位与。时间复杂度 O(log⁡L)\mathcal O(\log L)O(logL),其中 LLL 为区间长度。而 pushUp 可以用大整数加法的方式实现(相当于并行,毕竟进位也是 0,10,10,1,也可以用 bitset\rm bitsetbitset 存储),也是 O(log⁡L)\mathcal O(\log L)O(logL) 。

复杂度是什么呢?老规矩,势能。一个被完全覆盖的节点要往下递归,最多 O(log⁡V)\mathcal O(\log V)O(logV) 次。整棵树的代价和 T(n)=2T(n2)+O(log⁡n)=O(n)T(n)=2T({n\over 2})+\mathcal O(\log n)=\mathcal O(n)T(n)=2T(2n​)+O(logn)=O(n),所以势能带来的代价是 O(nlog⁡V)\mathcal O(n\log V)O(nlogV),加上一般复杂度 O(qlog⁡2n)\mathcal O(q\log^2 n)O(qlog2n) 可过。

代码

容易编译超时,建议 Clang 编译。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())if(c == '-') f = -f;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}typedef __uint128_t ulllong;
void readHex(ulllong &v){static int8_t haxi[1<<8];static bool done = false; if(!done){memset(haxi,-1,1<<8); // not gooddone = true; rep(i,0,9) haxi[i^48] = int8_t(i);rep(i,'a','f') haxi[i] = int8_t(i-'a'+10);}v = 0; int c = getchar(); // read by hexfor(; ~haxi[c]; c=getchar()) v = (v<<4)^haxi[c];
}
void writeHex(const ulllong &v){if(v>>4) writeHex(v>>4);if((v&15) < 10) putchar(int((v&15)^48));else putchar(int((v&15)-10+'a'));
}const int LOST = 1<<19; ///< length of segment tree
ulllong a[LOST|1]; ///< original array
template < int dep > ///< log(len)+1
struct Node{Node<dep-1> lson, rson;ulllong v[dep], sum, tag;Node():tag(~ulllong(0)){}void operator &= (const ulllong &w){tag &= w, sum = 0;for(int i=0; i!=dep; ++i)v[i] &= w, sum += v[i]<<i;}void pushDown(){lson &= tag, rson &= tag;tag = compl ulllong(0);}void pushUp(){ulllong &co = v[dep-1] = 0;for(int i=0; i!=dep-1; ++i){v[i] = lson.v[i] xor co xor rson.v[i];co = (lson.v[i]&(co|rson.v[i]))|(co&rson.v[i]);}sum = lson.sum+rson.sum;}void build(int l=1,int r=LOST){lson.build(l,(l+r)>>1), rson.build((l+r+2)>>1,r);pushUp(); // update sum and v}void div(int ql,int qr,const ulllong &qv,int l=1,int r=LOST){if(!sum || qr < l || r < ql) return ; // emptypushDown(), lson.div(ql,qr,qv,l,(l+r)>>1);rson.div(ql,qr,qv,(l+r+2)>>1,r), pushUp();}void band(int ql,int qr,const ulllong &qv,int l=1,int r=LOST){if(qr < l || r < ql) return ;if(ql <= l && r <= qr) return void(*this &= qv);pushDown(), lson.band(ql,qr,qv,l,(l+r)>>1);rson.band(ql,qr,qv,(l+r+2)>>1,r), pushUp();}ulllong query(int ql,int qr,int l=1,int r=LOST){if(qr < l || r < ql) return ulllong(0);if(ql <= l && r <= qr) return sum;pushDown(); return lson.query(ql,qr,l,(l+r)>>1)+ rson.query(ql,qr,(l+r+2)>>1,r);}
};
template < > // specialization
struct Node<1>{ulllong sum, *v;Node():sum(0),v(&sum){}void operator &= (const ulllong &w){sum &= w; // the same as v[0]}void div(int ql,int qr,const ulllong &qv,int l,int r){if(ql <= l && r <= qr) sum /= qv;}void band(int ql,int qr,const ulllong &qv,int l,int r){if(ql <= l && r <= qr) sum &= qv;}void build(int l,int r){ sum = a[l]; }ulllong query(int ql,int qr,int l,int r){return (ql <= l && r <= qr) ? sum : 0;}
};Node<20> sgt;
int main(){int n = readint(), q = readint();rep(i,1,n) readHex(a[i]);sgt.build();for(int op,l,r; q; --q){op = readint(), l = readint(), r = readint();if(op == 3){writeHex(sgt.query(l,r));putchar('\n'); continue;}ulllong v; readHex(v);if(op == 1 && v != 1) sgt.div(l,r,v);else if(op == 2) sgt.band(l,r,v);}return 0;
}

[UNR#5]诡异操作相关推荐

  1. 遇劣势变蠢、发语音嘲讽人类……OpenAI这些奇葩DOTA操作跟谁学的?

    夏乙 中奇 假装发自 温哥华 量子位 新浪科技 联合报道 刚刚,中国网友全村的希望LGD惜败温哥华: 两天前,AI全村的希望OpenAI Five更是在二连败之后,提前为TI之旅画上了句号. 月初轻松 ...

  2. CSS 标签诡异添加 injected stylesheet

    injected stylesheet css的一个异常标签,今天出现一个非常诡异的事情,就是在css标签里面,我并没有添加 injected stylesheet   这类的属性反而在有些电脑上会自 ...

  3. 8.11模拟:数据结构

    文章目录 前言 考场 复盘 T1 forward T2 basket T4 square 总结 前言 320分 还不错啦 没有挂分还是很可贵的 (暴力TLE就不怪我了) T4反过来想其实就很可做了 逆 ...

  4. YBTOJ:前缀数组(KMP)

    文章目录 题目描述 解析 代码 题目描述 解析 题面脸上写着5个大字:我是KMP 但是本题没有自己做出来...我一开始的思路其实很接近题解了,只是被我舍弃了qwq. 后来卡在暴力nL2的瓶颈上,用了个 ...

  5. conda安装GPU版pytorch,结果却是cpu版本[找到问题根源,从容解决]

    conda安装GPU版pytorch,结果却是cpu版本[找到问题根源,从容解决] 一.问题描述 二.网上解决方案罗列[此节为反面方案罗列!!!] 三.发现的根本原因[独家] 3.1 pytorch文 ...

  6. Solidity 安全:已知攻击方法和常见防御模式综合列表

    目录 重入漏洞 漏洞 预防技术 真实世界的例子:DAO 算法上下溢出 漏洞 预防技术 实际示例:PoWHC和批量传输溢出(CVE-2018-10299) 不期而至的Ether 漏洞 预防技术 真实世界 ...

  7. 文本特征提取——one-hot

    独热编码即 One-Hot 编码,又称一位有效编码.其方法是使用 N位状态寄存器来对 N个状态进行编码,每个状态都有它独立的寄存器位,并且在任意时候,其中只有一位有效. One-Hot 编码是分类变量 ...

  8. PHP采集器querylist

    官方文档链接 官方连接:http://www.querylist.cc/ 注意事项 如果composer安装 建议切换一下镜像地址,因为阿里云镜像会提示 输入账号和密码的诡异操作 E:\phpstud ...

  9. MFZ 杯 のDFS BFS总结

    新学了dps和bfs,, 这算是第一次实战, 挖出了不少的诡异的错误,,这里小结一下题目,, 等会再给一些题写个详细题解 再写个bfs,dfs总结 第一题:A - Red and Black 这题是我 ...

最新文章

  1. JasperReport报表设计4
  2. colsure php_PHP Closure(闭包)类详解
  3. C语言图书管理系统注册功能,图书管理系统的c语言源程序
  4. phar.php error 139,composer.phar 安装出现PHP Fatal error解决办法
  5. linux elf格式 全局指针表got call跳转表plt 简介
  6. android 上拉隐藏布局,Recycleview上拉隐藏与下拉显示
  7. 网络推广中网络推广专员如何培养与搜索引擎的友好度和信任度
  8. 【转】Java里如何实现线程间通信
  9. StoreFront 登陆页面的话持续时间
  10. 小余学调度:学习记录(2021.8.30-2021-9.5)
  11. MusicXML 3.0 (4) - 谱号
  12. 阿里云何川:开放兼容的云,计算巢帮助合作伙伴云化升级
  13. java期末项目实验答辩毕业设计工程项目源码
  14. 查询oracle 数据库中回滚段中一个时间点被修改的表数据并还原表中原来数据
  15. Dockerfile 学习:Docker Alpine PHP 安装扩展
  16. 2019美赛b题:基于Weighted-K-means聚类模型的选址
  17. Python 合并两个或多个pdf文件(获取pdf文件指定页)
  18. 国家职业资格:计算机网络管理员
  19. bitbucket 预览html,Bitbucket使用方法
  20. 怎样使用github?(转)

热门文章

  1. pr2020lut导入_pr lut预设怎么安装-PR下导入lut预设的方法 - 河东软件园
  2. python令人迷惑的duplicated和drop_duplicates()
  3. 使用GPU进行神经网络计算详解
  4. 浮动以及清楚浮动的几种方法
  5. 无条码商品新建商品档案,搭配蓝牙便携打印机移动打印条码标签
  6. java项目如何判断一个请求是否为AJAX请求
  7. c++ 问题:查找预编译头时遇到意外的文件结尾
  8. 零基础怎么做好海报重叠设计
  9. python列表中的元素可以是不同类型_Python列表中所有元素必须为相同类型的数据。...
  10. word批量修改交叉引用颜色