洛谷P2572 [SCOI2010] 序列操作

2024-03-14 18:36
文章标签 操作 序列 洛谷 scoi2010 p2572

本文主要是介绍洛谷P2572 [SCOI2010] 序列操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

lxhgww 最近收到了一个 01 序列，序列里面包含了 n 个数，下标从 0 开始。这些数要么是 0，要么是 1，现在对于这个序列有五种变换操作和询问操作：

  • 0 l r 把 [l,r] 区间内的所有数全变成 0；
  • 1 l r 把 [l,r] 区间内的所有数全变成 1；
  • 2 l r 把 [l,r] 区间内的所有数全部取反，也就是说把所有的 0 变成 1，把所有的 1 变成 0；
  • 3 l r 询问 [l,r] 区间内总共有多少个 1；
  • 4 l r 询问 [l,r] 区间内最多有多少个连续的 1。

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式

第一行两个正整数 n,m，表示序列长度与操作个数。
第二行包括 n 个数，表示序列的初始状态。
接下来 m 行，每行三个整数，表示一次操作。

输出格式

对于每一个询问操作，输出一行一个数，表示其对应的答案。

输入输出样例

输入 #1

10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

输出 #1

5
2
6
5

说明/提示

【数据范围】
对于 30% 的数据，1≤n,m≤1000；
对于100% 的数据，1≤n,m≤105。

思路

一看就是线段树

将操作简化：

操作0，1：区间改值，同时优先级最大，用正常的lazy标记下传即可，下传时将区间取反标记清空。

操作2：区间取反，下传时若下区间有操作0，1的标记，将其取反，否则将已有的区间取反标记取反。

操作3：区间求和，对线段树每一个节点维护一个sum值

操作4：区间最长连续“1”，维护方法与维护最大字段和类似：分别记录

max1l,max1r,max1n,max0l,max0r,max0n;

表示必然包含左端点的最长连续“1”数目，必然包含右端点的最长连续“1”数目，最长连续“1”数目，必然包含左端点的最长连续“0”数目，必然包含右端点的最长连续“0”数目，最长连续“0”数目。

#include<bits/stdc++.h>
using namespace std;
struct Tree{int l,r,lazy,sum,max1l,max1n,max1r,len,lazyq;int max0l,max0n,max0r;
}tree[4000010]; 
int n,m;
int a[1000010];
inline void pushup(Tree &rt,Tree rl,Tree rr)
{rt.max1n=max(rl.max1n,max(rr.max1n,rl.max1r+rr.max1l));rt.max0n=max(rl.max0n,max(rr.max0n,rl.max0r+rr.max0l));if(rl.sum==rl.len) rt.max1l=rl.sum+rr.max1l;else rt.max1l=rl.max1l;if(rr.sum==rr.len) rt.max1r=rr.sum+rl.max1r;else rt.max1r=rr.max1r;if(!rl.sum) rt.max0l=rl.len+rr.max0l;else rt.max0l=rl.max0l;if(!rr.sum) rt.max0r=rr.len+rl.max0r;else rt.max0r=rr.max0r;rt.sum=rl.sum+rr.sum;return;
}
inline void build(int rt,int l,int r)
{if(l==r){tree[rt]=(Tree){l,r,-1,a[l],a[l],a[l],a[l],1,0,!a[l],!a[l],!a[l]};return;}tree[rt]=(Tree){l,r};int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);tree[rt].lazy=-1;tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline void downlazy(int rt)
{if(tree[rt].lazy==-1&&tree[rt].lazyq==0) return;int rl=rt<<1,rr=rt<<1|1;if(tree[rt].lazy!=-1){tree[rl].lazyq=tree[rr].lazyq=0;tree[rl].lazy=tree[rr].lazy=tree[rt].lazy;tree[rl].sum=tree[rl].max1n=tree[rl].max1l=tree[rl].max1r=tree[rl].len*tree[rt].lazy;tree[rr].sum=tree[rr].max1n=tree[rr].max1l=tree[rr].max1r=tree[rr].len*tree[rt].lazy;tree[rl].max0n=tree[rl].max0l=tree[rl].max0r=tree[rl].len*(!tree[rt].lazy);tree[rr].max0n=tree[rr].max0l=tree[rr].max0r=tree[rr].len*(!tree[rt].lazy);tree[rt].lazy=-1;}if(tree[rt].lazyq){if(tree[rl].lazy!=-1) tree[rl].lazy^=1;else tree[rl].lazyq^=1;if(tree[rr].lazy!=-1) tree[rr].lazy^=1;else tree[rr].lazyq^=1;tree[rl].sum=tree[rl].len-tree[rl].sum;tree[rr].sum=tree[rr].len-tree[rr].sum;swap(tree[rl].max0l,tree[rl].max1l);swap(tree[rl].max0n,tree[rl].max1n);swap(tree[rl].max0r,tree[rl].max1r);swap(tree[rr].max0l,tree[rr].max1l);swap(tree[rr].max0n,tree[rr].max1n);swap(tree[rr].max0r,tree[rr].max1r);tree[rt].lazyq=0;}
}
inline void change(int rt,int L,int R,int d)
{if(tree[rt].l>=L&&tree[rt].r<=R){tree[rt].lazy=d;tree[rt].lazyq=0;tree[rt].sum=tree[rt].max1n=tree[rt].max1l=tree[rt].max1r=tree[rt].len*tree[rt].lazy;tree[rt].max0n=tree[rt].max0l=tree[rt].max0r=tree[rt].len*(!tree[rt].lazy);return;}downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(L<=mid) change(rt<<1,L,R,d);if(R>mid) change(rt<<1|1,L,R,d);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline void update(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R){if(tree[rt].lazy!=-1) tree[rt].lazy^=1;else tree[rt].lazyq^=1;tree[rt].sum=tree[rt].len-tree[rt].sum;swap(tree[rt].max0l,tree[rt].max1l);swap(tree[rt].max0n,tree[rt].max1n);swap(tree[rt].max0r,tree[rt].max1r);return;}downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(L<=mid) update(rt<<1,L,R);if(R>mid) update(rt<<1|1,L,R);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline int qerry_1(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R) return tree[rt].sum;downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1,ans=0;if(L<=mid) ans+=qerry_1(rt<<1,L,R);if(R>mid) ans+=qerry_1(rt<<1|1,L,R);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);return ans;
}
inline Tree qerry_2(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R) return tree[rt];downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;Tree ans,l,r;ans=l=r=(Tree){0,0,-1,0,0,0,0,0,0,0,0};if(L<=mid) l=qerry_2(rt<<1,L,R);if(R>mid) r=qerry_2(rt<<1|1,L,R);pushup(ans,l,r);return ans;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=m;i++){int op,l,r;scanf("%d%d%d",&op,&l,&r);l++,r++;switch(op){case 0:case 1:{change(1,l,r,op);break;}case 2:{update(1,l,r);break;}case 3:{printf("%d\n",qerry_1(1,l,r));break;}case 4:{Tree ans=qerry_2(1,l,r);printf("%d\n",ans.max1n);break;}}	} return 0;
}

