线段树的区间合并。
和上一题差不多....第三种操作只需要输出maxx[1]的值就可以。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> using namespace std; #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 const int maxn = 16005; int maxx[maxn<<2], pre_max[maxn<<2], suf_max[maxn<<2], cover[maxn<<2]; void pushUp(int rt, int m) { maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]); pre_max[rt] = pre_max[rt<<1]; suf_max[rt] = suf_max[rt<<1|1]; if(maxx[rt<<1] == (m-(m>>1))) pre_max[rt] = pre_max[rt<<1] + pre_max[rt<<1|1]; if(maxx[rt<<1|1] == (m>>1)) suf_max[rt] = suf_max[rt<<1|1]+suf_max[rt<<1]; maxx[rt] = max(maxx[rt], suf_max[rt<<1]+pre_max[rt<<1|1]); } void build(int l, int r, int rt) { maxx[rt] = pre_max[rt] = suf_max[rt] = r-l+1; cover[rt] = -1; if(l == r) return ; int m = l+r>>1; build(lson); build(rson); } void pushDown(int rt, int m) { if(~cover[rt]) { cover[rt<<1] = cover[rt<<1|1] = cover[rt]; maxx[rt<<1] = pre_max[rt<<1] = suf_max[rt<<1] = cover[rt]*(m-(m>>1)); pre_max[rt<<1|1] = suf_max[rt<<1|1] = maxx[rt<<1|1] = cover[rt]*(m>>1); cover[rt] = -1; } } void update(int L, int R, int l, int r, int rt, int val) { if(L<=l&&R>=r) { cover[rt] = val; maxx[rt] = suf_max[rt] = pre_max[rt] = val*(r-l+1); return ; } pushDown(rt, r-l+1); int m = l+r>>1; if(L<=m) update(L, R, lson, val); if(R>m) update(L, R, rson, val); pushUp(rt, r-l+1); } int main() { int n, m, sign, x, y; while(cin>>n>>m) { build(1, n, 1); while(m--) { scanf("%d", &sign); if(sign == 1) { scanf("%d%d", &x, &y); update(x, y+x-1, 1, n, 1, 0); } else if(sign == 2){ scanf("%d%d", &x, &y); update(x, y+x-1, 1, n, 1, 1); } else { printf("%d ", maxx[1]); } } } }