2022-9-23总结

归并

考虑用 fhq-treap 维护数列。

设合并的时候数列 $a$ 的第一个数为 $x$，数列 $b$ 的第一个数为 $y$ 。

如果 $x < y$ ，就将数列 $a$ 前面所有小于 $y$ 的数合并到新序列里，否则就将数列 $b$ 前面所有小于 $x$ 的数合并到新序列里。

每次合并的时间复杂度是 $O(段数* \log n)$ 的。

但是每次合并的时候数列的前缀最大值会越来越小，也就是整个数列越来越接近有序。

但是总体的时间复杂度我不会证，直接 skip 罢。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <random>
using namespace std;
 
const int N = 1e6+10;
 
namespace fhq_treap {
    struct node {
        int ls, rs;
        int siz, key, val;
        int max;
    } a[N];
    random_device seed;
    mt19937 random(seed());
 
    int root, node_cnt;
 
    #define ls(i) a[i].ls
    #define rs(i) a[i].rs
    int newnode(int val)
    {
        int x = ++node_cnt;
        a[x].ls = a[x].rs = 0;
        a[x].siz = 1;
        a[x].key = random();
        a[x].val = a[x].max = val;
        return x;
    }
    void pushup(int i)
    {
        a[i].siz = 1 + a[ls(i)].siz + a[rs(i)].siz;
        a[i].max = max({a[ls(i)].max, a[rs(i)].max, a[i].val});
    }
    void split(int p, int k, int &x, int &y)
    {
        if(!p) return void(x = y = 0);
        if(a[ls(p)].siz+1 <= k)
            x = p, split(rs(p), k-a[ls(p)].siz-1, rs(x), y);
        else
            y = p, split(ls(p), k, x, ls(y));
        pushup(p);
    }
    void split_val(int p,int k,int &x,int &y)
    {
        if(!p) return void(x = y = 0);
        if(max(a[ls(p)].max, a[p].val) <= k)
            x = p, split_val(rs(p), k, rs(x), y);
        else
            y = p, split_val(ls(p), k, x, ls(y));
        pushup(p);
    }
    int merge(int x, int y)
    {
        if(!x or !y) return x|y;
        if(a[x].key < a[y].key)
        {
            rs(x) = merge(rs(x), y);
            pushup(x); return x;
        }
        else
        {
            ls(y) = merge(x, ls(y));
            pushup(y); return y;
        }
    }
    int getval(int &rt, int k)
    {
        int x, y, z;
        split(rt, k, y, z);
        split(y, k-1, x, y);
        int ans = a[y].val;
        rt = merge(merge(x, y), z);
        return ans;
    }
}
using namespace fhq_treap;
 
int n, m;
 
void merge(int l, int m, int r);
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        int a; scanf("%d", &a);
        root = merge(root, newnode(a));
    }
    int opt, l, k, r;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d", &opt);
        if(opt == 1)
        {
            scanf("%d%d%d", &l, &k, &r);
            merge(l, k, r);
        }
        else
        {
            scanf("%d", &l);
            printf("%d\n", getval(root, l));
        }
    }
}
 
void merge(int l, int m, int r)
{
    int a, b, c, d, i, tmp = 0;
    split(root, r, root, d);
    split(root, m, root, c);
    split(root, l-1, a, b);
    while(b and c)
    {
        int valb = getval(b, 1);
        int valc = getval(c, 1);
        if(valb < valc)
        {
            split_val(b, valc, i, b);
            tmp = merge(tmp, i);
        }
        else
        {
            split_val(c, valb, i, c);
            tmp = merge(tmp, i);
        }
    }
    if(b) tmp = merge(tmp, b);
    if(c) tmp = merge(tmp, c);
    root = merge(merge(a, tmp), d);
}

Cigar Box

原题ARC112

考虑一个合法的操作序列，一个数可能被操作过很多次，但实际有用的只有最后一次，我们定义一个数的最后一次操作为一个关键操作。

