朝田诗乃 的博客

朝田诗乃 的博客

题解 P5500 【[LnOI2019]真正的OIer从不女装】

posted on 2019-08-10 10:29:50 | under 题解 |

我们发现, $\forall k>0, Ans_{k} = Ans_{1}$ ,其中 $Ans_{j}$ 表示正好反转 $j$ 次的最大答案。所以对于本题, $k=0$ 和 $k\neq 0$ 分开讨论即可。

为什么 $\forall k>0, Ans_{k} = Ans_{1}$ 呢?

假设序列为 $\underrightarrow{1}\underrightarrow{2}\underrightarrow{3}$ ;

从某个位置翻转后变成: $\underleftarrow{2}\underleftarrow{1}\underleftarrow{3}$ ;

将序列整个翻转对答案没有影响,即: $\underrightarrow{3}\underrightarrow{1}\underrightarrow{2}$ ;

即一次翻转与把序列开头的某一段接到序列后面等效。因此, $\forall k>0, Ans_{k} = Ans_{1}$

我们发现翻转两次等于翻转一次,那么这样推出翻转多次等于翻转一次。

使用线段树来维护区间最长颜色段。对于所有 $k \neq 0$ 且询问区间左右端点颜色相同的询问,将区间最长颜色段与询问区间左右最长颜色段长度的和取max即可。

代码(很丑):

#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;

const int MAXN = 200050;
void read(int &x) {
    char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
    while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}

struct Segment_Tree {
    int lcol, rcol, col, lmax, rmax, v;
} t[MAXN << 2];
int n, m, a[MAXN];

void pushup(int u, int l, int r) {
    int mid = (l + r) >> 1;
    if(t[L(u)].col != t[R(u)].col || t[L(u)].col == -1 || t[R(u)].col == -1) t[u].col = -1;
    else t[u].col = t[L(u)].col;
    t[u].lcol = t[L(u)].lcol; t[u].rcol = t[R(u)].rcol;
    if(t[L(u)].col != -1 && t[L(u)].col == t[R(u)].lcol) t[u].lmax = (mid-l+1)+t[R(u)].lmax;
    else t[u].lmax = t[L(u)].lmax;
    if(t[R(u)].col != -1 && t[R(u)].col == t[L(u)].rcol) t[u].rmax = (r-mid)+t[L(u)].rmax;
    else t[u].rmax = t[R(u)].rmax;
    t[u].v = max(t[L(u)].v, t[R(u)].v);
    if(t[L(u)].rcol == t[R(u)].lcol) t[u].v = max(t[u].v, t[L(u)].rmax + t[R(u)].lmax);
}

void cover(int u, int l, int r, int c) {
    //cout << l << " " << r << " " << c << endl;
    t[u].col = t[u].lcol = t[u].rcol = c;
    t[u].v = t[u].lmax = t[u].rmax = r-l+1;
}

void pushdown(int u, int l, int r) {
    if(t[u].col != -1) {
        int mid = (l + r) >> 1;
        cover(L(u), l, mid, t[u].col);
        cover(R(u), mid+1, r, t[u].col);
    }
}

void build(int u, int l, int r) {
    if(l == r) {
        t[u].lcol = t[u].rcol = t[u].col = a[l];
        t[u].lmax = t[u].rmax = 1; t[u].v = 1;
        //cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl; 
        return;
    }
    int mid = (l + r) >> 1;
    build(L(u), l, mid); build(R(u), mid+1, r);
    pushup(u, l, r);
    //cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl; 
}

void print(int u, int l, int r) {
    if(l == r) {
        cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl; 
        return;
    }
    int mid = (l + r) >> 1;
    print(L(u), l, mid); print(R(u), mid+1, r);
    cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl; 
}

