题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4592
题意概述：
需要维护一个01序列A，一开始A全部都是1。支持如下操作：
1.将区间[l,r]变成0。
2.将区间[l0,r0]变成0，用其中原来1的个数去填补[l1,r1]中的0，当1的数量过多的时候剩余的1会被丢弃；当1的数量不足的时候从左到右依次填充0。
3.询问区间[l,r]中最长的0串长度。
N,M<=200000.
我就直接把考试的时候写的东西弄上来了：
首先建立一颗序列线段树，维护01序列，支持求和操作，同时维护最长序列。
对于1操作，直接区间赋值为0。
对于2操作，首先对[l0,r0]对1求和，记为x，然后赋值为0。然后在区间[l1,r1]中找到第一个0数量大于等于x的位置（实在没有就是r1），然后区间赋值。这一步可以用前缀和的思想，先求[1,l1-1]（注意先对[l0,r0]操作）中的0数量y，然后就可以在线段树里直接查找第x+y个0的位置，最后的结果和r1比较，取较小值。
对于3操作，首先在线段树中维护区间左起最长、右起最长、区间最长的0串长度，查询的时候：要查询的区间完全在左半边或者右半边，直接递归处理；当查询区间跨越当前区间的中点，左右区间右起最长，左起最长各自与查询长度取min相加作为一个答案，递归到左右区间，三个答案取最大值；询问区间包含当前区间，直接返回区间最长0串长度（实际上处理的思路就是分治，跨越中间的，左边的，右边的）。
于是一通维护下来相当于要维护的东西有：1数量之和，0数量之和，0区间最长串三件套。
时间复杂度O(MlogN)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std; int N,M;
struct segment_tree{
static const int maxn=;
int rt,np,lc[maxn],rc[maxn],s0[maxn],s1[maxn],ml[maxn],mr[maxn],mm[maxn],flag[maxn];
segment_tree(){ rt=np=; }
void pushup(int now,int L,int R){
int m=L+R>>;
s0[now]=s0[lc[now]]+s0[rc[now]];
s1[now]=s1[lc[now]]+s1[rc[now]];
ml[now]=max(ml[lc[now]],ml[lc[now]]==m-L+?ml[lc[now]]+ml[rc[now]]:);
mr[now]=max(mr[rc[now]],mr[rc[now]]==R-m?mr[rc[now]]+mr[lc[now]]:);
mm[now]=max(mr[lc[now]]+ml[rc[now]],max(mm[lc[now]],mm[rc[now]]));
}
void pushdown(int now,int L,int R){
if(flag[now]==-) return;
int m=L+R>>;
if(flag[now]==){
ml[lc[now]]=mr[lc[now]]=mm[lc[now]]=m-L+;
s0[lc[now]]=m-L+,s1[lc[now]]=,flag[lc[now]]=;
ml[rc[now]]=mr[rc[now]]=mm[rc[now]]=R-m;
s0[rc[now]]=R-m,s1[rc[now]]=,flag[rc[now]]=;
}
else{
ml[lc[now]]=mr[lc[now]]=mm[lc[now]]=;
s0[lc[now]]=,s1[lc[now]]=m-L+,flag[lc[now]]=;
ml[rc[now]]=mr[rc[now]]=mm[rc[now]]=;
s0[rc[now]]=,s1[rc[now]]=R-m,flag[rc[now]]=;
}
flag[now]=-;
}
void build(int &now,int L,int R){
now=++np;
lc[now]=rc[now]=,s0[now]=ml[now]=mr[now]=mm[now]=,s1[now]=R-L+,flag[now]=-;
if(L==R) return;
int m=L+R>>;
build(lc[now],L,m); build(rc[now],m+,R);
}
void update(int now,int L,int R,int A,int B,int v){
if(A<=L&&R<=B){
if(v==){
ml[now]=mr[now]=mm[now]=R-L+;
s0[now]=R-L+,s1[now]=,flag[now]=;
}
else{
ml[now]=mr[now]=mm[now]=;
s0[now]=,s1[now]=R-L+,flag[now]=;
}
return;
}
pushdown(now,L,R);
int m=L+R>>;
if(B<=m) update(lc[now],L,m,A,B,v);
else if(A>m) update(rc[now],m+,R,A,B,v);
else update(lc[now],L,m,A,B,v),update(rc[now],m+,R,A,B,v);
pushup(now,L,R);
}
int query_s(int now,int L,int R,int A,int B,int v){
if(A<=L&&R<=B) return v?s1[now]:s0[now];
pushdown(now,L,R);
int m=L+R>>;
if(B<=m) return query_s(lc[now],L,m,A,B,v);
if(A>m) return query_s(rc[now],m+,R,A,B,v);
return query_s(lc[now],L,m,A,B,v)+query_s(rc[now],m+,R,A,B,v);
}
int query_p(int now,int L,int R,int k){
if(L==R) return L;
pushdown(now,L,R);
int m=L+R>>;
if(k<=s0[lc[now]]) return query_p(lc[now],L,m,k);
return query_p(rc[now],m+,R,k-s0[lc[now]]);
}
int query_mm(int now,int L,int R,int A,int B){
if(A<=L&&R<=B) return mm[now];
pushdown(now,L,R);
int m=L+R>>;
if(B<=m) return query_mm(lc[now],L,m,A,B);
if(A>m) return query_mm(rc[now],m+,R,A,B);
int re=min(m-A+,mr[lc[now]])+min(B-m,ml[rc[now]]);
return max(re,max(query_mm(lc[now],L,m,A,m),query_mm(rc[now],m+,R,m+,B)));
}
}st; void work()
{
scanf("%d%d",&N,&M);
st.build(st.rt,,N);
int op,l0,r0,l1,r1,x,y,p;
for(int i=;i<=M;i++){
scanf("%d",&op);
if(op==){
scanf("%d%d",&l0,%r0);
st.update(st.rt,,N,l0,r0,);
}
else if(op==){
scanf("%d%d%d%d",&l0,&r0,&l1,&r1);
x=st.query_s(st.rt,,N,l0,r0,);
if(!x) continue;
st.update(st.rt,,N,l0,r0,);
y=l1==?:st.query_s(st.rt,,N,,l1-,);
p=min(r1,st.query_p(st.rt,,N,y+x));
st.update(st.rt,,N,l1,p,);
}
else if(op==){
scanf("%d%d",&l0,&r0);
printf("%d\n",st.query_mm(st.rt,,N,l0,r0));
}
}
}
int main()
{
work();
return ;
}