XP04 - day09
2026-08-20 20:10:28
发布于：广东
90阅读
0回复
0点赞
重生赛题解
CSP-S 2024解析
线段树区间查询 区间修改 懒标记
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,m,a[N];
struct node{
int mx;
int lz;
}tr[N*4];
void push_up(int u){
tr[u].mx = max(tr[u*2].mx,tr[u*2+1].mx);
}
void push_down(int u){
if(tr[u].lz){
tr[u*2].mx+=tr[u].lz;
tr[u*2+1].mx+=tr[u].lz;
tr[u*2].lz+=tr[u].lz;
tr[u*2+1].lz+=tr[u].lz;
tr[u].lz = 0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u].mx=a[l];
return;
}
int mid =l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int lc,int rc,int x){
if(l>=lc && r<=rc){
tr[u].mx+=x;
tr[u].lz+=x;//懒标记
return;
}
int mid = l+r>>1;
push_down(u);//在递归前，把没有干完的活干完
if(lc<=mid)update(u*2,l,mid,lc,rc,x);
if(rc>=mid+1)update(u*2+1,mid+1,r,lc,rc,x);
push_up(u);
}
int query(int u,int l,int r,int lc,int rc){
//区间覆盖
if(l>=lc && r<=rc){
return tr[u].mx;
}
int mid = l+r>>1;
int mx = -1e18;
push_down(u);//在递归前，把没有干完的活干完
if(lc<=mid)mx = query(u*2,l,mid,lc,rc);
if(rc>=mid+1)mx = max(query(u*2+1,mid+1,r,lc,rc),mx);
return mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);//建树
while(m--){
int op,l,r,x;
cin>>op;
if(op==1){
cin>>l>>r>>x;
update(1,1,n,l,r,x);
}else{
cin>>l>>r;
cout<<query(1,1,n,l,r)<<"\n";
}
}
return 0;
}
线段树
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,m,a[N];
struct node{
int mx;
int mn;
int sum;
}tr[N*4];
void push_up(int u){
tr[u].mx=max(tr[u*2].mx,tr[u*2+1].mx);
tr[u].mn=min(tr[u*2].mn,tr[u*2+1].mn);
tr[u].sum = tr[u*2].sum+tr[u*2+1].sum;
}
void build(int u,int l,int r){
if(l==r){
tr[u].mx=tr[u].mn=tr[u].sum=a[l];
return;
}
int mid = l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
push_up(u);
}
void add(int u,int l,int r,int lc,int rc,int x){
if(l==lc && r==rc){
tr[u].mx = tr[u].sum = tr[u].mn = x;
return;
}
int mid = l+r>>1;
if(lc<=mid)add(u*2,l,mid,lc,rc,x);
if(rc>=mid+1)add(u*2+1,mid+1,r,lc,rc,x);
push_up(u);
}
node sum(int u,int l,int r,int lc,int rc){
if(l>=lc && r<=rc){
return tr[u];
}
int mid = l+r>>1;
node ans = {-1e18,1e18,0};
if(lc<=mid){
node now = sum(u*2,l,mid,lc,rc);
ans.mx = max(now.mx,ans.mx);
ans.mn = min(now.mn,ans.mn);
ans.sum += now.sum;
}
if(rc>=mid+1){
node now = sum(u*2+1,mid+1,r,lc,rc);
ans.mx = max(now.mx,ans.mx);
ans.mn = min(now.mn,ans.mn);
ans.sum += now.sum;
}
return ans;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int op,l,r;
cin>>op>>l>>r;
if(op==1)add(1,1,n,l,l,r);
else if(op==2){
cout<<sum(1,1,n,l,r).mx<<"\n";
}else if(op==3){
cout<<sum(1,1,n,l,r).mn<<"\n";
}else{
cout<<sum(1,1,n,l,r).sum<<"\n";
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,m,a[N];
struct node{
int mx;
}tr[N*4];
void push_up(int u){
tr[u].mx = max(tr[u*2].mx,tr[u*2+1].mx);
}
void build(int u,int l,int r){
if(l==r){
tr[u].mx=a[l];
return;
}
int mid =l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
push_up(u);
}
// u下标 [l,r]线段树 区间 [lc,rc]更新区间 x
// [1,6] [1,3] [4,6] [2,4]
void update(int u,int l,int r,int lc,int rc,int x){
if(l==lc && r==rc){
tr[u].mx = max(tr[u].mx,x);
return;
}
int mid = l+r>>1;
if(lc<=mid)update(u*2,l,mid,lc,rc,x);
if(rc>=mid+1)update(u*2+1,mid+1,r,lc,rc,x);
push_up(u);
}
int query(int u,int l,int r,int lc,int rc){
//区间覆盖
if(l>=lc && r<=rc){
return tr[u].mx;
}
int mid = l+r>>1;
int mx = -1e18;
if(lc<=mid)mx = query(u*2,l,mid,lc,rc);
if(rc>=mid+1)mx = max(query(u*2+1,mid+1,r,lc,rc),mx);
return mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);//建树
while(m--){
char op;
int l,r;
cin>>op>>l>>r;
if(op=='U'){
update(1,1,n,l,l,r);
}else{
cout<<query(1,1,n,l,r)<<"\n";
}
}
return 0;
}
4倍空间证明
bitset【模板题】文档
二、bitset 是什么
1. 从 bool 数组理解 bitset
假设有一个集合，元素编号从 0 到 9。
如果元素 2、5、7 在集合中，我们可以用一个 bool 数组表示：
bool vis[10];
vis[2] = true;
vis[5] = true;
vis[7] = true;
也可以用 bitset 表示：
bitset<10> s;
s[2] = 1;
s[5] = 1;
s[7] = 1;
此时可以理解成：
编号： 9 8 7 6 5 4 3 2 1 0
状态： 0 0 1 0 1 0 0 1 0 0
其中：
1表示这个元素存在。0表示这个元素不存在。
所以：
s[x] == 1
就表示：
元素 x 在集合中。
而：
s[x] == 0
就表示：
元素 x 不在集合中。
三、为什么 bitset 很快
很多学生第一次学 bitset 时会有一个疑问：
它不也是存了很多个 0 和 1 吗？为什么会比 bool 数组快？
关键在于：
普通写法经常是一个元素一个元素处理，而
bitset的集合运算可以一整块一整块处理。
1. 普通 bool 数组怎么求交集
假设有两个集合 A 和 B，每个集合最多有 100000 个元素。
如果用 bool 数组求交集大小，通常会这样写：
int ans = 0;
for(int i = 0; i < n; i++){
if(a[i] && b[i]) ans++;
}
这段代码的意思是：
第 0 位看一次
第 1 位看一次
第 2 位看一次
...
第 99999 位看一次
如果 n = 100000，那么一次交集查询大约要检查 100000 次。
如果有 100000 次查询，最坏可能达到：
100000 * 100000 = 10000000000
也就是一百亿级别，肯定不行。
2. bitset 怎么求交集
使用 bitset 后，交集可以直接写成：
(a & b).count()
这里的 & 不是一个一个元素慢慢做，而是对底层存储的一整块二进制位一起做。
现在把集合看成一排灯泡：
A 集合：101100100101...
B 集合：100110101001...
交集就是：
只有 A 和 B 同一位置都是 1，结果才是 1。
也就是按位与：
A：101100100101
B：100110101001
&：100100100001
bitset 底层通常会把很多个 bit 打包到一个机器字里。
在 64 位机器上，可以粗略理解为：
一次处理 64 个元素的状态。
所以原来需要看 100000 次，现在大约只需要看：
100000 / 64 ≈ 1563
也就是说，一次集合运算从十万级操作，变成了一千多块操作。
这就是 bitset 快的第一层原因。
3. count 为什么也快
count() 用来统计 bitset 中有多少个 1。
比如：
a.count()
表示集合 A 当前有多少个元素。
很多同学会以为 count() 是一个一个 bit 数过去的，其实底层通常会使用 CPU 的快速统计指令，比如 popcount。
可以粗略理解成：
拿到一整块 64 位二进制数，CPU 可以很快算出里面有几个 1。
例如某一块是：
10110100...
CPU 可以很快统计这一块里面有几个 1，不需要你手写循环一个一个判断。
所以：
(a & b).count()
大致分成两步：
第一步：把 A 和 B 按块做 & 运算。
第二步：统计结果中有多少个 1。
每一步都是按块处理，因此非常快。
4. 为什么空间也更省
普通 bool 数组虽然每个位置只表示真或假，但很多环境中一个 bool 可能会占 1 字节。
1 字节 = 8 bit。
也就是说：
bool 数组：一个元素可能用 8 个 bit 存。
bitset：一个元素只用 1 个 bit 存。
如果有 100000 个元素：
bool 数组大约需要 100000 字节。
bitset 大约需要 100000 / 8 = 12500 字节。
bitset 不仅少占空间，而且因为数据更紧凑，更容易放进 CPU 缓存里，**速度也会更好。
5. 总结：bitset 快在哪里
| 原因 | 解释 |
|---|---|
| 位压缩 | 一个元素只占 1 个 bit |
| 批量运算 | 一次可以处理 32 或 64 个状态 |
| CPU 指令快 | &、` |
| 缓存友好 | 数据压缩后更小，更容易被 CPU 快速读取 |
所以 bitset 适合这类问题：
状态只有存在 / 不存在，或者是 / 否。
并且需要大量集合运算。
四、bitset 常用操作
假设：
bitset<100005> a, b;
常用操作如下：
| 操作 | 写法 | 含义 |
|---|---|---|
| 加入元素 x | a[x] = 1 |
让 x 存在于集合 A |
| 删除元素 x | a[x] = 0 |
让 x 不存在于集合 A |
| 反转元素 x | a[x] = a[x] ^ 1 |
有则删，无则加 |
| 统计元素个数 | a.count() |
集合 A 中有多少个元素 |
| 交集 | a & b |
同时在 A 和 B 中的元素 |
| 并集 | `a | b` |
| 对称差 | a ^ b |
只在其中一个集合中的元素 |
| 是否存在任意 1 | a.any() |
是否非空 |
| 是否全是 0 | a.none() |
是否为空 |
五、GNU 扩展函数：_Find_first 和 _Find_next
本题还有两个查询：
- 查询集合中的最小存在元素。
- 查询集合中编号大于等于
L的最小存在元素。
标准 bitset 本身没有提供这种查找函数。
但是在 GNU C++ 中，bitset 有两个非常好用的扩展函数：
_Find_first()
_Find_next(pos)
1. _Find_first()
int ans = a._Find_first();
含义是：
找到 a 中第一个为 1 的位置。
也就是集合中的最小元素。
如果集合为空，它会返回 bitset 的长度。
例如：
const int MAXV = 100000 + 5;
bitset<MAXV> a;
如果 a 为空：
a._Find_first() == MAXV
所以要判断：
if(ans == MAXV) ans = -1;
2. _Find_next(pos)
int ans = a._Find_next(pos);
含义是：
找到下标严格大于 pos 的第一个 1。
注意是：
严格大于 pos
不是大于等于。
所以如果要找编号 >= L 的最小存在元素，应该找：
a._Find_next(L - 1)
但是如果 L = 0，那么 L - 1 = -1，这个写法不够稳。
更推荐写成：
int ans;
if(L == 0) ans = a._Find_first();
else ans = a._Find_next(L - 1);
这样更清楚，也更适合课堂讲解。
3. 重要提醒
_Find_first() 和 _Find_next() 是 GNU C++ 扩展，不是标准 C++。
也就是说：
如果 OJ 使用 GNU++17 / GNU++14，一般可以使用。
如果是严格标准 C++ 环境，可能编译失败。
本题是 bitset 模板题，通常评测环境支持 GNU C++，所以可以使用。
字符串哈希笔记（压缩版）
1. 作用
字符串哈希：
将字符串映射成一个数字，用数字快速判断两个字符串是否相同。
暴力比较：
一次比较 O(n)
m 次询问：
O(nm)
字符串哈希：
预处理：
O(n)
查询：
O(1)
2. 哈希思想
把字符串看成一个 B 进制数字。
例如：
***
假设：
a=1 b=2 c=3
B=10
哈希：
1×10²+2×10+3
公式：
h[i]=h[i-1]*B+s[i]
3. 前缀哈希
定义：
h[i]=前 i 个字符的哈希值
例如：
abcdef
h[3]=***
预处理：
h[i]=h[i-1]*B+s[i];
p[i]=B^i;
其中：
p[i]=B的i次方
4. 求区间哈希
求：
[l,r]
字符串哈希：
公式：
get(l,r)=h[r]-h[l-1]*B^(r-l+1)
理解：
完整前缀
-
左边多余部分
代码：
ull get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
5. 判断两个子串
比较：
[l1,r1]
[l2,r2]
步骤：
① 判断长度：
r1-l1 == r2-l2
② 判断哈希：
get(l1,r1)==get(l2,r2)
相同：
Yes
否则：
No
6. 模板代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1000010;
const int B=131;
int n,m;
string s;
ull h[N],p[N];
ull get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main(){
cin>>n>>m;
cin>>s;
s=" "+s;
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*B+s[i];
p[i]=p[i-1]*B;
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(r1-l1!=r2-l2)
cout<<"No\n";
else if(get(l1,r1)==get(l2,r2))
cout<<"Yes\n";
else
cout<<"No\n";
}
}
7. 哈希碰撞
不同字符串：
可能哈希相同
解决：
双哈希
两个：
hash1
hash2
同时判断。
unsigned long long
利用：
自然溢出
mod 2^64
竞赛常用。
8. 本题 A29720
数据：
n,m<=1000000
不能暴力。
思路：
预处理前缀哈希
↓
计算任意区间哈希
↓
比较两个区间哈希
复杂度：
预处理 O(n)
每次询问 O(1)
总复杂度 O(n+m)
9. 易错点
① 字符串下标
一般：
s=" "+s;
改成：
1~n
② 长度先判断
错误：
只判断hash
正确：
长度相同 && hash相同
③ 区间公式
必须记：
get(l,r)
=
h[r]-h[l-1]*B长度
一句话总结
字符串哈希 = 前缀哈希 + 快速求区间哈希，用数字代替字符串比较，把 O(n) 比较优化成 O(1)。
有帮助，赞一个