时间复杂度越高的算法能模拟的结构就越多...
题目大意:
给定一串长度为n,元素只能为0或1的序列,默认该序列元素全为0.
接下来需要进行m次操作,操作分为两种:
1.把区间 \([a,b]\) 中的所有元素值取反.
2.求区间 \([a,b]\) 中元素值为1的元素数量.
每一次调用操作1时,每次一行输出一个整数,表示元素值为1的元素数量.
第一行两个整数,分别为 \(n\) 和 \(m\) .
接下来有 \(m\) 行,每行三个整数分别为 \(c,a,b\) 。其中 \(c\) 决定操作的种类.
-
当 \(c\) 等于1时,表示第一种操作.
-
当 \(c\) 等于2时,表示第二种操作.
对于所有的测试点,满足 \(2 \le n \le 10^5,1 \le m \le 10^5,1 \le a,b \le n,c \in \{0,1\}.\)
正解:
虽然洛谷上显示这道题需要用分块,但是我们仍然可以只用线段树来写.
想想,分块做到的是将序列分成几块区间,而线段树不也是分区间吗?
两者都做到了通过小区间来合并出最终的答案,但是还是显得线段树更高级一些.(其实是我不会写分块QAQ)
本题中,我们的tree数组可以存储当前区间元素值为1的元素数量,以方便后续查询时合并信息。
如果要对当前区间所有元素取反,那么我们也很容易推出取反后元素值为1的数量为区间长度 - 原本元素值为1的元素数量.
因为一段区间取反两次和原来结果不变,所以我们的lazytag用布尔值来存储当前的状态.
注意:在pushdown时要注意当前lazytag状态是不是0,如果为0会导致越界(
别问我怎么知道)
总的来说,这到题对于线段树来说可以是练练手,但对于日常的刷题,还是差了点的.
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,c,a,b;
bool lazy[400005];
struct node{
ll l,r,len;
}tree[400005];
inline ll lu(ll u){return u << 1;}
inline ll ru(ll u){return u << 1 | 1;}
void push_up(ll u){
tree[u].len = tree[lu(u)].len + tree[ru(u)].len;
return;
}
void build(ll u,ll l,ll r){
tree[u].l = l,tree[u].r = r;
if(l == r){
return;
}else{
ll mid = (l + r) >> 1;
build(lu(u),l,mid);
build(ru(u),mid + 1,r);
}
return;
}
void mtag(ll u){
lazy[u] = !lazy[u];
tree[u].len = (tree[u].r - tree[u].l - tree[u].len + 1);
return;
}
void pdown(ll u){
if(!lazy[u]) return;
mtag(lu(u));
mtag(ru(u));
lazy[u] = 0;
return;
}
void update(ll u,ll sl,ll sr){
if(tree[u].l >= sl && tree[u].r <= sr){
lazy[u] = !lazy[u];
tree[u].len = (tree[u].r - tree[u].l - tree[u].len + 1);
}else{
pdown(u);
ll mid = (tree[u].l + tree[u].r) >> 1;
if(sl <= mid) update(lu(u),sl,sr);
if(sr > mid) update(ru(u),sl,sr);
push_up(u);
}
return;
}
ll search(ll u,ll sl,ll sr){
if(tree[u].l >= sl && tree[u].r <= sr) return tree[u].len;
ll mid = (tree[u].l + tree[u].r) >> 1;pdown(u);
ll res = 0;
if(sl <= mid) res += search(lu(u),sl,sr);
if(sr > mid) res += search(ru(u),sl,sr);
push_up(u);
return res;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
cin >> n >> m;
build(1,1,n);
while(m--){
cin >> c >> a >> b;
if(!c){
update(1,a,b);
}else{
cout<<search(1,a,b)<<'\n';
}
}
return 0;
}
谢谢观看!
标签:le,洛谷,ll,元素,tree,return,sl,TJOI20009,P3870 From: https://www.cnblogs.com/Little-Knight-qwq/p/18534090