首页 > 其他分享 >洛谷P3870[TJOI20009]-开关

洛谷P3870[TJOI20009]-开关

时间:2024-11-07 21:58:49浏览次数:5  
标签:le 洛谷 ll 元素 tree return sl TJOI20009 P3870

时间复杂度越高的算法能模拟的结构就越多...

题目大意:

给定一串长度为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

相关文章

  • 洛谷 P2113 看球泡妹子(DP)
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场,小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ,可以得到转移方程:但是,我们发现数组空间有一点小大,可以优化一下。发现每一次转移都是 ,于是可以滚动数组优化空......
  • 洛谷P3516 [POI2011] PRZ-Shift
    题意Link有一个排列\(a\),你可以执行两种操作:A:将最后一个数移到最前面B:将第三个数移到最前面构造一组操作序列将其变为递增排列,输出形如5a2b...表示执行\(5\)次A操作再执行\(2\)次B操作。思路很有意思的构造。仔细思考,操作A使我们能将原排列变为它的任何一......
  • 洛谷P5741
    P5741【深基7.例10】旗鼓相当的对手-加强版-洛谷|计算机科学教育新生态【深基7.例10】旗鼓相当的对手-加强版题目描述现有N(N<=1000)名同学参加了期末考试,并且获得了每名同学的信息:姓名(不超过8个字符的字符串,没有空格)、语文、数学、英语成绩(均为不超过150的自然......
  • 洛谷 P1638 逛画展
     此题运用滑动窗口和左右指针1.用identifiers储存画师的编号2.用count储存画师的画的数量3.将左右指针初始化为0,先右移右指针,当恰好找到第一个解时(即左右指针范围内画师数量恰好等于m),进入下一个while,如果此时窗口长度小于前一个解的窗口长度,相等则取左指针较靠前的。4.移......
  • 洛谷题单指南-二叉堆与树状数组-P1801 黑匣子
    原题链接:https://www.luogu.com.cn/problem/P1801题意解读:动态维护一组序列,并随时可以求第k小的值,每次求第k小的顺序是递增的,比如第一次取第1小,然后是第2小,以此类推。解题思路:对于求第k小的问题,已经介绍过几种方案:1、快选算法,每次查询时间复杂度logn,传送门:https://www.cnblogs......
  • 【洛谷 P3695 CYaRon!语】从一道大模拟入坑自制编程语言
    原题传送门本来是想投题解的,但是仔细阅读了一下主题库题解规范,发现这篇文章更加适合单独作为一篇blog阅读而非挂在题解区里污染环境,所以就这样了。0xff开始之前这道题我很早以前就开始看了,那时还只有星野梦美大佬的一篇题解。而到现在,我终于是有了时间和能力来切掉这道题,......
  • 洛谷题单指南-二叉堆与树状数组-P3378 【模板】堆
    原题链接:https://www.luogu.com.cn/problem/P3378题意解读:实现二叉堆。解题思路:二叉堆本质上一棵完全二叉树,根节点称为堆顶,根据特性不同分为有两种:大根堆:所有父节点的值大于子节点,根节点最大小根堆:所有父节点的值小于子节点,根节点最小主要作用:动态维护序列,并快速找到最大/最......
  • 洛谷题单指南-字符串-P6824 「EZEC-4」可乐
    原题链接:https://www.luogu.com.cn/problem/P6824题意解读:已知整数序列a[i],i在1~n,有整数k,求一个整数x,要求a[i]^x<=k,使得符合要求的a[i]数量最多,求这个数量。解题思路:1、确定x的范围由于a[i]^x<=k,因此,x的有效二进制位不可能超过a[i],而a的取值范围<=1000000,因此x差不多......
  • 洛谷:P5707 【深基2.例12】上学迟到 (纯净的顺序结构方法)
    本内容纯作者吃饱了没事干做出来的,仅供娱乐和思路参考(当然代码肯定是AC了)最近我想重新提升一下自己的编程能力,想选一个题量比较精炼的平台,所以就用了洛谷。题目描述学校和yyy的家之间的距离为s米,而yyy以v米每分钟的速度匀速走向学校。在上学的路上,yyy还要额外花费1......
  • 洛谷P5739
    P5739【深基7.例7】计算阶乘-洛谷|计算机科学教育新生态【深基7.例7】计算阶乘 题目描述求n!,也就是1*2*3...*n。挑战:尝试不使用循环语句(for、while)完成这个任务。 输入格式第一行输入一个正整数n。 输出格式输出一个正整数,表示n!。 样例#1样例输入3......