设 $f(i,l,r()$ 为进行了 $i$ 次操作，其中有 $l$ 次是放到左边的关键操作， $r$ 次是放到右边的关键操作的方案数，于是我们就有了一个 DP:

$$f(i,l,r) = f(i-1,l,r)*(l+r) + f(i-1,l-1,r) + f(i-1,l,r-1)$$

但是这是一个 $O(mn^2)$ 的 DP。

我们观察发现，单独记录 $l,r$ 没有什么太大作用，所以我们可以把这两维压成一维: $f(i,j)$ 表示进行了 $i$ 次操作，有 $j$ 次是关键操作的方案数。

$$f(i,j) = f(i-1,j-1) + f(i-1,j)*2j$$

统计最终答案时，我们可以枚举 $i,j$ 表示下标在 $[i,j]$ 之间的数没有进行过任何关键操作，如果目标序列中 $[i,j]$ 之间的数是递增的，那么这就是一种合法方案(因为原序列是递增的，没有被操作过的数相对大小不变)，此方案贡献为 $f(m,i-1+n-j)*\binom{i-1+n-j}{i-1}$

我们还少考虑一种情况：所有数都被操作过；这种情况直接加上就行了。贡献为 $\sum\limits_{i=0}^{n} f(m,n)*\binom{n}{i}$

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

typedef long long ll;
const int N = 3005;
const int P = 998244353;

int n, m;
int a[N];
ll f[N][N];
ll fact[N], finv[N];

void prework(int n);
ll qpow(ll a, ll b);
ll C(int n, int m);

int main()
{
    cin >> n >> m; prework(n);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    f[0][0] = 1;
    for(int i = 1; i <= m; i++)
        for(int j = 0; j <= n; j++)
        {
            if(j) (f[i][j] += f[i-1][j-1]) %= P;
            (f[i][j] += f[i-1][j]*j*2%P) %= P;
        }
    
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
        {
            if(j != i and a[j-1] > a[j]) break;
            (ans += f[m][i-1+n-j] * C(i-1+n-j,i-1)%P) %= P;
        }
    
    for(int i = 0; i <= n; i++)
        (ans += f[m][n] * C(n,i)%P) %= P;
    
    cout << ans << "\n";
}

ll C(int n, int m)
{
    if(n < m or n < 0 or m < 0) return 0;
    return fact[n] * finv[m]%P * finv[n-m]%P;
}
void prework(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
    finv[n] = qpow(fact[n], P-2);
    for(int i = n-1; i >= 0; i--)
        finv[i] = finv[i+1]*(i+1)%P;
}
ll qpow(ll a, ll b)
{
    ll ans = 1; a %= P;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

Wine Thief

ARC120F

直接算显然没法算，于是我们考虑计算每个数的贡献，即 $a_i$ 乘以包含 $a_i$ 的合法的方案数。

设 $G(n,k,i)$ 表示 $n$ 个数中选 $k$ 个， 必须选第 $i$ 个数的合法方案数，所以答案就是:

$$\sum _{i=1}^{n} a_i*G(n,k,i)$$

但是 $G(n,k,i)$ 比较难求，暴力求的话只能枚举这个数前面后面选了多少个，如果能用其他的 $G$ 值求的话会比较方便。

为了不枚举这个数前面后面选了多少个，我们可以将序列连接成环来考虑。

把序列连接成环后只多了一个限制： $a_1$ 和 $a_n$ 不能同时选。

先把 $G(n,k,i)$ 的定义放到环上变成 $G'(n,k,i)$，因为环是旋转同构的，所以对于任意的 $i$ ，他们的 $G'(n,k,i)$ 都相同。

设 $f(n,k)$ 为在一个长度为 $n$ 的序列中，选出 $k$ 个数的方案数，考虑把这 $k$ 个数插入剩下的 $n-k$ 个数之间的空隙中，所以 $f(n,k) = C_{n-k+1}^{n}$ 。

设 $F(n,k) = G'(n,k,i)$ ，首先有 $F(n,k)=[k=1], n<3$ ，否则任意选一个数，环就会被这个数和它旁边的两个数断开，所以 $F(n,k)=f(n-3,k-1), n>3$ 。

所以

$$F(n,k) = \begin{cases} [k=1], & n < 3 \\ f(n-3,k-1), & n \ge 3 \end{cases}$$

但是环上还有一个 $a_1$ 和 $a_n$ 不能同时选的限制，考虑把这个限制去掉，我们只需要加上强制同时选 $a_1$ 和 $a_n$ 的情况就可以了。

如果强制选上 $a_1$ 和 $a_n$ ，那么中间的 $n-4$ 个点就又构成一个子问题，可以递归解决：

$$G(n,k,i) = \begin{cases} 0 & ,i \le 0 \\ F(n,k) + f(n-4,k-2) & ,i=1 \\ F(n,k) + G(n-4,k-2,i-1) & ,i>1 \\ G(n,k,n-i+1) & ,i > \lceil \frac{n}{2} \rceil \end{cases}$$

如果每个 $G(n,k,i)$ 直接递归的话是 $O(n^2)$ 的，考虑展开每个 $G(n,k,i)$ 的递归:

$$G(n,k,i) = F(n,k)+F(n-4,k-2)+ \cdots + G( n- \lfloor \frac{i}{2} \rfloor *4, k- \lfloor \frac{i}{2} \rfloor *2, i \bmod 2 )$$

对于每个 $i$，前面所有的 $F$ 项都是相同的，可以直接预处理 $F$ 的前缀和，然后就可以 $O(1)$ 算 $G$ 值了。

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

typedef long long ll;
const int N = 3e5+10;
const int P = 998244353;

int n, k, d;
int a[N];
ll fact[N], finv[N];
ll pre[N];

void prework();
ll F(int n, int k);
ll f(int n, int k);
ll C(int n, int m);
ll qpow(ll a, ll b);
ll G(int n, int k, int i);

int main()
{
    cin >> n >> k >> d;
    prework(); ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int a; cin >> a;
        (ans += a*G(n,k,i)%P) %= P;
    }
    cout << ans << "\n";
}

void prework()
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
    
    finv[n] = qpow(fact[n], P-2);
    for(int i = n-1; i >= 0; i--)
        finv[i] = finv[i+1]*(i+1)%P;
    
    for(int i = 0; i < n; i++)
        pre[i+1] = (pre[i] + F(n-i*4, k-i*2))%P;
    
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        (ans += a[i]*G(n, k, i)%P) %= P;
}

ll G(int n, int k, int i)
{
    if(i <= 0) return 0;
    if(i == 1) return f(n-2, k-1);
    if(i > (n+1)/2) return G(n, k, n-i+1);
    return (pre[i/2] + G(n-(i/2)*4, k-(i/2)*2, i%2))%P;
}
ll F(int n, int k)
{
    if(n < 3) return k == 1;
    else return f(n-3, k-1);
}
ll f(int n, int k)
{
    return C(n-k+1, k);
}
ll C(int n, int m)
{
    if(n < m or n < 0 or m < 0) return 0;
    return fact[n]%P * finv[m]%P * finv[n-m]%P;
}
ll qpow(ll a, ll b)
{
    ll ans = 1; a %= P;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}