2023.8.14 nfls集训Day6 考试总结

2023暑nfls

前言：被打爆了！！！破防实录

Result

Progress

开题。

F：回文串串题，难受
G：网格图，相邻位置，40*40 范围 等于 网络流
H：我超，3000分的 DS，这是要维护个啥啊（事实证明到最后都没看懂题）

我超，怎么开完题有人 $F$ 就过了啊！！！

从开 $G$ 变成开 $F$，想了一会，考虑把先半径单增这个条件抽象成给每个点一个相对大小的权值，那可以规约到回文串中，做一个二关键字的回文。

那是不是 manacher 就好了，但是，我 不 会 写 manacher 了！！！

要吐了！！！

尝试回忆，回忆失败！我回去一定好好学串串！！！

无奈开 $G$，先黑白染色，玩一玩样例，猜了个结论叫最终状态一定是全为当前最大值。

感觉好对啊！直接开冲。

然后挂了，调了一会，感觉没问题，开始质疑！hack 成功！

为什么每天都在干这种事啊！！！！

冷静下来，重新观察一下性质，虽然结论挂了，但是结束状态长的样子很确定

找找操作里不变的东西，显然黑白差不变，然后推一推，改一改做法，又会了。

调了好久啊！！！但是最后还是过了。

回头看 $F$，收到信息可以 DP ？？？

为啥我 DP 也搞不出来啊！！！为啥大家都不带 log 啊，破防了！

LCIS 又是什么东西啊！太神奇了！最后只切 $G$ 破防收场。

F 完美队形

郑重记录一下这个神奇的东西：LCIS

首先一增一减的东西是很不好维护的，我们把串复制一遍并倒过来

可以发现 递增回文序列 等于 当前两个序列上的 最长公共上升子序列(LCIS)

而这个 LCIS 的求法也很简单。

我们先考虑一个 $O(n^3)$ 的求法。

$f(i,j)$ 为 A 串前 $i$，B 串前 $j$ 的 LCIS

如果 $A_i \neq B_j$ ：$f(i,j) = f(i - 1, j)$

否则 $A_i = B_j$ ：

可以发现这个 $k$ 的合法只跟 $A_i$ 有关，那显然可以记一下前缀 max 直接优化掉。

那这题就是个简单的 LCIS 板子。

G 做游戏

很长的操作的东西，可以考虑一下什么东西是不变的。

我们黑白染色，每次同时给相邻的 $+1$, 则显然有黑白块之间的差不变。

考虑最终状态全部相同，设最后全是 $x$，则有：

$(C_1 - C_0) x = S_1 - S_0$

然后初中知识分讨一下。

$C_1 - C_0 \neq 0$ ： $x$ 可得定值

$C_1 - C_0 = 0, S_1 - S_0 \neq 0$ 无解

$C_1 - C_0 = 0, S_1 - S_0 = 0$ 这说明 $x$ 全都合法，但显然答案关于 $x$ 递增，所以二分。

最后只剩如何 check $x$，这东西显然随便流，太好建模，不讲了。

H 线段树

一道很强大的 DS 啊！感觉无愧这个 3000 分。

本题第一个难点是对于这个询问操作的转换。

我们可以观察出这样一个性质：

假如一个区间 $x$，包含要查询的点 $K$，若 $x-1$ 与他有交，则 $Ans_K$ 为将两个区间并起来，原数组上新区间的max。

也就是说，我么可以通过区间合并，将询问转化为原序列上的一段区间 max

这个问题是平凡的。

但是！

我们发现将两个区间交换，其答案是不同的！换句话说，这个合并只能是从后往前有顺序的合并。

这就解释了为什么，你做区间合并时不能直接一颗主席树拍上去将整个 $[L,R]$ 合并。
（我一开始的想法）

既然只能从后往前合并，那就得先找出 $[L,R]$ 中最后一个包含 $k$ 的区间

这个问题不可持久化的话，可以区间覆盖+单点查询max

可持久化的问题在于 max 不可减，但实际上仔细想想。

求 $[1,R]$ 的答案与求 $[L,R]$ 的答案效果是一模一样的！如果答案求出来 $< L$ 一定无解，否则就是 $[L,R]$ 的答案。

这是此题第二个妙的地方。

那么已经求出最后一个区间 $End$，接下来要做的就是快速往前合并区间。

此题第三个妙的地方，这个过程实际上并不那么复杂，我们发现这个合并区间的操作本身就是左右可并的。

那我们如果求出每个区间与前一个有交的区间合并，我们就可以 倍增 的把所有前缀区间合并起来。

而带修很简单，在普通线段树上随意修改一下即可。

所以我们就用一颗（单点修改，区间取max）普通线段树 + （区间推平，单点路径max）主席树 + 倍增 解决了此题。

十分的妙！值得回味。

