关键词：
题目背景
话说我大一中的运动会就要来了，据本班同学剧透（其实早就知道了），我萌萌的初二年将要表演腰鼓[喷]，这个无厘头的题目便由此而来。
Ivan乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外人间隔。”
题目描述
设想一下，腰鼓有两面，一面是红色的，一面是白色的。初二的苏大学神想给你这个oier出一道题。假设一共有N（1<=N<=20,000）个同学表演，表演刚开始每一个鼓都是红色面朝向观众，舞蹈老师会发出M（1<=M<=20,000）个指令，如果指令发给第i个表演的同学,这位同学就会把腰鼓反过来，如果腰鼓之前是红色面朝向观众的,那么就会变成白色面朝向观众，反之亦然。那么问题来了（！？），在老师每一次发出指令后，找到最长的连续的一排同学，满足每相邻的两个手中的腰鼓朝向观众的一面互不相同，输出这样一排连续的同学的人数。
输入输出格式
输入格式：
第一行有两个整数, 分别为表演的同学总数N, 和指令总数M。
之后M行, 每行有一个整数i: 1<=i<=N, 表示舞蹈老师发出的指令。
输出格式：
输出有M行, 其中每i行有一个整数.
表示老师的第i条指令发出之后, 可以找到的满足要求的最长连续的一排表演同学有多长?
输入输出样例
6 2 2 4
3 5
说明
Huangc温馨提示：其实数据根本没你想象的那么大。。。[坏笑]、、
分析：一类线段树的经典题型，这种题和求最长相同颜色区间的做法是差不多的，都是要用线段树解决，那么要记录哪些信息呢？满足要求的区间长度是肯定要记录的，还要记录每一个区间左端点和右端点的颜色，仅仅用这些信息还不能更新区间长度，还要记录每个区间从左向右最多能扩展多少，从右向左能扩展多少，这样就能求出答案来。
合并是一个难点，当前区间的答案可能是左区间的答案也可能是右区间的答案也可能是左右中间合并的答案，在合并的时候判断一下左右端点的颜色是否相同就好了.同时还要更新向右延伸的最大长度和向左延伸的最大长度.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; int n,m,lnum[200010],rnum[200010],lc[200010],rc[200010],ans[200010]; void pushup(int o,int len) { lnum[o] = lnum[o * 2]; rnum[o] = rnum[o * 2 + 1]; lc[o] = lc[o * 2]; rc[o] = rc[o * 2 + 1]; ans[o] = max(max(lnum[o * 2],max(rnum[o * 2 + 1],max(rnum[o * 2],lnum[o * 2 + 1]))),max(ans[o * 2],ans[o * 2 + 1])); if (rc[o * 2] != lc[o * 2 + 1]) { ans[o] = max(ans[o],rnum[o * 2] + lnum[o * 2 + 1]); if (lnum[o * 2] == (len - (len >> 1))) lnum[o] += lnum[o * 2 + 1]; if (rnum[o * 2 + 1] == (len >> 1)) rnum[o] += rnum[o * 2]; } } void build(int l,int r,int o) { if (l == r) { lnum[o] = rnum[o] = ans[o] = 1; lc[o] = rc[o] = 0; return; } int mid = (l + r) >> 1; build(l,mid,o * 2); build(mid + 1,r,o * 2 + 1); pushup(o,r - l + 1); } void update(int l,int r,int o,int v) { if (l == r) { lc[o] = rc[o] = (lc[o] + 1) % 2; return; } int mid = (l + r) >> 1; if (v <= mid) update(l,mid,o * 2,v); else update(mid + 1,r,o * 2 + 1,v); pushup(o,r - l + 1); } int main() { scanf("%d%d",&n,&m); build(1,n,1); for (int i = 1; i <= m; i++) { int t; scanf("%d",&t); update(1,n,1,t); printf("%d ",ans[1]); } return 0; }
洛谷p2253好一个一中腰鼓！
题目背景话说我大一中的运动会就要来了，据本班同学剧透（其实早就知道了），我萌萌的初二年将要表演腰鼓[喷]，这个无厘头的题目便由此而来。Ivan乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外... 查看详情
p2253好一个一中腰鼓！
...的题目便由此而来。Ivan乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外人间隔。”题目描述设想一下，腰鼓有两面，一面是红色的，一面是白色的。初二的苏大学神想给你这个oier出一道题... 查看详情
p2253好一个一中腰鼓！
P2253好一个一中腰鼓！本蒟蒻第一次用线段树做连续最长子段线段树是将一个大区间二分成两个小区间，通过递归解决两个小区间的问题，然后合并。得到大区间的解。类比一下分治法求单个最长连续子段。每次也都是将一个大... 查看详情
p2253好一个一中腰鼓！(代码片段)
题意：给你一个序列，初始是0，每次一个操作，把一个数^=1 每次求出最长01串的长度 正解：线段树（虽然暴力能过） 对于每个区间，记录三个值 lmax，以l为首的01串长度 rmax，以r为尾的01串长度 ... 查看详情
线段树p2253好一个一中腰鼓！(代码片段)
...就是说一开始所有的状态均为0会有m次指令每一次可以把一个点的状态进行更改原来是0就变成1原来是1就变成0 为了锻炼代码能力我决定还是中规中矩地写线段树这一道题还规定了一种串 就是0和1间隔交替（比如010101 1... 查看详情
线段树
...的了。现在又有人讲介个东西拿出来做做样子吧。P2253好一个一中腰鼓！然而这题数据水。所以评级也不高。#include<iostream>#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;structnode//线段树结构体intlf;//从 查看详情
洛谷——p2256一中校运会之百米跑
P2256一中校运会之百米跑题目背景在一大堆秀恩爱的**之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了100米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师... 查看详情
洛谷p2264情书
P2264情书88通过971提交题目提供者lin_toto标签字符串难度提高+/省选-提交该题 讨论 题解 记录最新讨论yyy快把题目改回来噫这题的题目好逗啊。。。情书std题目背景一封好的情书需要撰写人全身心的投入。崔君阳同学看... 查看详情
洛谷p2365任务安排[解法二斜率优化]
解法一：http://www.cnblogs.com/SilverNebula/p/5926253.html 解法二：斜率优化在解法一中有这样的方程：dp[i]=min(dp[i],dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]))其中min的后半部分，也就是dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sum 查看详情
单次接龙dfs洛谷
题目传送门：https://www.luogu.org/problem/show?pid=1019#sub典型的爆搜，每次更新最大龙长度即可搜索每个字符串编号，与已经连接好的字符串进行比较，以此往后找，若全部匹配，则可以接龙注意：1.自己也可以与自己相连2.题目中所说... 查看详情
[洛谷p1747]好奇怪的游戏
题目大意：有两匹马，马可以走"日"，也可以像象走"田"，求它走到(1,1)的步数。 题解：bfs卡点：边界判断成了可以走到(0,y)或(x,0) C++ Code：#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=51;intdx[12]={2,-2,2, 查看详情
洛谷p1747好奇怪的游戏
P1747好奇怪的游戏题目背景《爱与愁的故事第三弹·shopping》娱乐章。调调口味来道水题。题目描述爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。... 查看详情
Perl Regex 在捕获组一中返回命名组
...【发布时间】：2022-01-1216:35:36【问题描述】：我尝试获取一个正则表达式，它返回第一个捕获组中的匹配项。我放入正则表达式的应用程序只能使用第一个捕获组。每个正则表达式都在工作，但我不能将这两个组合在一起，使输... 查看详情
洛谷p1490解题报告
P1490买蛋糕题目描述野猫过生日，大家当然会送礼物了（咳咳，没送礼物的同志注意了哈！！），由于不知道送什么好，又考虑到实用性等其他问题，大家决定合伙给野猫买一个生日蛋糕。大家不知道最后要买的蛋糕的准确价格... 查看详情
洛谷p2018消息传递树形dp
洛谷P2018消息传递树形DPdp[u]表示u节点已经被传到，然后将其字节点都传到所需要的最少时间可知一个原则一个树中的子树中如果同时开始传，那么最晚才能传到的，那他肯定最先开始传因为本身需要的时间就大了，如果再晚一... 查看详情
洛谷1262间谍网络
tarjan缩点后找入度为零的强连通分量，加上它的sum即可但注意到还有NO的可能，所以大致有两种方法：1.tarjan之前先来一遍bfs2.tarjan内加一个数组维护最小编号貌似前者比较好写qwq1#include<cstdio>2#include<cstring>3usingnamespacestd;... 查看详情
洛谷p1783海滩防御分析+题解代码
洛谷P1783海滩防御分析+题解代码题目描述：WLP同学最近迷上了一款网络联机对战游戏（终于知道为毛JOHNKRAM每天刷洛谷效率那么低了），但是他却为了这个游戏很苦恼，因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是，W... 查看详情
洛谷p1469找筷子
题目描述经过一段时间的紧张筹备，电脑小组的“RP餐厅”终于开业了，这天，经理LXC接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题，筷子！CX小... 查看详情