题解 P5251 【[LnOI2019]第二代图灵机】
诗乃
2019-03-11 17:51:45
对于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数据，现已修正标程与数据。
```cpp
#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');
}
}
}
```