作者: JvJvmore

Educational Codeforces Round 112 (Rated for Div. 2)

https://codeforces.com/contest/1555

C. Coin Rows

题意:
两行数,第一个人先走,拿走所有经过的;第二个人再走。只能往右下走,从左上出发。第一个人想让第二个拿的最少,第二个人要拿的最多,问第二个人拿多少

做法:
推一下发现是第二层的前缀和与第一层后缀和取max

拓展:
不妨考虑一下若不止两行该怎么做

D. Say No to Palindromes

题意:
给一个由abc三个字母组成的串,问至少改几个字母使得每个子串均不为长度大于1的回文。每次询问原串的一个子串

做法:
观察可知条件等价为连续三个字符各不相同,共六种情况,枚举即可,答案满足可加性

E. Boring Segments

题意:
数轴上给若干条线段,给出左右端点及其权值。当选取一条线段时,其覆盖的所有整点“连通”。现要求选定一个子集,使全部整点连通,同时使得最大权值减最小权值最小

做法:
首先,“连通”条件可进行转化:所有整点“连通”等价为所有整点及半整点 (x.5) 均被覆盖
由此,可以利用线段树对整体连通性进行维护:将点数翻倍(加上半整点),添加线段即区间 +1,移除即区间 -1,若全局最小值大于 0 则为连通
基于此,不难想到另一部分,将线段按权值从小到大排序,用 2-pointer 就能 O(n) 枚举所有情况
总复杂度 O(nlogn)

AC代码

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_N = 3E5 + 100;
const int MAX_M = 2E6 + 100;
const int INF = 1E6 + 100;

class SegmentTree {
   private:
    int n;
    int a[MAX_M << 2], lz[MAX_M << 2];

    void modify(int n, int l, int r, int ll, int rr, int x) {
        if (ll <= l && r <= rr) {
            a[n] += x;
            lz[n] += x;
            return;
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        if (ll <= mid) modify(n << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(n << 1 | 1, mid + 1, r, ll, rr, x);
        a[n] = min(a[n << 1], a[n << 1 | 1]);
    }

   public:
    void init(int _n) { n = _n; }

    void modify(int l, int r, int x) { modify(1, 1, n, l, r, x); }

    bool query() { return a[1]; }
};

class Segment {
   public:
    int l, r, w;
    bool operator<(const Segment& s) { return w < s.w; }
};

int n, m;
SegmentTree tr;
Segment seg[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> seg[i].l >> seg[i].r >> seg[i].w;
        seg[i].l = seg[i].l * 2 - 1;
        seg[i].r = seg[i].r * 2 - 1;
    }
    sort(seg, seg + n);
    tr.init(2 * m - 1);
    // init

    int ans = INF;
    int l = 0, r = -1;
    while (!tr.query()) {
        r += 1;
        tr.modify(seg[r].l, seg[r].r, 1);
    }

    while (l < n) {
        if (tr.query()) ans = min(ans, seg[r].w - seg[l].w);
        tr.modify(seg[l].l, seg[l].r, -1);
        l += 1;
        while (r + 1 < n && !tr.query()) {
            r += 1;
            tr.modify(seg[r].l, seg[r].r, 1);
        }
    }

    cout << ans << endl;

    return 0;
}

心路历程:
折磨了一个多小时没想出来,最后看的题解
2-pointer倒不难想,维护这样的权值模式排序后这么扫比较常见
维护是完全没想到,一直在考虑dp线段树优化,最关键的第一步转化还是第一次见,是一个好技巧

F. Good Graph

题意:
动态维护一个图,只有加边操作。需要满足加边后任一简单环上异或和为 1,否则添加失败

做法:

首先观察出下面几个性质

  1. 若添加前两端点不连通,则添加成功
  2. 若添加的两端点在一棵树上,则路径异或和为 1 时添加成功
  3. 若添加的两点已经在一个简单环上,添加必失败
  4. 若添加的两端点间原路径有任一段包含在任一环上,添加必失败

后两条性质整合一下就是当添加的两端点间的路径经过一条环的边的话,必失败
然后就结束了,这显然用LCT维护就好了
需要注意的是IO量比较大,需要快读

AC代码

#include <cstdio>
#include <utility>
using namespace std;

const int MAX_N = 3E5 + 100;

class Node {
   public:
    int val, tot;
    bool isEdge;
    int eSz;
    int flag, flz, fTot;
    bool flip;
    Node *c[2], *p, *pp;

    void fix() {
        tot = val;
        fTot = flag;
        eSz = isEdge;
        if (c[0]) {
            c[0]->p = this;
            tot ^= c[0]->tot;
            fTot += c[0]->fTot;
            eSz += c[0]->eSz;
        }

        if (c[1]) {
            c[1]->p = this;
            tot ^= c[1]->tot;
            fTot += c[1]->fTot;
            eSz += c[1]->eSz;
        }
    }

    void pushFlip() {
        if (flz) {
            flz = 0;
            flag = isEdge;
            if (c[0]) {
                c[0]->flz = 1;
                c[0]->fTot = c[0]->eSz;
            }
            if (c[1]) {
                c[1]->flz = 1;
                c[1]->fTot = c[1]->eSz;
            }
        }

        if (!flip) return;
        flip = 0;
        swap(c[0], c[1]);
        if (c[0]) c[0]->flip ^= 1;
        if (c[1]) c[1]->flip ^= 1;
    }

    int type() { return p ? this == p->c[1] : 2; }

    void rot(int i, int j) {
        bool b = i ^ j;
        Node *x = c[i], *y = 2 == j ? x : x->c[j], *z = b ? y : x;

        if (y->p = p) p->c[type()] = y;
        c[i] = z->c[i ^ 1];
        if (j < 2) {
            x->c[j] = y->c[j ^ 1];
            z->c[j ^ 1] = b ? x : this;
        }
        y->c[i ^ 1] = b ? this : x;

        fix();
        x->fix();
        y->fix();

        swap(pp, y->pp);
    }

    void splay() {
        for (pushFlip(); p;) {
            if (p->p) p->p->pushFlip();
            p->pushFlip();
            pushFlip();

            if (2 == p->type())
                p->rot(type(), 2);
            else
                p->p->rot(p->type(), type());
        }
    }

    Node *first() {
        pushFlip();
        return c[0] ? c[0]->first() : (splay(), this);
    }
};

class LCT {
   public:
    Node node[MAX_N << 1];

    Node *access(Node *u) {
        for (u->splay(); Node *pp = u->pp; u = pp) {
            pp->splay();
            u->pp = 0;

            if (pp->c[1]) {
                pp->c[1]->p = 0;
                pp->c[1]->pp = pp;
            }
            pp->c[1] = u;
            pp->fix();
        }
        return u;
    }

    void makeRoot(Node *u) {
        access(u);
        u->splay();
        if (u->c[0]) {
            u->c[0]->flip ^= 1;
            u->c[0]->p = 0;
            u->c[0]->pp = u;
            u->c[0] = 0;
            u->fix();
        }
    }

    bool connected(Node *u, Node *v) {
        Node *ru = access(u)->first();
        return ru == access(v)->first();
    }

    void link(Node *u, Node *v) {
        if (connected(u, v)) return;
        makeRoot(u);
        u->pp = v;
    }

    void cut(Node *u, Node *v) {
        makeRoot(v);
        u->splay();
        if (v != (u->pp ?: u->c[0])) return;
        if (u->pp) {
            u->pp = 0;
        } else {
            u->c[0] = v->p = 0;
            u->fix();
        }
    }

    //====================

    Node *access(int u) { return access(node + u); }
    void makeRoot(int u) { makeRoot(node + u); }
    bool connected(int u, int v) { return connected(node + u, node + v); }
    void link(int u, int v) { link(node + u, node + v); }
    void cut(int u, int v) { cut(node + u, node + v); }
};

int read() {
    int ret = 0;
    char c = getchar();
    while ('0' > c || c > '9') c = getchar();
    while ('0' <= c && c <= '9') {
        ret *= 10;
        ret += c - '0';
        c = getchar();
    }
    return ret;
}

int n, q, m;
int a[MAX_N];
LCT tr;

int main() {
    n = read();
    q = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = i;
    }
    m = n;

    while (q--) {
        int u = read(), v = read(), w = read();
        if (!tr.connected(u, v)) {
            puts("YES");

            m += 1;
            tr.node[m].isEdge = 1;
            tr.node[m].val = w;
            tr.link(u, m);
            tr.link(v, m);
        } else {
            tr.makeRoot(u);
            tr.access(v);
            tr.node[v].splay();

            if (tr.node[v].fTot -
                (tr.node[v].c[1] ? tr.node[v].c[1]->fTot : 0)) {
                puts("NO");
            } else if (1 ==
                       (tr.node[v].tot ^
                        (tr.node[v].c[1] ? tr.node[v].c[1]->tot : 0) ^ w)) {
                puts("YES");
                tr.node[v].c[0]->flz = 1;
                tr.node[v].c[0]->fTot = tr.node[v].c[0]->eSz;
            } else {
                puts("NO");
            }
        }
    }

    return 0;
}

心路历程
想出性质的时候还不会LCT,当时考虑的做法是缩点处理后两个性质
然后写了奇怪的LCT,维护了很多东西,常数巨大,T了
苦思之后在梦里想起有快读这么个东西,赶紧爬起来改了,就过了

Educational Codeforces Round 111 (Rated for Div. 2)

https://codeforces.com/contest/1550

D. Excellent Arrays

题意
要求构造一个数列 a ,使得 a_i + a_j = i + ja_i \neq i
给定数列长度 n,元素上下界 l, r
求数列的种类数模 10^9 + 7

数据范围
2\leq n \leq 2\sdot 10^5, -10^9 \leq l \leq 1, n \leq r \leq 10^9
多组数据保证 n 的和不超过上界

做法
首先很容易发现,数列一定是由 i - xi + x 一半一半构成的(奇数有一个可任选)
再看复杂度,很显然,枚举一个量级为 n 的东西即可
进一步地,发现 l, r, x 要满足下列关系
不妨考虑数列分为三段:分界点为最靠前的- x最靠后的+ x,不妨记为ll, rr
那么有关系 ll - x \geq l, rr + x \leq r,即 rr \leq r - x, ll \geq l + x
即给定 x,大于 r - xi 必须全取 i - x, 小于 l + xi 必须全取 i + x,剩下的可任意取
注意到只有当 r - x < nl + x > 1 的时候会受上下界影响,且不能过半,只用枚举一个 O(n) 的范围即可

