https://www.luogu.org/problem/show?pid=2253
题目背景
话说我大一中的运动会就要来了，据本班同学剧透（其实早就知道了），我萌萌的初二年将要表演腰鼓[喷]，这个无厘头的题目便由此而来。
Ivan乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外人间隔。”
题目描述
设想一下，腰鼓有两面，一面是红色的，一面是白色的。初二的苏大学神想给你这个oier出一道题。假设一共有N（1<=N<=20,000）个同学表演，表演刚开始每一个鼓都是红色面朝向观众，舞蹈老师会发出M（1<=M<=20,000）个指令，如果指令发给第i个表演的同学,这位同学就会把腰鼓反过来，如果腰鼓之前是红色面朝向观众的,那么就会变成白色面朝向观众，反之亦然。那么问题来了（！？），在老师每一次发出指令后，找到最长的连续的一排同学，满足每相邻的两个手中的腰鼓朝向观众的一面互不相同，输出这样一排连续的同学的人数。
输入输出格式
输入格式：
第一行有两个整数, 分别为表演的同学总数N, 和指令总数M。
之后M行, 每行有一个整数i: 1<=i<=N, 表示舞蹈老师发出的指令。
输出格式：
输出有M行, 其中每i行有一个整数.
表示老师的第i条指令发出之后, 可以找到的满足要求的最长连续的一排表演同学有多长?
输入输出样例
输入样例#1：
6 2 2 4
输出样例#1：
3 5
说明
Huangc温馨提示：其实数据根本没你想象的那么大。。。[坏笑]、、
思路：这个题就是找每次修改后最长的01串
然后线段树维护4个值：1.区间左端点是0还是1 。 2.区间右端点是0还是1。 3.区间左端点开始最长的01串。 4.区间右端点开始最长的01串。
（2333）5.区间中最长的01串。 6.区间长度
就可以做了
#include<bits/stdc++.h> using namespace std; #define maxn 1000000 int n,m,x,y; struct Type_Tree{ int l,r,mid,len,ren,s; }tree[maxn<<2]; void tree_up(int k) { tree[k].l=tree[k<<1].l; tree[k].r=tree[k<<1|1].r; tree[k].len=tree[k<<1].len; tree[k].ren=tree[k<<1|1].ren; tree[k].mid=max(tree[k<<1].mid,tree[k<<1|1].mid); tree[k].mid=max(tree[k].mid,tree[k<<1|1].len); tree[k].mid=max(tree[k].mid,tree[k<<1].ren); if(tree[k<<1].r!=tree[k<<1|1].l) { tree[k].mid=max(tree[k].mid,tree[k<<1].ren+tree[k<<1|1].len); if(tree[k<<1].len==tree[k<<1].s) tree[k].len+=tree[k<<1|1].len; if(tree[k<<1|1].ren==tree[k<<1|1].s) tree[k].ren+=tree[k<<1].ren; } } void tree_build(int l,int r,int k) { tree[k].s=r-l+1; if(r==l) { tree[k].l=tree[k].r=0; tree[k].len=tree[k].ren=tree[k].mid=1; return ; } int mid=(l+r)>>1; tree_build(l,mid,k<<1); tree_build(mid+1,r,k<<1|1); tree_up(k); } void tree_change(int l,int r,int k,int to) { if(l==r) { tree[k].l=tree[k].r=tree[k].r^1; return ; } int mid=(l+r)>>1; if(to<=mid) tree_change(l,mid,k<<1,to); else tree_change(mid+1,r,k<<1|1,to); tree_up(k); } int main() { scanf("%d%d",&n,&m); tree_build(1,n,1); for(int i=1;i<=m;i++) { scanf("%d",&x); tree_change(1,n,1,x); printf("%d ",tree[1].mid); } return 0; }