朝田诗乃 的博客

朝田诗乃 的博客

题解 P5251 【[LnOI2019]第二代图灵机】

posted on 2019-03-11 17:51:45 | under 题解 |

对于20%的数据,对于每个Q操作,用 $O(n)$ 的复杂度在 $[l,r]$ 之间进行尺取(若熟悉尺取法可跳过):

对于3操作,

定理1 :若一个合法区间 $[l_1,r_1]$ 被另一个合法区间 $[l_2,r_2]$ 包含,则 $[l_2,r_2]$ 一定不是最优解。

由于数字都是正整数,证明显然。

定理2 :若一个区间 $[l_1,r_1]$ 是合法区间且 $[l_1,r_1]$ 内不包含其他合法区间,则 $[l_1+1,r_2](l_1+1 ≤ r_2 ≤ r_1)$ 一定不是一个合法区间。

这好像是废话

因此我们可以枚举左端点和与其对应的最优右端点,记为 $f(l)$ ,则 $f(l)$ 单增,枚举复杂度 $O(n)$ 。

对于4操作,尺取,过程与3几乎没有任何区别这里不在赘述。

对于100%的数据:

使用珂朵莉树(ODT,又称老司机树)维护颜色序列,由于数据随机,可将所求区间 $(l,r)$ 中的节点个数降到 $log$ 级别(证明百度,我也不记得为什么了),同20%做法进行暴力尺取。使用线段树维护区间数字和以更新答案。特别的,对于4操作,直接尺取可能丢失某些情况,因此我们还需要维护区间数字最大值。(这个实现的时候就会知道了)

在随机数据情况下,总复杂度 $O(nlog^2n)$

感谢@Sooke 提供的Hack数据,现已修正标程与数据。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <bitset>
#include <cstdlib>
#define IT set<node>::iterator
using namespace std;
const int MAXM = 150, MAXN = 100050;

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

void write(int x) {if(x > 9) write(x / 10); putchar(x % 10 + 48);}

struct node {
    int l, r;
    mutable int v;
    node(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
    bool operator < (const node &o) const {
        return l < o.l;
    }
};

set <node> s;
int n, m, q, ap[MAXM], t[MAXN], tree[MAXN << 2], w[MAXN];
int apt[MAXM];

int lowbit(int x) {return x & (-x);}

void update(int x, int val) {
    for(; x <= n; t[x] += val, x += lowbit(x));
}
int query(int x) {
    int res = 0;
    for(; x > 0; res += t[x], x -= lowbit(x));
    return res;
}
int ask(int l, int r) {return query(r) - query(l-1);}

void pushup(int i){tree[i] = max(tree[i << 1], tree[i << 1 | 1]);}

void updatemax(int i, int l, int r, int x, int val) {
    if (l == r) {tree[i] = val; return;}
    int mid = (l + r) / 2;
    if (x <= mid) updatemax(i << 1, l, mid, x, val);
    else updatemax(i << 1 | 1, mid + 1, r, x, val);
    pushup(i);
}

int querymax(int i, int l, int r, int x, int y) {
    if (x <= l && r <= y) return tree[i];
    int mx = 0, mid = (l + r) / 2;
    if (x <= mid) mx = max(mx, querymax(i << 1, l, mid, x, y));
    if (y > mid) mx = max(mx, querymax(i << 1 | 1, mid + 1, r, x, y));
    return mx;
}

IT spilit (int pos) {
    IT it = s.lower_bound(node(pos));
    if(it != s.end() && it->l == pos) return it;
    it--;
    int L = it -> l, R = it -> r;
    int V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
}

bool all_one(IT l, IT r) {
    if(l == r || (++l)-- == r) return 1;
    ++l;
    for(IT i = l; i != r; ++i)
        if(i->r != i->l) return 0;
    return 1;
}

void assign(int l, int r, int val = 0) {
    IT ir = spilit(r+1), il = spilit(l);
    s.erase(il, ir);
    s.insert(node(l, r, val));
}

int query1(int l, int r) {
    int ans = 2147483647, lef; memset(ap, 0, sizeof ap);
    IT ir = spilit(r+1), il = spilit(l), L, R; --il;
    L = R = il; lef = m;
    while(R != ir) {
        if(L != il) {--ap[L->v]; if(!ap[L->v]) ++lef;} ++L;
        while(lef && R != ir) {++R; ++ap[R->v]; if(ap[R->v] == 1) --lef;}
        if(R == ir) break;
        while(!lef && L != R) {--ap[L->v]; if(!ap[L->v]) ++lef; ++L;} 
        if(lef) {--L; ++ap[L->v]; --lef;}
        ans = min(ask(L->r, R->l), ans);
    }
    return ans;
}

int query2(int l, int r) {
    memset(apt, 0, sizeof apt);
    int ans = querymax(1, 1, n, l, r);
    IT ir = spilit(r+1), il = spilit(l), R, L;
    R = il; L = il;
    for( ;R != ir; ++R) {
        ++apt[R->v];
        while(!all_one(L, R)) --apt[L->v],++L;
        while(L != R && apt[R->v] > 1) --apt[L->v], ++L;
        if(L != R) ans = max(ans, ask(L->r, R->l));
    }
    return ans;
}

int main() {
    read(n); read(q); read(m);
    s.insert(node(0, 0, -1)); 
    for(int x, i = 1; i <= n; ++i) read(x), update(i, x), updatemax(1, 1, n, i, x);
    for(int x, i = 1; i <= n; ++i) read(x), s.insert(node(i, i, x));
    int opt, l, r, x;
    while(q--) {
        read(opt);
        if(opt == 1) {
            read(l); read(r);
            update(l, r - ask(l, l));
            updatemax(1, 1, n, l, r);
        } else if(opt == 2) {
            read(l); read(r); read(x);
            assign(l, r, x);
        } else if(opt == 3) {
            read(l); read(r);
            int ans = query1(l, r);
            if(ans == 2147483647) puts("-1"); 
            else write(ans), putchar('\n');
        } else if(opt == 4) {
            read(l); read(r);
            write(query2(l, r)); putchar('\n');
        }
    }
}