洛谷P2253 好一个一中腰鼓！
题目背景
话说我大一中的运动会就要来了，据本班同学剧透（其实早就知道了），我萌萌的初二年将要表演腰鼓[喷]，这个无厘头的题目便由此而来。
\(Ivan\)乱入：“忽一人大呼：‘好一个安塞腰鼓！’满座寂然，无敢哗者，遂与外人间隔。”
题目描述
设想一下，腰鼓有两面，一面是红色的，一面是白色的。初二的苏大学神想给你这个\(OIer\)出一道题。假设一共有\(N（1 \leq N \leq 20,000\)）个同学表演，表演刚开始每一个鼓都是红色面朝向观众，舞蹈老师会发出\(M（1 \leq M \leq 20,000\)）个指令，如果指令发给第i个表演的同学,这位同学就会把腰鼓反过来，如果腰鼓之前是红色面朝向观众的,那么就会变成白色面朝向观众，反之亦然。那么问题来了（！？），在老师每一次发出指令后，找到最长的连续的一排同学，满足每相邻的两个手中的腰鼓朝向观众的一面互不相同，输出这样一排连续的同学的人数。
输入输出格式
输入格式：
第一行有两个整数, 分别为表演的同学总数\(N\), 和指令总数\(M\)。
之后\(M\)行, 每行有一个整数\(i: 1 \leq i \leq N\), 表示舞蹈老师发出的指令。
输出格式：
输出有\(M\)行, 其中每\(i\)行有一个整数.
表示老师的第\(i\)条指令发出之后, 可以找到的满足要求的最长连续的一排表演同学有多长?
输入输出样例
输入样例#1：
6 2
2
4输出样例#1：
3
5说明
\(Huangc\)温馨提示：其实数据根本没你想象的那么大。。。
思路：首先对于修改操作显然我们可以用线段树的单点修改来维护，然后对于查询操作，可以用一种类似于求区间最大字段和的思想，但是需要记录一个lc和rc，分别表示一个区间左端点和右端点的状态是什么，pushup的时候判断一下即可。
代码：
#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 20007
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
int n,m,lmax[maxn<<2],maxx[maxn<<2],rmax[maxn<<2],lc[maxn<<2],rc[maxn<<2];
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
void build(int rt, int l, int r) {
lmax[rt]=rmax[rt]=maxx[rt]=1;
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
inline void pushup(int rt, int len) {
if(lmax[ls]==(len-(len>>1))&&lc[rs]!=rc[ls])
lmax[rt]=(len-(len>>1))+lmax[rs];
else lmax[rt]=lmax[ls];
if(rmax[rs]==(len>>1)&&lc[rs]!=rc[ls])
rmax[rt]=(len>>1)+rmax[ls];
else rmax[rt]=rmax[rs];
maxx[rt]=max(maxx[ls],maxx[rs]);
if(rc[ls]!=lc[rs]) maxx[rt]=max(maxx[rt],lmax[rs]+rmax[ls]);
lc[rt]=lc[ls],rc[rt]=rc[rs];
}
void add(int rt, int l, int r, int L) {
if(l==r) {
lc[rt]^=1;
rc[rt]^=1;
return;
}
int mid=(l+r)>>1;
if(L<=mid) add(ls,l,mid,L);
else add(rs,mid+1,r,L);
pushup(rt,r-l+1);
}
int main() {
n=qread(),m=qread();
build(1,1,n);
for(int i=1,x;i<=m;++i) {
x=qread();
add(1,1,n,x);
printf("%d\n",maxx[1]);
}
return 0;
}
