线段树。
题意是给出一个长为N的区间，不断进行三中操作：1.插入一个区间，所有被插入的地方都表示占有；2.删除一个区间，所有删除的地方都表示释放；3.询问整个范围内最长的连续的空区间的长度。很明显的线段树，可惜我想错了，以为入区间的最大值可以独立的从两个子区间中寻找，忘记了两个子区间合并后可能得到一个更长的区间，尝试好多数据都对，提交就是WA，看网上的做法跟我的差别很大，也没心情看。搁置了好几天，今天终于发现原来自己从开始就把算法想错了，而不是代码的问题，白查了那么久，理解还是不够深啊。
#include<iostream>
#include<string>#include<cstring>#include<cstdio>#include<queue>#include<stack>#include<algorithm>#include<cmath>#include<set>#include<map>#include<vector>#include<fstream>#include<sstream>#include<iomanip>using namespace std;const int N = 16001;const int M = 101;const int MAX = 1000000000;struct node{ int l,r;//denotes the bound of the segment int la,ra,ma;//denotes the the bound of max free segment in this segment int f;//denotes if the segment is 2 full used or 0 free or 1 partial used}t[4*N];void build(int i, int l, int r){ t[i].l = l; t[i].r = r; t[i].f = 0; if(l == r)return; int mid = (l+r)>>1; build(i<<1, l, mid); build((i<<1)+1, mid+1, r);}void insert(int i, int l, int r){ if(t[i].l == l && t[i].r == r) { t[i].f = 2; t[i].ma = t[i].la = t[i].ra = 0; return; } int x; if(t[i].f == 0) { x = (i<<1); t[i].f = 1; t[x].f = 0; t[x+1].f = 0; t[x].la = t[x].ma = t[x].ra = t[x].r-t[x].l+1; x++; t[x].la = t[x].ma = t[x].ra = t[x].r-t[x].l+1; } int mid = (t[i].l + t[i].r)>>1; if(r <= mid) { insert(i<<1, l, r); } else if(l > mid) { insert((i<<1)+1, l, r); } else { insert(i<<1, l, mid); insert((i<<1)+1, mid+1, r); } //the key oprations x = i<<1; if(t[x].f == 0) { t[i].la = t[x].ma + t[x+1].la; } else { t[i].la = t[x].la; } x++; if(t[x].f == 0) { t[i].ra = t[x-1].ra + t[x].ma; } else { t[i].ra = t[x].ra; } int a,b,c; a = max(t[i<<1].ma,t[(i<<1)+1].ma); b = t[i<<1].ra + t[(i<<1)+1].la; c = max(t[i].la, t[i].ra); t[i].ma = max(max(a,b),c); if(t[i<<1].f == t[(i<<1)+1].f) { t[i].f = t[i<<1].f; }}void remove(int i, int l, int r){ if(t[i].l == l && t[i].r == r) { t[i].f = 0; t[i].ma = t[i].la = t[i].ra = r-l+1; return; } int x; if(t[i].f == 2) { x = (i<<1); t[i].f = 1; t[x].f = 2; t[x+1].f = 2; t[x].la = t[x].ma = t[x].ra = 0; x++; t[x].la = t[x].ma = t[x].ra = 0; } int mid = (t[i].l + t[i].r)>>1; if(r <= mid) { remove(i<<1, l, r); } else if(l > mid) { remove((i<<1)+1, l, r); } else { remove(i<<1, l, mid); remove((i<<1)+1, mid+1, r); } //the key oprations x = i<<1; if(t[x].f == 0) { t[i].la = t[x].ma + t[x+1].la; } else { t[i].la = t[x].la; } x++; if(t[x].f == 0) { t[i].ra = t[x-1].ra + t[x].ma; } else { t[i].ra = t[x].ra; } int a,b,c; a = max(t[i<<1].ma,t[(i<<1)+1].ma); b = t[i<<1].ra + t[(i<<1)+1].la; c = max(t[i].la, t[i].ra); t[i].ma = max(max(a,b),c); if(t[i<<1].f == t[(i<<1)+1].f) { t[i].f = t[i<<1].f; }}int main(){ int n,p,c,a,b; while(scanf("%d%d",&n,&p) != EOF) { build(1,1,n); t[1].f = 0; t[1].ma = t[1].la = t[1].ra = n; while(p--) { scanf("%d",&c); if(c == 1) { scanf("%d%d",&a,&b); if(b == 0)continue; insert(1,a,a+b-1); } else if(c == 2) { scanf("%d%d",&a,&b); remove(1,a,a+b-1); } else { printf("%d\n",t[1].ma); } } } return 0;}