# 朝田诗乃 的博客

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

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


#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;

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;}
}
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() {
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--) {
if(opt == 1) {
updatemax(1, 1, n, l, r);
} else if(opt == 2) {