洛谷P2572 [SCOI2010]序列操作(ODT)

题解

题意

题目链接

sol

odt板子题.....

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long 
#define fin(x) freopen(#x".in", "r", stdin);
#define fout(x) freopen(#x".out", "w", stdout); 
#define fi first
#define se second 
#define int long long 
using namespace std;
const int maxn = 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
#define sit set<node>::iterator 
struct node {
    int l, r;
    mutable int v;
    bool operator < (const node &rhs) const {
        return l < rhs.l;   
    }
};
set<node> s;
sit split(int p) {
    sit pos = s.lower_bound({p});
    if(pos != s.end() && pos->l == p) return pos;
    pos--; int l = pos->l, r = pos->r, v = pos->v;
    s.erase(pos);
    s.insert({l, p - 1, v});
    return s.insert({p, r, v}).fi;
}
void mem(int l, int r, int v) {
    sit ed = split(r + 1), bg = split(l);
    s.erase(bg, ed);
    s.insert({l, r, v});
}
void rev(int l, int r) {
    sit ed = split(r + 1), bg = split(l);
    for(sit i = bg; i != ed; i++) i->v ^= 1;
}
int querynum(int l, int r) {
    int ans = 0; sit ed = split(r + 1), bg = split(l);
    for(sit i = bg; i != ed; i++)
        if(i->v == 1) ans += i->r - i->l + 1;
    return ans;
}
int querysuc(int l, int r) {
    int ans = 0, pre = 0; sit ed = split(r + 1), bg = split(l);
    for(sit i = bg; i != ed; i++)
        if(i->v == 1) ans = max(ans, i->r - i->l + 1 + pre), pre += i->r - i->l + 1;
        else pre = 0;
    return ans;
}
signed main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) s.insert({i, i, read()});
    s.insert({n + 1, n + 1, 0});
    for(int i = 1; i <= m; i++) {
        int op = read(), a = read() + 1, b = read() + 1;
        if(op == 0 || op == 1) mem(a, b, op);
        else if(op == 2) rev(a, b);
        else if(op == 3) printf("%d\n", querynum(a, b));
        else printf("%d\n", querysuc(a, b));
    }
    return 0;
}