void update(int u, int l, int r, int tl, int tr, int c) {
    if(tr < l || tl > r) return;
    if(tl <= l && r <= tr) {
        cover(u, l, r, c);
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    update(L(u), l, mid, tl, tr, c); update(R(u), mid+1, r, tl, tr, c);
    pushup(u, l, r);
}

int query(int u, int l, int r, int tl, int tr) {
    if(tl <= l && r <= tr) return t[u].v;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if(tr <= mid) return query(L(u), l, mid, tl, tr);
    else if(tl > mid) return query(R(u), mid+1, r, tl, tr);
    else {
        int res = max(query(L(u), l, mid, tl, tr), query(R(u), mid+1, r, tl, tr));
        if(t[L(u)].rcol == t[R(u)].lcol) {
            int rm = min(mid-tl+1, t[L(u)].rmax), lm = min(tr-mid, t[R(u)].lmax);
            res = max(res, rm + lm);
        }
        return res;
    }
}

int Qcol(int u, int l, int r, int x) {
    if(l == r) return t[u].col;
    if(l <= x && x <= r && t[u].col != -1) return t[u].col;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if(x <= mid) return Qcol(L(u), l, mid, x);
    else return Qcol(R(u), mid+1, r, x);
}

int Qlmax(int u, int l, int r, int tl, int tr) {
    //cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl; 
    if(l <= tl && tr <= r && l + t[u].lmax - 1 >= tl) return l+t[u].lmax-tl;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if(tl > mid) return Qlmax(R(u), mid+1, r, tl, tr);
    else if(tr <= mid) return Qlmax(L(u), l, mid, tl, tr);
    else if(t[L(u)].rcol == t[R(u)].lcol && mid-t[L(u)].rmax+1 <= tl) return Qlmax(L(u), l, mid, tl, mid) + Qlmax(R(u), mid+1, r, mid+1, tr);
    else return Qlmax(L(u), l, mid, tl, mid);
    /*{
        if(t[L(u)].col != -1) {
            if(t[L(u)].col != t[R(u)].lcol) return mid-tl+1;
            else return mid-tl+1+Qlmax(R(u), mid+1, r, mid+1, tr);
        } else return Qlmax(L(u), l, mid, tl, mid);
    }*/
}

int Qrmax(int u, int l, int r, int tl, int tr) {
    //cout << u << " " << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << " " << t[u].col << endl; 
    if(l <= tl && tr <= r && r - t[u].rmax + 1 <= tr) return tr - r + t[u].rmax;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    //cout << R(u) << " " << L(u) << " " << t[R(u)].col << " " << t[L(u)].rcol << endl;
    if(tl > mid) return Qrmax(R(u), mid+1, r, tl, tr);
    else if(tr <= mid) return Qrmax(L(u), l, mid, tl, tr);
    else if(t[R(u)].lcol == t[L(u)].rcol && mid+1+t[R(u)].lmax-1 >= tr) return Qrmax(L(u), l, mid, tl, mid) + Qrmax(R(u), mid+1, r, mid+1, tr);
    else return Qrmax(R(u), mid+1, r, mid+1, tr);
    /*{
        if(t[R(u)].col != -1) {
            if(t[R(u)].col != t[L(u)].rcol) return tr-mid;
            else return tr-mid+Qrmax(L(u), l, mid+1, tl, mid);
        } else return Qrmax(R(u), mid+1, r, mid+1, tr);
    }*/
}

int main() {
    read(n); read(m);
    for(int i = 1; i <= n; ++i) read(a[i]);
    build(1, 1, n);
    int l, r, x; char opt;
    while(m--) {
        while(opt = getchar(), opt != 'R' && opt != 'Q');
        read(l); read(r); read(x);
        if(opt == 'R') update(1, 1, n, l, r, x);
        else {
            if(x) {
                int lc = Qcol(1, 1, n, l), rc = Qcol(1, 1, n, r);
                if(lc == rc) {
                    int lm = Qlmax(1, 1, n, l, r), rm = Qrmax(1, 1, n, l, r);
                    //cout << lm << " " << rm << endl;
                    printf("%d\n", max(query(1, 1, n, l, r), min(lm + rm, r-l+1)));
                } else printf("%d\n", query(1, 1, n, l, r));
                //print(1, 1, n);
            } else printf("%d\n", query(1, 1, n, l, r));
        }
    }
}