AC代码

#include <iostream>
using namespace std;

#define int long long

const int MAX_N = 2E5 + 100;
const int MOD = 1E9 + 7;

int bin(int x, int n) {
    int ret = 1;
    for (; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

int fac[MAX_N], facInv[MAX_N];
void initInv(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 0; i <= n; ++i) facInv[i] = bin(fac[i], MOD - 2);
}

// 0 <= n <= m
inline int C(int n, int m) {
    return fac[m] * facInv[n] % MOD * facInv[m - n] % MOD;
}

int T;
int n, l, r;

signed main() {
    initInv(2E5);

    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> l >> r;
        int ans = 0;
        int ll = min(r - n, 1 - l);
        int rr = ll + (n + 1) / 2;

        if (n & 1) {
            ans += 2 * max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2 + 1) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
                if (lp <= n / 2 + 1 && rp <= n / 2) {
                    ans = (ans + C(n / 2 + 1 - lp, n - lp - rp)) % MOD;
                }
            }
        } else {
            ans += max(0ll, ll - 1) * C(n / 2, n) % MOD;
            for (int x = max(1ll, ll); x <= rr; ++x) {
                int rp = max(0ll, n - r + x);
                int lp = max(0ll, l + x - 1);
                if (lp <= n / 2 && rp <= n / 2) {
                    ans = (ans + C(n / 2 - lp, n - lp - rp)) % MOD;
                }
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

心路历程
最开始考虑枚举 ll,rr,利用式子 1 \leq x \leq Min\{ll - l, r - rr\} 确定 x
发现做不了,枚举 x 更方便,遂改邪归正

E. Stringforces

题意
给一个长度为 n 的包含前 k 个小写字母与 ? 的字符串
要求将 ? 替换为小写字母,使得以每个小写字母为全部元素的最长连续子串长度的最小值最大
例如串 aaababbbb a的长为3,b的长为4,最小值为3

数据范围
1\leq n \leq 2 \sdot 10^5, 1\leq k \leq 17

做法
挺明显的二分答案,关键在于如何check
因为 k 给的很小,所以check往 O(2^k) 上考虑,但是在那之前首先考虑更小的做法
题意转化为,给定一个长度 m,要求对于每种字母都构造出至少一段这样长度的子串
假如给定这些子串的排列顺序,那么贪心可以 O(k + n) 解决
即只要使每个子串尽量靠左即可,具体做法为dp记录每种元素的最靠左的完成子串位置即可
但是枚举排列顺序需要 O(k!) 显然不行
不过显然这 k! 种排列大量重叠,具有相同前缀
很容易想到优化成 O(2^k) 的做法,类似dfs弄一下,2^k 状态,O(k) 转移,再 O(kn) 预处理
check总复杂度为 O(k2^k + kn)

AC代码

#include <iostream>
#include <queue>
using namespace std;

const int MAX_N = 2E5 + 100;
const int MAX_K = 20;

int n, k;
char s[MAX_N];
int a[MAX_N], dp[MAX_N];
int b[MAX_N][MAX_K];

bool check(int m) {
    static int tmp[MAX_K];
    for (int i = 1; i <= k; ++i) {
        tmp[i] = -1;
        b[n + 1][i] = n + 1;
    }
    for (int i = n; i >= 1; --i) {
        if (a[i]) {
            for (int j = 1; j <= k; ++j) {
                if (j != a[i]) tmp[j] = -1;
            }
            if (-1 == tmp[a[i]]) tmp[a[i]] = i;
        } else {
            for (int j = 1; j <= k; ++j) {
                if (-1 == tmp[j]) tmp[j] = i;
            }
        }

        for (int j = 1; j <= k; ++j) {
            if (tmp[j] - i + 1 >= m) {
                b[i][j] = i + m - 1;
            } else {
                b[i][j] = b[i + 1][j];
            }
        }
    }
    // init

    for (int i = 0; i <= (1 << k) - 1; ++i) {
        dp[i] = n + 2;
    }
    queue<int> que;
    que.push(0);
    dp[0] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int i = 1, j = 1; j <= k; i <<= 1, j += 1) {
            if (~u & i) {
                int v = u | i;
                int w = b[dp[u]][j];
                if (w <= n) {
                    if (n + 2 == dp[v]) que.push(v);
                    dp[v] = min(dp[v], w + 1);
                }
            }
        }
    }

    return dp[(1 << k) - 1] <= n + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    cin >> (s + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = '?' == s[i] ? 0 : s[i] - 'a' + 1;
    }
    a[n + 1] = -1;
    // init

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    if (!check(r)) r -= 1;

    cout << r << endl;

    return 0;
}

心路历程
自己想的时候只想到二分答案和 2^k,之后就懵逼了
最后看了题解才捋清了思路
转移的时候忘记规划取min以及多次入队了,WA一发MLE一发,数据似乎挺水的

Codeforces Round 727 (Div. 2)

https://codeforces.com/contest/1539

E. Game with Cards

题意:
n 个回合游戏
初始时左右手各有一张值为 的卡片
每个回合会提供一张值为 k_i 的卡片,必须将其与左手或右手的卡片交换
要求每个回合后满足左右手的卡片值分别落在指定区间内
a_{l,i} \leq l \leq b_{l, i}, a_{r,i} \leq r \leq b_{r,i}

数据范围:
2 \leq n \leq 10 ^ 5
2 \leq m \leq 10^9
0 \leq k_i \leq m
0 \leq a_{l,i} \leq b_{l,i} \leq m,\ 0 \leq a_{r,i} \leq b_{r,i} \leq m

做法:
考虑每次交换对未来产生的影响,即其在未来能继续满足多少回合的区间
容易发现,这个“影响”越远越好
那么可以用dp来维护这个影响
f[i][0/1] 代表进行第 i 个回合,交换左/右手后,另一只手上的数字的最远影响范围
若记 g[i][0/1] 代表 k[i] 在左/右手时,满足 [i, g[i][0/1]] 的条件,而不满足 [i, g[i][0/1] + 1] 的条件
意会一下就能构造出转移方程,即满足条件且最大化 f[i][0/1]
那么考虑怎么获得 g[i][0/1]
即考虑这样一个问题:
给定一任意数组 a ,给 n 次询问,每次给出值 p ,求满足 a_i \geq p 的最小下标
挺显然可以用权值线段树离线维护,从右往左扫一遍
总复杂度 O(n + nlogn)

AC代码:

#include <iostream>
using namespace std;

#define int long long

const int MAX_N = 1E5 + 100;
const int INF = MAX_N;

class SegmentTree {
   private:
    int n, m;
    class Node {
       public:
        int a = INF, l, r;
    } a[20 * MAX_N];