这篇关于洛谷P2572 [SCOI2010] 序列操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/809339。

相关文章

uva 10131 最长子序列

uva 10131 最长子序列

题意： 给大象的体重和智商，求体重按从大到小，智商从高到低的最长子序列，并输出路径。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect
阅读更多...
POJ1631最长单调递增子序列

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
动手学深度学习【数据操作+数据预处理】

动手学深度学习【数据操作+数据预处理】

import osos.makedirs(os.path.join('.', 'data'), exist_ok=True)data_file = os.path.join('.', 'data', 'house_tiny.csv')with open(data_file, 'w') as f:f.write('NumRooms,Alley,Price\n') # 列名f.write('NA
阅读更多...
线程的四种操作

线程的四种操作

所属专栏：Java学习        1. 线程的开启 start和run的区别： run：描述了线程要执行的任务，也可以称为线程的入口 start：调用系统函数，真正的在系统内核中创建线程（创建PCB，加入到链表中），此处的start会根据不同的系统，分别调用不同的api，创建好之后的线程，再单独去执行run（所以说，start的本质是调用系统api，系统的api
阅读更多...
Java IO 操作——个人理解

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理（ 原文章），记录一下。 首先，理解Java的IO操作到底操作的什么内容，过程又是怎么样子。          数据来源的操作： 来源有文件，网络数据。使用File类和Sockets等。这里操作的是数据本身，1,0结构。    File file = new File("path");   字
阅读更多...
MySQL——表操作

MySQL——表操作

目录 一、创建表 二、查看表 2.1 查看表中某成员的数据 2.2 查看整个表中的表成员 2.3 查看创建表时的句柄 三、修改表 alter 3.1 重命名 rename 3.2 新增一列 add 3.3 更改列属性 modify 3.4 更改列名称 change 3.5 删除某列 上一篇博客介绍了库的操作，接下来来看一下表的相关操作。 一、创建表 create
阅读更多...
封装MySQL操作时Where条件语句的组织

封装MySQL操作时Where条件语句的组织

在对数据库进行封装的过程中，条件语句应该是相对难以处理的，毕竟条件语句太过于多样性。 条件语句大致分为以下几种： 1、单一条件，比如：where id = 1; 2、多个条件，相互间关系统一。比如：where id > 10 and age > 20 and score < 60; 3、多个条件，相互间关系不统一。比如：where (id > 10 OR age > 20) AND sco
阅读更多...
PHP7扩展开发之流操作

PHP7扩展开发之流操作

前言 啥是流操作？简单来讲就是对一些文件，网络的IO操作。PHP已经把这些IO操作，封装成流操作。这节，我们将使用PHP扩展实现一个目录遍历的功能。PHP示例代码如下： <?phpfunction list_dir($dir) {if (is_dir($dir) === false) {return;} $dh = opendir($dir);if ($dh == false) {ret
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2