这题其实就是一个线段树维护最大连续和的水题。
别的操作不说，操作1只要二分找区间前
\(k\)个0即可。
需要注意的是，因为操作1两区间可能有交，因此要先清空再二分查询……
复杂度
\(O(n log ^ 2 n)\)。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 2e5 + 5;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, m;struct Tree{ int l, r, sum, lzy; int lmax, rmax, imax; In Tree operator + (const Tree& oth)const { Tree ret; ret.l = l, ret.r = oth.r; ret.sum = sum + oth.sum, ret.lzy = -1; ret.lmax = lmax; if(ret.lmax == r - l + 1) ret.lmax += oth.lmax; ret.rmax = oth.rmax; if(ret.rmax == oth.r - oth.l + 1) ret.rmax += rmax; ret.imax = max(max(imax, oth.imax), rmax + oth.lmax); return ret; }}t[maxn << 2];In void build(int L, int R, int now){ t[now].l = L, t[now].r = R; t[now].lzy = -1; if(L == R) {t[now].sum = 1;return;} int mid = (L + R) >> 1; build(L, mid, now << 1); build(mid + 1, R, now << 1 | 1); t[now] = t[now << 1] + t[now << 1 | 1];}In void change(int now, int d){ t[now].sum = (t[now].r - t[now].l + 1) * d; t[now].lzy = d; t[now].lmax = t[now].rmax = t[now].imax = (t[now].r - t[now].l + 1) * (d ^ 1);}In void pushdown(int now){ if(~t[now].lzy) { change(now << 1, t[now].lzy), change(now << 1 | 1, t[now].lzy); t[now].lzy = -1; }}In void update(int L, int R, int now, int d){ if(t[now].l == L && t[now].r == R) {change(now, d); return;} pushdown(now); int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) update(L, R, now << 1, d); else if(L > mid) update(L, R, now << 1 | 1, d); else update(L, mid, now << 1, d), update(mid + 1, R, now << 1 | 1, d); t[now] = t[now << 1] + t[now << 1 | 1];}In int query_sum(int L, int R, int now){ if(t[now].l == L && t[now].r == R) return t[now].sum; pushdown(now); int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) return query_sum(L, R, now << 1); else if(L > mid) return query_sum(L, R, now << 1 | 1); else return query_sum(L, mid, now << 1) + query_sum(mid + 1, R, now << 1 | 1);}In Tree query_con(int L, int R, int now){ if(t[now].l == L && t[now].r == R) return t[now]; pushdown(now); int mid = (t[now].l + t[now].r) >> 1; if(R <= mid) return query_con(L, R, now << 1); else if(L > mid) return query_con(L, R, now << 1 | 1); else return query_con(L, mid, now << 1) + query_con(mid + 1, R, now << 1 | 1);}int main(){ n = read(), m = read(); build(1, n, 1); for(int i = 1; i <= m; ++i) { int op = read(), l1 = read(), r1 = read(); if(op == 0) update(l1, r1, 1, 0); else if(op == 2) write(query_con(l1, r1, 1).imax), enter; else { int l2 = read(), r2 = read(); int sum = query_sum(l1, r1, 1); update(l1, r1, 1, 0); if(!sum) continue; int L = l2, R = r2; while(L < R) { int mid = (L + R) >> 1; if(mid - l2 + 1 - query_sum(l2, mid, 1) >= sum) R = mid; else L = mid + 1; } update(l2, L, 1, 1); } } return 0;}