    void modify(int n, int l, int r, int p, int x) {
        if (l == r) {
            a[n].a = min(a[n].a, x);
            return;
        }

        int mid = (l + r) >> 1;
        if (p <= mid) {
            if (!a[n].l) a[n].l = ++m;
            modify(a[n].l, l, mid, p, x);
        } else {
            if (!a[n].r) a[n].r = ++m;
            modify(a[n].r, mid + 1, r, p, x);
        }

        a[n].a = INF;
        if (a[n].l) a[n].a = min(a[n].a, a[a[n].l].a);
        if (a[n].r) a[n].a = min(a[n].a, a[a[n].r].a);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (0 == n) return INF;
        if (ll <= l && r <= rr) {
            return a[n].a;
        }

        int mid = (l + r) >> 1;
        int ret = INF;
        if (ll <= mid) ret = min(ret, query(a[n].l, l, mid, ll, rr));
        if (mid < rr) ret = min(ret, query(a[n].r, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) {
        n = _n;
        m = 1;
    }

    void modify(int p, int x) { modify(1, 1, n, p + 1, x); }

    int query(int l, int r) { return query(1, 1, n, l + 1, r + 1); }
};

int n, m;
int k[MAX_N];
int a[MAX_N][2];
int lt[MAX_N][2], rt[MAX_N][2];
int ans[MAX_N];

SegmentTree trr[2], trl[2];

int dp[MAX_N][2];
int lst[MAX_N][2];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    trl[0].init(m + 1);
    trl[1].init(m + 1);
    trr[0].init(m + 1);
    trr[1].init(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
        cin >> lt[i][0] >> rt[i][0];
        cin >> lt[i][1] >> rt[i][1];
    }

    for (int i = n; i >= 1; --i) {
        trl[0].modify(lt[i][0], i);
        trr[0].modify(rt[i][0], i);
        trl[1].modify(lt[i][1], i);
        trr[1].modify(rt[i][1], i);

        a[i][0] = min(trl[0].query(k[i] + 1, m), trr[0].query(0, k[i] - 1)) - 1;
        a[i][1] = min(trl[1].query(k[i] + 1, m), trr[1].query(0, k[i] - 1)) - 1;
    }
    a[0][0] = trl[0].query(1, m) - 1;
    a[0][1] = trl[1].query(1, m) - 1;
    dp[0][0] = a[0][1];
    dp[0][1] = a[0][0];

    for (int i = 1; i <= n; ++i) {
        if (a[i][0] >= i) {
            if (-1 == dp[i - 1][1] || dp[i - 1][0] >= a[i - 1][1]) {
                dp[i][0] = dp[i - 1][0];
                lst[i][0] = 0;
            } else {
                dp[i][0] = a[i - 1][1];
                lst[i][0] = 1;
            }

            if (dp[i][0] < i) dp[i][0] = -1;
        } else {
            dp[i][0] = -1;
        }

        if (a[i][1] >= i) {
            if (-1 == dp[i - 1][0] || dp[i - 1][1] >= a[i - 1][0]) {
                dp[i][1] = dp[i - 1][1];
                lst[i][1] = 1;
            } else {
                dp[i][1] = a[i - 1][0];
                lst[i][1] = 0;
            }

            if (dp[i][1] < i) dp[i][1] = -1;
        } else {
            dp[i][1] = -1;
        }
    }

    if (-1 != dp[n][0]) {
        cout << "Yes" << endl;

        ans[n + 1] = 0;
        for (int i = n; i >= 2; --i) {
            ans[i] = lst[i][ans[i + 1]];
        }
        for (int i = 2; i <= n + 1; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else if (-1 != dp[n][1]) {
        cout << "Yes" << endl;

        ans[n + 1] = 1;
        for (int i = n; i >= 2; --i) {
            ans[i] = lst[i][ans[i + 1]];
        }
        for (int i = 2; i <= n + 1; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

心路历程:
思路想了一会,但是显然完全没想清楚
线段树维护的东西一直在修修补补(主要是端点值),dp方程也一直在改
小错误相当多,乱WA了20发才过
另外还读错题意了

Bob holds one card with number 0 in the left hand and one in the right hand

这一句我直接用翻译拿到的是,左手是0右手是1
留着以后下饭用

F. Strange Array

题意:
给一个数组,对于每个数要求计算一个“奇怪值”,定义如下
任选一个子区间,排序后(相等值任意调换),每个值到中心位置(偶数取右侧)的距离将对奇怪值产生贡献
一个数的奇怪值就是它的贡献的最大值

数据范围:
1 \leq n \leq 2·10^5,\ 1\leq a_i \leq n

做法:
子区间排序后当前数距中位数的距离,直接维护显然困难
考虑换一种角度想这个东西
记子区间内大于当前数的数量有 p, 小于当前数的数量有 q
则这一距离可以转化为一个用 p, q 表示的式子,大致是 abs(p - q)/2,再上下取整弄一下
问题转化为了对于每个数,寻找子区间来最大化与最小化 p - q
更进一步的,维护的区间可以从待询问的数那里拆成左右两半分别维护,最后加起来即可
这个东西可以用线段树离线维护
考虑从小到大依次加入数字,那么未加入的都是比当前值大的
考虑一个数组 c 来记录这个关系,若 a_i < a_{cur} 这一位取-1,大于则为 1
那么一个区间的 p - q 即为 \Sigma c_i
最后考虑一下等于的情况该怎么处理就好了

AC代码:

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MAX_N = 2E5 + 100;
const int INF = MAX_N;

class SegmentTree1 {
   private:
    int n;
    int a[MAX_N << 2];
    int lz[MAX_N << 2];

    void modify(int n, int l, int r, int ll, int rr, int x) {
        if (ll <= l && r <= rr) {
            a[n] += x;
            lz[n] += x;
            return;
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        if (ll <= mid) modify(n << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(n << 1 | 1, mid + 1, r, ll, rr, x);
        a[n] = max(a[n << 1], a[n << 1 | 1]);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return a[n];
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        int ret = -INF;
        if (ll <= mid) ret = max(ret, query(n << 1, l, mid, ll, rr));
        if (mid < rr) ret = max(ret, query(n << 1 | 1, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) { n = _n; }

    void modify(int l, int r, int x) { modify(1, 1, n, l, r, x); }

    int query(int l, int r) { return query(1, 1, n, l, r); }
};

class SegmentTree2 {
   private:
    int n;
    int a[MAX_N << 2];
    int lz[MAX_N << 2];

    void modify(int n, int l, int r, int ll, int rr, int x) {
        if (ll <= l && r <= rr) {
            a[n] += x;
            lz[n] += x;
            return;
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        if (ll <= mid) modify(n << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(n << 1 | 1, mid + 1, r, ll, rr, x);
        a[n] = min(a[n << 1], a[n << 1 | 1]);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return a[n];
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        int ret = INF;
        if (ll <= mid) ret = min(ret, query(n << 1, l, mid, ll, rr));
        if (mid < rr) ret = min(ret, query(n << 1 | 1, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) { n = _n; }

    void modify(int l, int r, int x) { modify(1, 1, n, l, r, x); }

    int query(int l, int r) { return query(1, 1, n, l, r); }
};

int n;
map<int, vector<int>> mp;
SegmentTree1 tr1, tr2;
SegmentTree2 tr3, tr4;
int ans[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    tr1.init(n);
    tr2.init(n);
    tr3.init(n);
    tr4.init(n);
    for (int i = 1; i <= n; ++i) {
        int u;
        cin >> u;
        mp[u].push_back(i);

        tr1.modify(i, i, i);
        tr2.modify(i, i, n - i + 1);
        tr3.modify(i, i, i);
        tr4.modify(i, i, n - i + 1);
    }
    // init

    for (auto it : mp) {
        for (int i : it.second) {
            tr3.modify(i, n, -2);
            tr4.modify(1, i, -2);
        }

        for (int i : it.second) {
            int lA = tr2.query(1, i) - tr2.query(i, i);
            int rA = tr1.query(i, n) - tr1.query(i, i);
            int lB = tr4.query(1, i) - tr4.query(i, i);
            int rB = tr3.query(i, n) - tr3.query(i, i);
            ans[i] = max(abs((lA + rA + 1) / 2), abs((lB + rB) / 2));
        }

        for (int i : it.second) {
            tr1.modify(i, n, -2);
            tr2.modify(1, i, -2);
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}

心路历程:
反应过来思路挺快的,写第一遍代码也挺快的
只是没想得太清楚,线段树没想够该用多少棵,等于的情况也只考虑了一半
调了蛮久的

2017-2018 Northwestern European Regional Contest (NWERC 2017)

https://codeforces.com/gym/101623

A. Ascending Photo

题意:
给一个数字串,需要花 x 刀将其切成 x + 1 个子段,满足任意排列子段后使整体有序,最小化 x 并输出

数据范围:
串长 1e6 ,元素 1 \leq h_i \leq 2e9

做法:
dp&map
反过来考虑,先全部切掉再组合,考虑怎么排可以少切一些
可以操作的空间只有相等的元素,两元素在原串与最终串中仍相邻则可少切一次,基于这个可以将原问题规约为dag考虑
dp很好考虑,从最终状态出发,f[i][j] 表示对于第 i 种元素,以其第 j 个结尾时的最小代价。转移方程如下
f[i][j] = {min}\{f[i - 1][p] + cal(i - 1, j)\}
cal 的作用大概就是算出 i 不以 j 开头时能否少切一次
总状态数为 O(n),转移搞搞可以弄成均摊 O(1) 的,总复杂度大概是 O(nlogn)
需要注意的是:相邻相同去重,离散化,单个元素的特殊情况

AC代码:

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MAX_N = 1E6 + 100;
const int INF = MAX_N;

int n, m;
map<int, int> mp;
map<int, int> f[MAX_N];
vector<int> G[MAX_N];
int h[MAX_N];

void init() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        mp[h[i]] = 0;
    }

    int oft = 0;
    for (int i = 2; i <= n; ++i) {
        if (h[i] == h[i - 1 - oft]) {
            oft += 1;
        }
        h[i - oft] = h[i];
    }
    n -= oft;
    //相邻去重

    int cnt = 0;
    for (auto& it : mp) {
        it.second = ++cnt;
    }
    for (int i = 1; i <= n; ++i) {
        h[i] = mp[h[i]];
        G[h[i]].push_back(i);
        m = max(m, h[i]);
    }
    //离散化,转为dag
}

int main() {
    ios::sync_with_stdio(false);
    init();

    f[0][0] = INF;
    f[0][n + 1] = 0;
    for (auto it : mp) {
        int i = it.second;

        int bs = INF;
        for (auto it : f[i - 1]) {
            bs = min(bs, it.second + (int)G[i].size());
        }
        //不连接时的最小值

        int mi = bs, mip = 0;  //最小值
        int si = bs, sip = 0;  //次小值
        for (int j : G[i]) {
            if (i - 1 == h[j - 1]) {
                if (si > f[i - 1][j - 1] + (int)G[i].size() - 1) {
                    si = f[i - 1][j - 1] + (int)G[i].size() - 1;
                    sip = j;

                    if (mi > si) {
                        swap(mi, si);
                        swap(mip, sip);
                    }
                }
            }
        }

        if (G[i].size() > 1) {
            for (int j : G[i]) {
                if (j == mip)
                    f[i][j] = si;
                else
                    f[i][j] = mi;
            }
        } else {
            f[i][G[i].back()] = mi;
        }
    }

    int ans = INF;
    for (auto it : f[m]) {
        ans = min(ans, it.second);
    }
    cout << ans - 1 << endl;

    return 0;
}

用例:

7
1 2 3 4 2 3 5
//3

7
1 2 3 4 2 4 5
//3

14
2 2 3 3 5 5 1 1 2 2 3 3 4 4
//3

心路历程:
训练的时候思路是从一个假贪心出发
规约着就变成了个链式约束的n-sat,然后越走越偏最后开始网络流乱搞(如果上课好好听讲,早知道这是个NP,就不至于这样了XD)
其实当时也想过dp,转移都想的差不多了,但是复杂度算错了,主要是第二维不知道怎么想的直接当 $n$ 算了,主要没想到用map来存状态
其实不是难题,但是硬刚了5h,说明大脑还是不够升级,思路也不够广
补的时候花了1h才调好,码力也不够XD

F. Factor-Free Tree

题意:
当且仅当一棵带权二叉树的所有节点满足:其权与其所有祖先的权互质,其为Factor-Free。现给一棵二叉树的前序遍历,构造一棵Factor-Free的树,若不可能,输出impossible
数据范围:
1 \leq n \leq 10^6,\ 1 \leq a_i \leq 10^7,时限3s

做法:
分解质因数,O(n \frac{\sqrt a}{loga} )
预处理每个数的最大互质区间 l[i], r[i]O(nloga) 空间 O(a)
对于区间 [ll, rr], 满足 ll \leq i \leq rr, l[i] \leq ll, rr \leq r[i]i 能作为这个区间的根,将区间分为 [ll, i - 1], [i + 1, rr],递归解决
可以证明,若有多个节点满足条件,可任取一个作为根
找根直接搜索即可,从两端往中间搜,找到即结束搜索
普通暴力容易想到卡成 O(n^2) 的数据,按照上述策略搜索则不会,复杂度不会证,猜测为 O(nlogn)
总复杂度 O(n \frac{\sqrt a}{loga} + nloga + nlogn)

AC代码:

#include <iostream>
using namespace std;

const int MAX_N = 1E6 + 100;
const int MAX_A = 1E7 + 100;
const int MAX_SQRT_A = 4E3 + 100;
const int MAX_LOG_A = 27;

int pSz, pr[MAX_SQRT_A];
void initPrime(int n) {
    static bool vis[MAX_SQRT_A];
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) pr[pSz++] = i;
        for (int j = 0; j < pSz; ++j) {
            if (pr[j] * i > n) break;
            vis[pr[j] * i] = true;
            if (0 == i % pr[j]) break;
        }
    }
}

int fSz, fac[MAX_LOG_A];
void getFac(int x) {
    fSz = 0;
    for (int j = 0; j < pSz; ++j) {
        if (x % pr[j]) continue;
        fac[fSz++] = pr[j];
        while (0 == x % pr[j]) {
            x /= pr[j];
        }
    }

    if (x > 1) {
        fac[fSz++] = x;
    }
}

int n;
int ans[MAX_N];

int p[MAX_A];
int l[MAX_N], r[MAX_N];

bool solve(int ll, int rr, int fat) {
    if (ll > rr) {
        return true;
    }
    if (ll == rr) {
        ans[ll] = fat;
        return true;
    }

    for (int i = ll, j = rr; i <= j; ++i, --j) {
        if (l[i] <= ll && rr <= r[i]) {
            ans[i] = fat;
            return solve(ll, i - 1, i) && solve(i + 1, rr, i);
        }

        if (l[j] <= ll && rr <= r[j]) {
            ans[j] = fat;
            return solve(ll, j - 1, j) && solve(j + 1, rr, j);
        }
    }

    return false;
}

int main() {
    initPrime(3200);

    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int u;
        cin >> u;
        getFac(u);

        l[i] = 1;
        r[i] = n;
        for (int j = 0; j < fSz; ++j) {
            l[i] = max(l[i], p[fac[j]] + 1);
            r[p[fac[j]]] = min(r[p[fac[j]]], i - 1);
            p[fac[j]] = i;
        }
    }
    //初始化l, r

    if (solve(1, n, 0)) {
        for (int i = 1; i <= n; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

心路历程:
做法的前半大概10m就想到了,但是想不到基于l,r数组来找根的合适做法,一直觉得复杂度不对,考虑了一整天奇怪数据结构
最后突然来了灵感搜了题解,发现没人讲最后面这个怎么搞,发现不对劲,试着分析了一下复杂度发现可以不是 O(n^2)
做的时候当了点子王,犯了nt错误,贴在下面供以后娱乐

bool solve(int ll, int rr, int fat) {
    ...
    bool flag;  //利用堆空间未初始化的随机特性
    for (int i = ll, j = rr; i <= j;) {
        if (flag) {
            ...
        } else {
            ...
        }
        flag = !flag;
    }
    ...
}

测试之后发现,只要初始化flag就能过
对这个问题又做了进一步测试,代码如下

#include <iostream>
using namespace std;

bool go(int i) {
    bool flag;
    for (int j = 0; j < i; ++j)
    flag = !flag;
    return flag;
}

int main() {
    ios::sync_with_stdio(false);

    bool t;
    for (int i = 0; i < 2E5; ++i) t ^= go(i);
    cout << t << endl;

    return 0;
}

用的是cf的评测机,并没有发现对效率有影响,而且即使没有初始化,也是为false的(没有广泛测试)
所以最后我猜是这个东西影响了O2优化,因为不显式初始化的话,编译器并不知道初始值

J. Juggling Troupe

题意:
给一个元素为0,1,2的串,其在每个时刻会发生如下变化
假如一个位置(1\leq i \leq n)上的 a_i \geq 2 ,将会发生:a_i =a_i-2, a_{i-1} = a_{i-1} +1, a_{i + 1} = a_{i + 1} + 1
注意边界会"吞掉"数
同一时刻所有的变化同时发生
问时间足够长后,串的内容为什么

数据范围:
1 \leq n \leq 10^6, 0 \leq a_i \leq 2

做法:
打个表,发现如下两个规律:

  1. 操作可拆分,例如 0012200 -> 0111101,可拆为0011200 -> 0101110 -> 0102110 -> 0111101
  2. 连续的一串1中一个2会在对称位置产生0,并且区间左右延长一格,例如 00112100 -> 01101110

之后链表维护一下就好了

AC代码:

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 1E6 + 100;

int n;
char s[MAX_N];
vector<int> que;

int head, tail, m;
int l[MAX_N << 1], r[MAX_N << 1];
int lst[MAX_N << 1], nxt[MAX_N << 1];

int i;
void go(int p) {
    while (nxt[i] && p >= l[nxt[i]]) {
        i = nxt[i];
    }

    if (p > r[i]) {
        if (p == r[i] + 1 && p == l[nxt[i]] - 1) {
            r[i] = r[nxt[i]];
            if (nxt[nxt[i]]) {
                lst[nxt[nxt[i]]] = i;
            } else {
                tail = i;
            }
            nxt[i] = nxt[nxt[i]];

        } else if (p == r[i] + 1) {
            r[i] += 1;
        } else if (nxt[i] && p == l[nxt[i]] - 1) {
            l[nxt[i]] -= 1;
        } else {
            m += 1;
            l[m] = r[m] = p;
            if (lst[i]) {
                nxt[lst[i]] = m;
            } else {
                head = m;
            }
            lst[m] = lst[i];
            nxt[m] = i;
            lst[i] = m;
        }

        return;
    }

    int p0 = l[i] + r[i] - p;  //对称位置

    m += 1;
    l[m] = p0 + 1;
    r[m] = r[i] + 1;
    if (r[m] > n) r[m] = n;

    lst[m] = i;
    nxt[m] = nxt[i];
    if (nxt[i]) {
        lst[nxt[i]] = m;
    } else {
        tail = m;
    }
    nxt[i] = m;

    l[i] -= 1;
    if (l[i] <= 0) l[i] = 1;
    r[i] = p0 - 1;

    int lp = i, rp = m;
    if (lst[lp] && r[lst[lp]] + 1 == l[lp]) {
        r[lst[lp]] = r[lp];
        lst[nxt[lp]] = lst[lp];
        nxt[lst[lp]] = nxt[lp];
        i = lst[lp];
    }

    if (nxt[rp] && l[nxt[rp]] - 1 == r[rp]) {
        l[nxt[rp]] = l[rp];
        lst[nxt[rp]] = lst[rp];
        nxt[lst[rp]] = nxt[rp];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> s;
    n = strlen(s);
    int ll = 1, rr = 0;
    for (int i = 1; i <= n; ++i) {
        if ('0' == s[i - 1]) {
            if (rr >= ll) {
                m += 1;
                l[m] = ll;
                r[m] = rr;
                lst[m] = m - 1;
                nxt[m - 1] = m;
            }
            ll = i + 1;
            rr = i;
        } else {
            if ('2' == s[i - 1]) {
                que.push_back(i);
            }
            rr += 1;
        }
    }
    if (rr >= ll) {
        m += 1;
        l[m] = ll;
        r[m] = rr;
        lst[m] = m - 1;
        nxt[m - 1] = m;
    }
    // init

    if (m) {
        head = 1;
        tail = m;
    } else {
        cout << s << endl;
        return 0;
    }

    i = head;
    for (int u : que) {
        go(u);
    }

    for (int i = 1; i < min(n + 1, l[head]); ++i) {
        cout << 0;
    }
    cout.flush();
    for (int i = head; i; i = nxt[i]) {
        for (int j = max(1, l[i]); j <= min(n, r[i]); ++j) {
            cout << 1;
        }
        cout.flush();
        if (nxt[i]) {
            for (int j = max(1, r[i] + 1); j < min(n + 1, l[nxt[i]]); ++j) {
                cout << 0;
            }
            cout.flush();
        } else {
            break;
        }
    }
    for (int i = max(1, r[tail] + 1); i <= n; ++i) {
        cout << 0;
    }
    cout.flush();

    return 0;
}

心路历程:
打表找到规律还是挺快的,弄了二十来分钟吧
写链表算上调试大概弄了2h,太爬了
证明目前不会,主要是第一条,从第一条证第二题还是挺简单的
暴力程序这里就不贴了

E. English Restaurant

这应该是个概率dp,状态不行,捋不清,先占坑

Link-Cut Tree

CF上遇到一题需要这个
先学着Splay版本的,后续有机会再学Treap版本的

参考资料
QTREE解法的一些研究

基本

将树剖分,用数据结构维护链
常见的树剖因为维护的是静态树结构,因此可以用线段树
而要求维护动态的结构时,就得用Splay之类的动态数据结构了
对于Splay,很容易考虑区间查询及区间修改(需要能整体统计撤销的)
那么接下来就得考虑如何合理地进行剖分使复杂度正确

核心操作 Access(x)
将 x 到根的路径上全部变成实边,并且丢弃自己的所有儿子
具体步骤即:

  1. 将 x 转至其所在 Splay 的根
  2. 将父节点转至其所在 Splay 的根,随后替换掉其右儿子,即沿虚边将替换掉父节点的实儿子
  3. 断开右子树(其实可以不需要)
  4. 转到1
    这一操作的均摊复杂度是 O(logn)

换根 makeRoot(u)

  1. access(u)
  2. 将 u 的左子树翻转
  3. 断开左子树,连接虚边
  4. 更新信息

判连通 connected(u, v)
access(u) 并获取 Splay中最左节点(即根),对 access(v) 并同样获取最左节点,进行比较,相同则连通

连接 link(u, v)
首先要确保不连通

  1. makeRoot(u)
  2. 从 u 向 v 连一条虚边(v为父亲)

断开 cut(u, v)
首先要确保二者间存在边

  1. makeRoot(v), splay(u)
  2. 若 u 没有向上虚边,则断开 u 的左子树,更新信息
  3. 否则断开 u 向上的虚边
    情况 3 中,即 u 为 v 的虚儿子;情况 2 中 u 为 v 的实儿子

洛谷P3690 【模板】动态树(Link Cut Tree)

#include <iostream>
using namespace std;

const int MAX_N = 1E5 + 100;

class Node {
   public:
    int val = 0, tot = 0;
    bool flip = 0;
    Node *c[2], *p, *pp;

    Node() {
        c[0] = c[1] = 0;
        fix();
    }

    void pushFlip() {
        if (!flip) return;
        flip = 0;
        swap(c[0], c[1]);
        if (c[0]) c[0]->flip ^= 1;
        if (c[1]) c[1]->flip ^= 1;
    }

    void fix() {
        //维护的数据在这里处理
        tot = val;
        if (c[0]) {
            c[0]->p = this;
            tot ^= c[0]->tot;
        }
        if (c[1]) {
            c[1]->p = this;
            tot ^= c[1]->tot;
        }
    }

    int type() { return p ? this == p->c[1] : 2; }

    void rot(int i, int j) {
        bool b = i ^ j;
        Node *x = c[i], *y = 2 == j ? x : x->c[j], *z = b ? y : x;

        if (y->p = p) p->c[type()] = y;
        c[i] = z->c[i ^ 1];
        if (j < 2) {
            x->c[j] = y->c[j ^ 1];
            z->c[j ^ 1] = b ? x : this;
        }
        y->c[i ^ 1] = b ? this : x;

        fix();
        x->fix();
        y->fix();

        swap(pp, y->pp);
    }

    void splay() {
        for (pushFlip(); p;) {
            if (p->p) p->p->pushFlip();
            p->pushFlip();
            pushFlip();

            if (2 == p->type())
                p->rot(type(), 2);
            else
                p->p->rot(p->type(), type());
        }
    }

    Node *first() {
        pushFlip();
        return c[0] ? c[0]->first() : (splay(), this);
    }
};

class LCT {
   public:
    Node node[MAX_N];

    Node *access(Node *u) {
        for (u->splay(); Node *pp = u->pp; u = pp) {
            pp->splay();
            u->pp = 0;

            if (pp->c[1]) {
                pp->c[1]->p = 0;
                pp->c[1]->pp = pp;
            }
            pp->c[1] = u;
            pp->fix();
        }
        return u;
    }

    void makeRoot(Node *u) {
        access(u);
        u->splay();
        if (u->c[0]) {
            u->c[0]->flip ^= 1;
            u->c[0]->p = 0;
            u->c[0]->pp = u;
            u->c[0] = 0;
            u->fix();
        }
    }

    bool connected(Node *u, Node *v) {
        Node *ru = access(u)->first();
        return ru == access(v)->first();
    }

    void link(Node *u, Node *v) {
        if (connected(u, v)) return;
        makeRoot(u);
        u->pp = v;
    }

    void cut(Node *u, Node *v) {
        makeRoot(v);
        u->splay();
        if (v != (u->pp ?: u->c[0])) return;
        if (u->pp) {
            u->pp = 0;
        } else {
            u->c[0] = v->p = 0;
            u->fix();
        }
    }

    //===============

    Node *access(int u) { return access(node + u); }
    void makeRoot(int u) { makeRoot(node + u); }
    bool connected(int u, int v) { return connected(node + u, node + v); }
    void link(int u, int v) { link(node + u, node + v); }
    void cut(int u, int v) { cut(node + u, node + v); }
};

int n, m;
LCT tr;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> tr.node[i].val;
        tr.node[i].tot = tr.node[i].val;
    }

    while (m--) {
        int u, v, opt;
        cin >> opt >> u >> v;
        if (0 == opt) {
            tr.makeRoot(u);
            tr.access(v);
            tr.node[v].splay();
            cout << (tr.node[v].tot ^
                     (tr.node[v].c[1] ? tr.node[v].c[1]->tot : 0))
                 << '\n';
        } else if (1 == opt) {
            tr.link(u, v);
        } else if (2 == opt) {
            tr.cut(u, v);
        } else {
            tr.node[u].splay();
            tr.node[u].tot ^= tr.node[u].val;
            tr.node[u].val = v;
            tr.node[u].tot ^= v;
        }
    }

    return 0;
}

CF1555EDU F. Good Graph

Splay

早就听说SPLAY大名,可以做区间翻转操作
但是查到的都是平衡树相关的东西
因为这个是LCT的前置,所以终于要学了

基本功能

结构

一颗二叉搜索树,需要维护根节点编号与节点个数
每个节点维护父亲、左右儿子编号、节点权值、权值出现次数、子树大小
感觉跟AVL维护的东西差不多

基本操作

splay(伸展):将某个点旋转至根(其实可以旋转至任意父亲处)
push,remove

伸展
其中一个关键的地方在于旋转,应当使用双旋而不是单旋
单旋即将目标节点一直向上旋转
而双旋分六种情况,如下图(图源自OIWIKI)

前两种情况为父亲为根,做一次旋转即可
中间两种情况为,父亲方向与儿子方向相同,父亲先上旋转,儿子再上旋
底下两种情况为,父亲方向与儿子方向不同,儿子上旋两次
显然单旋弄一条链就直接卡没了,而双旋试一下就知道用链至少不会一直保持在最坏情况
严格的均摊复杂度可以由势能法证明是 O(logn)

具体实现起来,可以一次双旋,而不是做两次单旋,能省一些常数
分别画一下这六种情况的前后对应关系

图中红色标出的为断开的位置,观察一下最终连接,可以归纳出几个共通点(下述类型均指其为左儿子还是右儿子)

  1. 最顶端节点(c)断开处将连接首次旋转节点的异侧
  2. 中部的节点(后四种情况的x)连接底部节点(y)的断开处总是连接其儿子的异侧
  3. 最底部节点(后四种情况的y)与其父亲 (x) 类型相异侧,中间两种情况连接中部节点(x),后两种情况连接顶部节点(c)
    同时前两种情况(父亲为根),可以合并到最后两种情况进行处理
  4. (后四种情况)最后剩下的一个断开为首次旋转节点 (z) 与 y 类型相异侧,中间两种情况连接顶部节点(c),后两种情况连接中部节点(x)

这样就是四处断开的位置及其所有可能的连接方式,其中2,4两种是后四种情况独有的,1,3是全部情况共用的
再记得更新父亲的连接,这里用函数fix做,顺便维护想维护的值例如子树大小
代码实现如下

//该函数在最顶端节点处调用
//i指定首层节点的类型,0左,1右
//j指定次层节点的类型,0左,1右,2不存在
void rot(int i, int j) {
    int b = i ^ j;  //确定此次旋转的类型,0同侧,1异侧,当j为2时恒不为0,视作异侧
    //x为首层节点,y为次层节点,z为首次旋转的节点
    Node *x = c[i], *y = j == 2 ? x : x->c[j], *z = b ? y : x;

    if ((y->p = p)) p->c[type()] = y; //不要忘了更新父亲
    c[i] = z->c[i ^ 1];//连接1
    if (j < 2) {
        x->c[j] = y->c[j ^ 1];    //连接2
        z->c[j ^ 1] = b ? x : this;  //连接4
    }
    y->c[i ^ 1] = b ? this : x;  //连接3

    fix();
    x->fix();
    y->fix();
    if (p) p->fix();
} 

void fix() {
    if (c[0]) c[0]->p = this;
    if (c[1]) c[1]->p = this;
}

剩下的就好说了,递归上旋直到为根即完成伸展操作
增加push
寻找目标位置,遇到相等就直接计数+1,遇到空位就新增节点
最后记得splay
删除remove
寻找目标位置,旋到根
若数量多于1,则计数器-1
否则删除根,将左子树的最右节点旋为左子树的根(先断开左子树与根)
再将右子树直接作为新根的右子树
左子树为空直接将右子树顶上来

其他操作

kth(给排名查数),rnk(查排名),求前驱、后继
后三项都可以先插入待查的数,旋到根,查完之后再删除,非常方便

代码(洛谷P6136 【模板】普通平衡树(数据加强版))

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 1E6 + 1E5 + 100;
const int INF = (1 << 30) + 100;

//===========================================io

int read() {
    int ret = 0;
    char c = getchar();
    while ('0' > c || c > '9') c = getchar();
    while ('0' <= c && c <= '9') {
        ret *= 10;
        ret += c - '0';
        c = getchar();
    }
    return ret;
}

void write(int x) {
    static char wbuf[8];
    if (0 == x) putchar('0');
    int sz = 0;
    while (x) {
        wbuf[sz++] = '0' + x % 10;
        x /= 10;
    }
    while (sz) putchar(wbuf[--sz]);
}

//===========================================splay

class Node {  // Splay
   public:
    Node *p = 0, *c[2];

    bool flip = 0;  //可选(区间翻转)
    int val, cnt;   //可选(视维护的值而定)
    int sz;         //可选(kth,rnk需要)

    Node() {}

    Node(int _val) {
        c[0] = c[1] = 0;
        fix();
        val = _val;
        cnt = 1;
        sz = 1;
    }

    void fix() {
        sz = cnt;
        if (c[0]) {
            c[0]->p = this;
            sz += c[0]->sz;
        }
        if (c[1]) {
            c[1]->p = this;
            sz += c[1]->sz;
        }
    }

    void pushFlip() {
        if (!flip) return;
        flip = 0;
        swap(c[0], c[1]);
        if (c[0]) c[0]->flip ^= 1;
        if (c[1]) c[1]->flip ^= 1;
    }

    int type() { return p ? p->c[1] == this : -1; }

    void rot(int i, int j) {
        int b = i ^ j;
        Node *x = c[i], *y = j == 2 ? x : x->c[j], *z = b ? y : x;

        if ((y->p = p)) p->c[type()] = y;
        c[i] = z->c[i ^ 1];
        if (j < 2) {
            x->c[j] = y->c[j ^ 1];
            z->c[j ^ 1] = b ? x : this;
        }
        y->c[i ^ 1] = b ? this : x;

        fix();
        x->fix();
        y->fix();
        if (p) p->fix();
    }

    void splay() {
        for (pushFlip(); p;) {
            if (p->p) p->p->pushFlip();
            p->pushFlip();
            pushFlip();

            int c1 = type(), c2 = p->type();
            if (-1 == c2)
                p->rot(c1, 2);
            else
                p->p->rot(c2, c1);
        }
    }

    Node *first() {
        Node *c = this;
        while (c->c[1]) c = c->c[1];
        return c;
    }
};

class Splay {
   private:
    int n;
    Node node[MAX_N];
    Node *rt;

    //=======================

   public:
    void push(int x) {
        if (!n) {
            node[n++] = Node(x);
            rt = node;
        } else {
            Node *c = rt;
            while (true) {
                if (c->val == x) {
                    c->cnt += 1;
                    break;
                }

                int i = c->val < x;
                if (c->c[i]) {
                    c = c->c[i];
                } else {
                    c->c[i] = node + n;
                    node[n++] = Node(x);
                    c->c[i]->p = c;
                    c = c->c[i];
                    break;
                }
            }
            c->splay();
            rt = c;
        }
    }

    //需确保有数可删
    void remove(int x) {
        Node *c = rt;
        while (true) {
            if (c->val == x) {
                break;
            }
            c = c->c[c->val < x];
        }
        c->splay();
        rt = c;
        if (!--c->cnt) {
            if (c->c[0]) {
                rt = c->c[0]->first();
                c->c[0]->p = 0;
                rt->splay();
                rt->c[1] = c->c[1];
                rt->fix();
            } else {
                rt = c->c[1];
                if (rt) {
                    rt->p = 0;
                } else {
                    n = 0;
                }
            }
        } else {
            --c->sz;
        }
    }

    int rnk(int x) {
        push(x);
        int ret = rt->c[0] ? rt->c[0]->sz : 0;
        remove(x);
        return ret + 1;
    }

    //需确保k不大于总数
    int kth(int k) {
        Node *c = rt;
        while (true) {
            int lsz = c->c[0] ? c->c[0]->sz : 0;
            if (lsz + c->cnt < k) {
                k -= c->cnt + lsz;
                c = c->c[1];
            } else if (lsz < k) {
                c->splay();
                rt = c;
                return c->val;
            } else {
                c = c->c[0];
            }
        }
    }

    int lst(int x) {
        push(x);
        Node *c = rt->c[0];
        while (c->c[1]) c = c->c[1];
        remove(x);
        return c->val;
    }

    int nxt(int x) {
        push(x);
        Node *c = rt->c[1];
        while (c->c[0]) c = c->c[0];
        remove(x);
        return c->val;
    }
};

//===========================================

Splay tr;
int n, m;

int main() {
    n = read();
    m = read();
    while (n--) {
        int x = read();
        tr.push(x);
    }

    int ans = 0, lst = 0;
    while (m--) {
        int opt = read();
        int x = read() ^ lst;
        switch (opt) {
            case 1:
                tr.push(x);
                break;
            case 2:
                tr.remove(x);
                break;
            case 3:
                ans ^= lst = tr.rnk(x);
                break;
            case 4:
                ans ^= lst = tr.kth(x);
                break;
            case 5:
                ans ^= lst = tr.lst(x);
                break;
            case 6:
                ans ^= lst = tr.nxt(x);
                break;
        }
    }
    write(ans);
    putchar('\n');

    return 0;
}

区间翻转

还是基于splay操作,对于翻转 [l,r]
先把 l-1 splay至根
再把 r+1 splay至根的右儿子
翻转根的右儿子的左儿子即可
类似lazytag的做法

代码(洛谷P3391 【模板】文艺平衡树)

#include <iostream>
using namespace std;

const int MAX_N = 1E5 + 100;

int n, m;

class Node {
   public:
    int val, sz;
    bool flip;
    Node *p, *c[2];

    Node() {
        flip = 0;
        p = c[0] = c[1] = 0;
    }

    void pushFlip() {
        if (!flip) return;
        flip = 0;
        swap(c[0], c[1]);
        if (c[0]) c[0]->flip ^= 1;
        if (c[1]) c[1]->flip ^= 1;
    }

    void fix() {
        sz = 1;
        if (c[0]) {
            sz += c[0]->sz;
            c[0]->p = this;
        }
        if (c[1]) {
            sz += c[1]->sz;
            c[1]->p = this;
        }
    }

    int type() { return p ? this == p->c[1] : 2; }

    void rot(int i, int j) {
        int b = i ^ j;
        Node *x = c[i], *y = 2 & j ? x : x->c[j], *z = b ? y : x;

        if (y->p = p) p->c[type()] = y;
        c[i] = z->c[i ^ 1];
        if (j < 2) {
            x->c[j] = y->c[j ^ 1];
            z->c[j ^ 1] = b ? x : this;
        }
        y->c[i ^ 1] = b ? this : x;

        fix();
        x->fix();
        y->fix();
        if (p) p->fix();
    }

    void splay() {
        for (pushFlip(); p;) {
            if (p->p) p->p->pushFlip();
            p->pushFlip();
            pushFlip();

            if (2 & p->type())
                p->rot(type(), 2);
            else
                p->p->rot(p->type(), type());
        }
    }
};

class Splay {
   private:
    int n;
    Node node[MAX_N];
    Node *rt;

    void print(Node *c) {
        c->pushFlip();
        if (c->c[0]) print(c->c[0]);
        if (1 <= c->val && c->val <= n) cout << c->val << ' ';
        if (c->c[1]) print(c->c[1]);
    }

   public:
    void init(int _n) {
        n = _n;
        rt = node;
        node[0].val = 0;
        node[0].sz = n + 2;
        for (int i = 1; i <= n + 1; ++i) {
            node[i].val = i;
            node[i].p = node + i - 1;
            node[i - 1].c[1] = node + i;
            node[i].sz = n + 2 - i;
        }
    }

    Node *find(int k) {
        k += 1;

        Node *c = rt;
        while (true) {
            c->pushFlip();
            int lsz = c->c[0] ? c->c[0]->sz : 0;
            if (lsz + 1 < k) {
                k -= 1 + lsz;
                c = c->c[1];
            } else if (lsz < k) {
                return c;
            } else {
                c = c->c[0];
            }
        }
    }

    void flip(int l, int r) {
        Node *ln = find(l - 1);
        ln->splay();
        rt = ln;

        Node *rn = find(r + 1);
        ln->c[1]->p = 0;
        rn->splay();
        rn->p = ln;
        ln->c[1] = rn;

        rn->c[0]->flip ^= 1;
    }

    void print() { print(rt); }
};

Splay tr;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;

    tr.init(n);
    while (m--) {
        int l, r;
        cin >> l >> r;
        tr.flip(l, r);
    }
    tr.print();

    return 0;
}

Treap

参考资料
http://www.yhzq-blog.cc/fhq-treap%e6%80%bb%e7%bb%93/
实现基本照抄 kactl
感觉有必要,就顺手学一下好了

笛卡尔树

定义 一棵二叉树,节点维护键值对 (key, val),其中 key 满足堆性质而 val 满足二叉树性质
Treap 即为一棵特殊的笛卡尔树

Treap

结构 Treap为一棵笛卡尔树,其中 val 为所维护的值,而 key 为随机赋予的
由随机堆的性质,这棵树的深度为 O(logn) 级别的
维护 容易考虑用传统的旋转来维护,但是可以用分裂与合并操作来替代,其代码更短
需要维护的值具体有:key, val, cnt, l, r

class Node {
 public:
    int a, y, c = 1;    //val, key, cnt
    Node *l = 0, *r = 0;
    Node(int val) : a(val), y(rnd()) {}
    void recalc() { c = cnt(l) + cnt(r) + 1; }
};

其中随机值推荐使用 mt19937,简单测了一下发现比自己写的线性同余还快(rand()可以爬了)

FHQ-Treap

核心操作

分离 Split 将原树中的前 k 大的节点分裂出去
考虑一个递归过程
要从节点 u 的子树中分出 k 个节点
若左子树数量大于等于 k ,则变为从左子树中分出 k 个节点
否则从右子树中分出 k - cnt(l) - 1 个节点,接到当前节点的右侧,右子树剩下的部分就剩下

//first为被分出去的根,second为剩下部分的根
pair<Node*, Node*> split(Node* u, int k) {
    if (!u) return {};
    if (cnt(u->l) >= k) {
        auto pa = split(u->l, k);
        u->l = pa.second;
        u->recalc();
        return {pa.first, u};
    } else {
        auto pa = split(u->r, k - cnt(u->l) - 1);
        u->r = pa.first;
        u->recalc();
        return {u, pa.second};
    }
}

右合并 Merge 将给定的第二棵树合并到第一棵树的右侧
这里的 即为保证前者所有节点的权小于后者的(这里考虑从小到大)
需要注意该操作是不满足交换律的
还是递归处理
要满足BST性质,后者应当放到前者的右侧,或者前者应放到后者的左侧
假如那一侧已经被占了,那就将那一侧与要放的继续合并
再考虑满足堆性质(这里考虑大根堆)

//返回合并后的根
Node* merge(Node* u, Node* v) {
    if (!u) return v;
    if (!v) return u;
    if (u->y > v->y) {
        u->r = merge(u->r, v);
        u->recalc();
        return u;
    } else {
        v->l = merge(u, v->l);
        v->recalc();
        return v;
    }
}

基本操作的拓展

插入 insert 将某棵树插入到另一颗树的第 k + 1 个位置
做法非常简单,先将前 k 个元素拆出来,然后从左至右依次合并即可

Node* insert(Node* u, Node* v, int k) {
    auto pa = split(u, k);
    return merge(merge(pa.first, v), pa.second);
}

BST的操作

查询排名 rnk
按照BST的方法去做就好了

int rnk(Node* u, int val) {
    if (!u) return 0;
    if (u->a < val)
        return cnt(u->l) + 1 + rnd(u->r, val);
    else
        return rnd(u->l, val);
}

排名查元素 kth
可以偷懒,split两次之后merge

int kth(int k) {
    auto pa = split(rt, k);
    auto pb = split(pa.first, k - 1);
    int ret = pb.second->a;
    merge(merge(pb.first, pb.second), pa.second);
    return ret;
}

插入元素 push
结合rnd与insert就变成了push

void push(int val) {
    nodes[n] = Node(val);
    rt = n ? insert(rt, nodes + n, rnk(rt, val)) : nodes;
    n += 1;
}

弹出元素 pop
偷懒,用split和rnk拆出比它小的,然后剩下部分再拆掉第一个

void pop(int val) {
    auto pa = split(rt, rnk(rt, val));
    rt = merge(pa.first, split(pa.second, 1).second);
}

求前驱 pre 与 求后继 suc
偷懒,还是求个rnk然后拆

int pre(int val) {
    int k = rnk(rt, val);
    auto pa = split(rt, k);
    auto pb = split(pa.first, k - 1);
    int ret = pb.second->a;
    rt = merge(merge(pb.first, pb.second), pa.second);
    return ret;
}
int suc(int val) {
    int k = rnk(rt, val + 1);
    auto pa = split(rt, k);
    auto pb = split(pa.second, 1);
    int ret = pb.first->a;
    rt = merge(pa.first, merge(pb.first, pb.second));
    return ret;
}

另外,容易发现,按照上面那么做,就能处理重复元素的情况
结合上述内容,模板题就搞定了

洛谷P6136 【模板】普通平衡树(数据加强版)

#include <iostream>
#include <random>
using namespace std;

const int MAX_N = 1E6 + 1E5 + 100;

mt19937 rnd(114514);

class Treap {
private:
    class Node {
    public:
        int a, y, c = 1;
        Node *l = 0, *r = 0;
        Node(int val = 0) : a(val), y(rnd()) {}
        void recalc() { c = cnt(l) + cnt(r) + 1; }
    };
    //=============

    static int cnt(Node* u) { return u ? u->c : 0; }

    //============

    int n;
    Node* rt;
    Node nodes[MAX_N];

    //============

    pair<Node*, Node*>
    split(Node* u, int k) {
        if (!u) return {};
        if (cnt(u->l) >= k) {
            auto pa = split(u->l, k);
            u->l = pa.second;
            u->recalc();
            return {pa.first, u};
        } else {
            auto pa = split(u->r, k - cnt(u->l) - 1);
            u->r = pa.first;
            u->recalc();
            return {u, pa.second};
        }
    }

    Node* merge(Node* u, Node* v) {
        if (!u) return v;
        if (!v) return u;
        if (u->y > v->y) {
            u->r = merge(u->r, v);
            u->recalc();
            return u;
        } else {
            v->l = merge(u, v->l);
            v->recalc();
            return v;
        }
    }

    Node* insert(Node* u, Node* v, int k) {
        auto pa = split(u, k);
        return merge(merge(pa.first, v), pa.second);
    }

    //=======================

    int rnk(Node* u, int val) {
        if (!u) return 0;
        if (u->a < val)
            return cnt(u->l) + 1 + rnk(u->r, val);
        else
            return rnk(u->l, val);
    }

public:
    int rnk(int val) {
        return rnk(rt, val) + 1;
    }

    int kth(int k) {
        auto pa = split(rt, k);
        auto pb = split(pa.first, k - 1);
        int ret = pb.second->a;
        rt = merge(merge(pb.first, pb.second), pa.second);
        return ret;
    }

    void push(int val) {
        nodes[n] = Node(val);
        rt = n ? insert(rt, nodes + n, rnk(rt, val)) : nodes;
        n += 1;
    }

    void pop(int val) {
        auto pa = split(rt, rnk(rt, val));
        rt = merge(pa.first, split(pa.second, 1).second);
    }

    int pre(int val) {
        int k = rnk(rt, val);
        auto pa = split(rt, k);
        auto pb = split(pa.first, k - 1);
        int ret = pb.second->a;
        rt = merge(merge(pb.first, pb.second), pa.second);
        return ret;
    }

    int suc(int val) {
        int k = rnk(rt, val + 1);
        auto pa = split(rt, k);
        auto pb = split(pa.second, 1);
        int ret = pb.first->a;
        rt = merge(pa.first, merge(pb.first, pb.second));
        return ret;
    }
};

//=========================

int read() {
    int x = 0;
    char c = getchar();
    while ('0' > c || c > '9') c = getchar();
    while ('0' <= c && c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    return x;
}

char wBuf[10];
void write(int x) {
    if (!x) putchar('0');
    int cnt = 0;
    while (x) {
        wBuf[cnt++] = x % 10 + '0';
        x /= 10;
    }
    while (cnt) putchar(wBuf[--cnt]);
}

//=========================

int n, m, lst, ans;
Treap tr;

signed main() {
    n = read(), m = read();
    for (int i = 0; i < n; ++i) {
        int u = read();
        tr.push(u);
    }
    for (int i = 0; i < m; ++i) {
        int opt = read(), x = read() ^ lst;
        switch (opt) {
        case 1:
            tr.push(x);
            break;
        case 2:
            tr.pop(x);
            break;
        case 3:
            ans ^= lst = tr.rnk(x);
            break;
        case 4:
            ans ^= lst = tr.kth(x);
            break;
        case 5:
            ans ^= lst = tr.pre(x);
            break;
        case 6:
            ans ^= lst = tr.suc(x);
            break;
        }
    }
    write(ans);
    putchar('\n');

    return 0;
}

结果看,在偷了不少懒的情况下,平均比splay要稍快
而代码短了很多
其实可以发现,要实现这样的数据结构,关键在于两个基本操作以及 rnk
实际上 rnksplit 可以合并成按照权值进行分裂的版本(以下代码没测过)

//分裂出权值小于 k 的
pair<Node*, Node*> split(Node* u, int k) {
    if (!u) return {};
    if (u->a >= k) {
        auto pa = split(u->l, k);
        u->l = pa.second;
        u->recalc();
        return {pa.first, u};
    } else {
        auto pa = split(u->r, k - cnt(u->l) - 1);
        u->r = pa.first;
        u->recalc();
        return {u, pa.second};
    }
}

这么做的话可以减少一些常数,不过也有缺点

重要拓展

容易发现,数量版本的核心操作是不关心 val 的具体取值的,这一点与 Splay 非常相似
也就是说并不是实际上维护了BST本身,而是在满足 前者的权小于后者 的前提
更进一步地说,这是在维护这个序列本身,可以做一些区间操作
以区间翻转举例

区间翻转 flip
分成三步:提取区间,打标记,合并区间

auto pa = split(rt, r);
auto pb = split(pa.first, l - 1);
//提取的目标区间为 pb.second
pb.second->flip ^= 1;
//打上标记
rt = merge(merge(pb.first, pb.second), pa.second);
//合并区间

标记还需要具体实现,因此需要增加个pushFilp,有事没事下放一下

void Node::pushFlip() {
    if (flip) {
        flip = 0;
        if (l) l->flip ^= 1;
        if (r) r->flip ^= 1;
        swap(l, r);
    }
}

洛谷P3391 【模板】文艺平衡树

#include <iostream>
#include <random>
using namespace std;

const int MAX_N = 1E5 + 100;
mt19937 rnd(114514);

class Treap {
private:
    class Node {
    public:
        int a, k, c = 1;
        bool flip = 0;
        Node *l = 0, *r = 0;
        Node(int _a = 0) : a(_a), k(rnd()) {}
        void recalc() { c = cnt(l) + cnt(r) + 1; }
        void pushFlip() {
            if (flip) {
                flip = 0;
                if (l) l->flip ^= 1;
                if (r) r->flip ^= 1;
                swap(l, r);
            }
        }
    };

    int n;
    Node* rt;
    Node nodes[MAX_N];

    //==============

    static int cnt(Node* u) { return u ? u->c : 0; }

    pair<Node*, Node*> split(Node* u, int k) {
        if (!u) return {};
        u->pushFlip();
        if (cnt(u->l) >= k) {
            auto pa = split(u->l, k);
            u->l = pa.second;
            u->recalc();
            return {pa.first, u};
        } else {
            auto pa = split(u->r, k - cnt(u->l) - 1);
            u->r = pa.first;
            u->recalc();
            return {u, pa.second};
        }
    }

    Node* merge(Node* u, Node* v) {
        if (!u) return v;
        if (!v) return u;
        u->pushFlip();
        v->pushFlip();
        if (u->k < v->k) {
            v->l = merge(u, v->l);
            v->recalc();
            return v;
        } else {
            u->r = merge(u->r, v);
            u->recalc();
            return u;
        }
    }

    void print(Node* u) {
        if (!u) return;
        u->pushFlip();
        print(u->l);
        cout << u->a << ' ';
        print(u->r);
    }

public:
    void init(int _n) {
        n = _n;
        nodes[0] = Node(1);
        rt = nodes;
        for (int i = 1; i < n; ++i) {
            nodes[i] = Node(i + 1);
            rt = merge(rt, nodes + i);
        }
    }

    void flip(int l, int r) {
        auto pa = split(rt, r);
        auto pb = split(pa.first, l - 1);
        pb.second->flip ^= 1;
        rt = merge(merge(pb.first, pb.second), pa.second);
    }

    void print() {
        print(rt);
    }
};

int n, m;
Treap tr;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    tr.init(n);
    while (m--) {
        int l, r;
        cin >> l >> r;
        tr.flip(l, r);
    }
    tr.print();

    return 0;
}

效率差不多,和splay一比又短了

Link-Cut-Tree

既然这玩意能区间翻转了,那也就能做LCT了
(留个坑

wqs二分

概要

这一技巧专门用于解决形式如下的问题

给定若干件物品,从中选出k件,使其价值和最大

其中关键的限定条件为:

  1. 最终价值和为按件加和的形式,即无需关心物品价值具体如何,只要总价值为所选物品的和即可
  2. 在不存在限定条件k的情况下,可以较快得出解(复杂度能再乘log),同时要能顺便求出所取件数
  3. 满足k与其对应最优解的大小g(k)所组成的点(k, g(k))落在一上凸包或下凸包上

在此基础上我们考虑图像(k,g(k)-ck)(可以考虑为对原坐标轴进行变换)
可以看出新的最大值(即切线截距)将落在凸包上与其相切的一点处,此时限定条件下的最优解将化为全局最优解
即直接将所有物品的价值减去c,再直接进行无限定条件的求解,而后比较所求得的k与限定条件,可判断当前解是否满足限定。
不难想到对c进行二分来进行总的求解

细节

上下界按照需求容易确定
比较麻烦的地方在于,可能存在某些点落在凸包的边而非顶点上,即存在一段连续的k,均满足在某个斜率下值最大,这样可能导致无法求出指定的k
解决思路比较简单,在进行二分求解时,首先确保在选取最大值时优先选更多的物品,随后将收敛条件设为斜率的收敛,只要确保存在符合要求的k,则斜率与变换后最大值的收敛结果必然正确

洛谷P1484 种树

n \leq 10^5 个坑可以种树,相邻不能种,每个坑都有价值(可为负),求至多种k \leq \frac{n}{2} 棵树时的最大价值

做法
显然 O(n) DP可解全局最大值
同时随着选取树的数量的增多,显然最大价值的增量是单调减的,套用wqs二分即可
枚举斜率的时候需要考虑精度问题
AC代码

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

#define int long long
const int MAX_N = 5E5 + 100;
const double INF = 5E11 + 100;
const double eps = 1E-8;

int n, k;
int w[MAX_N];
double dp[MAX_N][2], dpK[MAX_N][2];  //考虑了前k棵树,前一棵是否选了

int curK;
double curGk;
void go(double c) {
    dpK[0][0] = dpK[0][1] = 0;
    dp[0][0] = 0;
    dp[0][1] = -INF;
    for (int i = 1; i <= n; ++i) {
        if (dp[i - 1][0] > dp[i - 1][1]) {
            dp[i][0] = dp[i - 1][0];
            dpK[i][0] = dpK[i - 1][0];
        } else if (dp[i - 1][0] < dp[i - 1][1]) {
            dp[i][0] = dp[i - 1][1];
            dpK[i][0] = dpK[i - 1][1];
        } else if (dpK[i - 1][0] > dpK[i - 1][1]) {
            dp[i][0] = dp[i - 1][0];
            dpK[i][0] = dpK[i - 1][0];
        } else {
            dp[i][0] = dp[i - 1][1];
            dpK[i][0] = dpK[i - 1][1];
        }

        dp[i][1] = dp[i - 1][0] + w[i] - c;
        dpK[i][1] = dpK[i - 1][0] + 1;
    }

    if (dp[n][1] > dp[n][0]) {
        curGk = dp[n][1];
        curK = dpK[n][1];
    } else if (dp[n][1] < dp[n][0]) {
        curGk = dp[n][0];
        curK = dpK[n][0];
    } else if (dpK[n][0] > dpK[n][1]) {
        curGk = dp[n][0];
        curK = dpK[n][0];
    } else {
        curGk = dp[n][1];
        curK = dpK[n][1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }

    double l = 0, r = INF;
    while (fabs(r - l) > eps) {
        double mid = (l + r) / 2;
        go(mid);
        if (curK < k) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << fixed << setprecision(0) << curGk + l * k << endl;

    return 0;
}

KMP & exKMP

其实就考虑计算:后缀函数(\pi) 和 Z函数
后缀函数的定义是一个串的最长公共前真后缀长度
Z函数的定义是一个串以某一位开始的后缀与原串的最长公共前缀长

KMP

O(n) 计算 后缀函数
O(n^2) 的算法很容易考虑,枚举每个可能的公共前缀开头向后匹配更新即可
考虑修改一下这一过程

假定已计算出了前 k 位的后缀函数,现考虑第 k + 1 位的
k + 1 位将在原有某个后缀的基础上增加一位,这一后缀必然是包含在第 k 位的最长公共前后缀内的
所以首先考虑在第 k 位的最长公共前后缀基础上添上一位,即尝试匹配 S_{k + 1}S_{\pi(k) + 1}
当失配时即继续考虑更短的公共前后缀,那显然继续考虑的就是第 \pi(k) 位的最长公共前后缀基础上添加一位(其实也就是第 k 位稍短一些的最长公共前后缀)
依次这样迭代下去直到第一位

这个过程复杂度为 O(n) 不那么显然,需要分析一下
其实也就是看总的匹配需求次数,好吧其实挺显然的
因为每次成功的匹配至多使后续可能的失配次数+1,而出现失配后会使后续可能的失配次数变少
所以总的匹配次数至多为 2n

字符串匹配

后缀函数最常见的应用就是做字符串匹配了(还有各种简单字符串题)
考虑正在匹配模式串的第 j 位,原串的第 i
若失配,由于模式串的前 j - 1 位均匹配过了,则模式串的前 \pi(j - 1) 还是匹配的,将 j 跳转过去就行了
若匹配,则考虑下一位,i,j 均后移一位
特别的,有成功匹配处,则有 i 指向模式串的后一位,可作为答案拿出,并视作失配继续进行下去直到匹配串走完

找个板子题做做

洛谷 P3375 【模板】KMP字符串匹配

#include <cstring>
#include <iostream>

using namespace std;

const int MAX_N = 1E6 + 100;

int n, m;
char a[MAX_N], b[MAX_N];
int pi[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin >> (a + 1);
    cin >> (b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    // init

    pi[0] = -1;
    for (int i = 1; i <= m; ++i) {
        int j = pi[i - 1];
        while (j >= 0 && b[j + 1] != b[i]) j = pi[j];
        pi[i] = j + 1;
    }

    for (int i = 1, j = 1; i <= n; ++i, ++j) {
        while (j && a[i] != b[j]) {
            j = pi[j - 1] + 1;
        }
        if (j == m) {
            cout << i - m + 1 << '\n';
        }
    }

    for (int i = 1; i <= m; ++i) {
        cout << pi[i] << ' ';
    }
    cout << endl;

    return 0;
}

Z Algorithm

O(n) 计算 Z函数
O(n^2) 的算法很容易考虑,暴力向后直到失配即可
考虑能否模仿一下kmp的过程,利用原先匹配的结果

假定已经计算出了前 k 位的Z函数,考虑第 k + 1 位的Z函数
首先考虑最长的可能,去掉第 k 位的那个字符,等同于去掉第 1 位的那个字符
也就是 Z(k + 1) 至少有 min(Z(k) - 1, Z(1)) (下标从 0 开始记)
可以从 min(Z(k) - 1, Z(1)) + 1 开始暴力匹配
但是这一优化显然不够,还是有可能会多次匹配同一字符

容易想到可以把 1 扩展到任意的 x,有
Z(k + x) \geq min\{Z(k) - x, Z(x)\}
且若 Z(x) < Z(k) - x,有 S_{Z(x)} \neq S_{x + Z(x)} = S_{k + x + Z(x)},即有 Z(k + x) = Z(x)
故不妨每次从使 k + Z(k) - 1 最大的一个 k 处考虑
Z(x) < Z(k) - x 时可以 O(1) 计算
否则直接向后暴力
这样每个字符显然只被匹配一次,很显然是 O(n)

计算模式串与匹配串每个后缀的LCP

因为当求得的LCP为模式串长时即为找到了匹配,故字符串匹配为该问题的一个子集
所以该算法也称为扩展KMP

考虑匹配过程中对匹配串最远访问到了 k + lcp(k) - 1
即从 k 开始匹配了 lcp(k)
则有 lcp(k + x) \geq min\{lcp(k) - x, Z(x)\}
类似算Z数组的时候弄弄就好了

有两道题可以一做

P5410 【模板】扩展 KMP(Z 函数)

#include <cstring>
#include <iostream>

using namespace std;

using LL = long long;
const int MAX_N = 2E7 + 100;

int n, m;
int z[MAX_N], p[MAX_N];
char a[MAX_N], b[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin >> a;
    n = strlen(a);
    cin >> b;
    m = strlen(b);

    // z[0] = 0;
    for (int i = 1, k = 0; i < m; ++i) {
        int x = i - k;
        if (z[x] < z[k] - x) {
            z[i] = z[x];
        } else {
            z[i] = max(0, z[k] - x);
            while (b[z[i]] == b[i + z[i]]) z[i] += 1;
            if (k + z[k] < i + z[i]) k = i;
        }
    }
    LL ans = m + 1;
    for (int i = 1; i < m; ++i) {
        ans ^= (i + 1ll) * (z[i] + 1);
    }
    cout << ans << endl;

    for (int i = 0, k = 0; i < n; ++i) {
        int x = i - k;
        if (z[x] < p[k] - x) {
            p[i] = z[x];
        } else {
            p[i] = max(0, p[k] - x);
            while (i + p[i] < n && b[p[i]] == a[i + p[i]]) p[i] += 1;
            if (k + p[k] < i + p[i]) k = i;
        }
    }
    ans = 0;
    for (int i = 0; i < n; ++i) {
        ans ^= (i + 1ll) * (p[i] + 1);
    }
    cout << ans << endl;

    return 0;
}

Codeforces Round #741 (Div. 2) E. Rescue Niwen!

题意

求一个字符串的所有子串的“最长上升子序列”长度,其中子串先按起始下标顺序,再按终止下标倒序排序排列,子串大小即按字符串比较来排列。
如abac,生成的序列为 a ab aba abac b ba bac a ac c
数据范围
多组数据,卡log
思路
可以很简单的构造 O(n^3) 的dp
因为子串的排列方式,可以看出整个序列可以被划分为 n 段单调增的部分,显然,如果要取一段,那么必然从某一位开始取完剩下的这段
那么将状态设为 dp[i],取了第 i 组的某一个后缀后,最长上升子序列的长度,转移方程为
dp[j] = Max\{dp[i] + n - i + 1 - f(i, j)\}
其中 f(i, j)s[i..n],s[j..n] 的最长公共前缀长度,且有 s[i + f(i, j)] > s[j + f(i, j)]
暴力求最长公共前缀,是 O(n^3) 的,也就是现有瓶颈
要考虑 O(n^2) 求出这个东西
显然,可以裸套Z Algorithm
但是其实这玩意非常愚蠢,转移如下
s[i] = s[j], f(i, j) = f(i + 1, j + 1) + 1
否则 f(i, j) = 0
AC代码(Z函数版本)

#include <cstring>
#include <iostream>
using namespace std;

const int MAX_N = 5000 + 7;

int T, n;
char s[MAX_N];
int z[MAX_N][MAX_N];
int dp[MAX_N];

void getZ(int n, char s[], int z[]) {
    z[0] = 0;
    for (int i = 1, k = 0; i < n; ++i) {
        int x = i - k;
        z[i] = 0;
        if (z[x] < z[k] - x) {
            z[i] = z[x];
        } else {
            z[i] = max(0, z[k] - x);
            while (s[z[i]] == s[i + z[i]]) z[i] += 1;
            if (k + z[k] < i + z[i]) k = i;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n;
        cin >> (s + 1);
        for (int i = 1; i <= n; ++i) {
            dp[i] = 0;
            getZ(n - i + 1, s + i, z[i] + i);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (s[i + z[j][i]] > s[j + z[j][i]]) {
                    dp[i] = max(dp[i], dp[j] + n - i + 1 - z[j][i]);
                }
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }

    return 0;
}