贴下代码。

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5, INF = 1e9 + 7;
int n, m, Q;
int Val[maxn], Root[maxn], L[maxn][25], R[maxn][25];
struct Quer {
    int l, r;
}Que[maxn];
namespace Sigment_Tree1 {
    struct node {
        int l, r;
        int maxx;
    }Tree[maxn << 2];
    #define lc(i) i << 1
    #define rc(i) i << 1 | 1
    inline void Push_Up(int i) { Tree[i].maxx = max(Tree[lc(i)].maxx, Tree[rc(i)].maxx); }
    inline void Build(int i, int l, int r) {
        Tree[i].l = l, Tree[i].r = r, Tree[i].maxx = INF;
        if(l == r) { Tree[i].maxx = Val[l]; return ; }
        int mid = (l + r) >> 1;
        Build(lc(i), l, mid), Build(rc(i), mid + 1, r);
        Push_Up(i);
    }
    inline void Update(int i, int l, int r, int x, int num) {
        if(l == r) { Tree[i].maxx = num; return ; }
        int mid = (l + r) >> 1;
        if(x <= mid) Update(lc(i), l, mid, x, num);
        else Update(rc(i), mid + 1, r, x, num);
        Push_Up(i);
    }
    inline int Query(int i, int l, int r, int ql, int qr) {
        if(l >= ql && r <= qr) return Tree[i].maxx;
        int mid = (l + r) >> 1, maxx = 0;
        if(ql <= mid) maxx = max(maxx, Query(lc(i), l, mid, ql, qr));
        if(qr > mid) maxx = max(maxx, Query(rc(i), mid + 1, r, ql, qr));
        return maxx;
    }
    #undef lc(i)
    #undef rc(i)
}
namespace Sigment_Tree2 {
    struct node {
        int ls, rs;
        int Tag;
    }Tree[maxn * 100];
    int tot = 0;
    #define lc(i) Tree[i].ls
    #define rc(i) Tree[i].rs
    inline void Copy(int &i, int v) { i = ++tot, Tree[i] = Tree[v]; }
    inline void Push_Up(int i) { Tree[i].Tag = max(Tree[lc(i)].Tag, Tree[rc(i)].Tag); }
    inline void Update(int &i, int v, int l, int r, int ql, int qr, int num) {
        Copy(i, v);
        if(l >= ql && r <= qr) { Tree[i].Tag = num; return ; } 
        int mid = (l + r) >> 1;
        if(ql <= mid) Update(lc(i), lc(v), l, mid, ql, qr, num);
        if(qr > mid) Update(rc(i), rc(v), mid + 1, r, ql, qr, num);
    }
    inline int Query(int i, int l, int r, int x, int Tag) {
        Tag = max(Tag, Tree[i].Tag);
        if(l == r) return Tag;
        int mid = (l + r) >> 1;
        if(x <= mid) return Query(lc(i), l, mid, x, Tag);
        else return Query(rc(i), mid + 1, r, x, Tag);
    }
}
int main() {
    // freopen("H.in", "r", stdin);
    // freopen("H.out", "w", stdout);
    n = read(), m = read(), Q = read();
    for(register int i = 1; i <= n; ++i) Val[i] = read();
   Sigment_Tree1::Build(1, 1, n);
    for(register int i = 1; i <= m; ++i) {
        Que[i].l = read(), Que[i].r = read();
        Sigment_Tree2::Update(Root[i], Root[i - 1], 1, n, Que[i].l, Que[i].r, i);
    }
    for(register int i = 1; i <= m; ++i) {
        L[i][0] = Sigment_Tree2::Query(Root[i - 1], 1, n, Que[i].l, 0);
        R[i][0] = Sigment_Tree2::Query(Root[i - 1], 1, n, Que[i].r, 0);
    }
    for(register int i = 1; i <= 20; ++i)
        for(register int x = 1; x <= m; ++x) {
            L[x][i] = L[L[x][i - 1]][i - 1];
            R[x][i] = R[R[x][i - 1]][i - 1];
        }
    while(Q--) {
        int op = read();
        if(op == 1) {
            int x = read(), num = read();
            Sigment_Tree1::Update(1, 1, n, x, num);
        }
        else {
            int l = read(), r = read(), x = read();
            int End = Sigment_Tree2::Query(Root[r], 1, n, x, 0);
            if(End < l) printf("%d\n", Sigment_Tree1::Query(1, 1, n, x, x));
            else {
                int Lpos = End, Rpos = End;
                for(register int i = 20 ; i >= 0; --i) {
                    if(L[Lpos][i] >= l) Lpos = L[Lpos][i];
                    if(R[Rpos][i] >= l) Rpos = R[Rpos][i];
                }
                l = Que[Lpos].l, r = Que[Rpos].r;
                printf("%d\n", Sigment_Tree1::Query(1, 1, n, l, r));
            }
        }
    }
    return 0;
}