2022-10-26总结

Infinite Operation

Description

给出 $n$ 和一个长度为 $n$ 的数列 $a_{1 \dots n}$。

有 $q$ 次修改，每次给出两个数 $p$、$v$，表示将 $a_p$ 修改为 $v$。修改会改变 $a$，对以后的答案产生影响。

在每一次修改后，求出下面问题的答案：

你可以操作这个序列任意多次。下面的 $a$ 与 $x$ 均为实数。

每次选择两个 $[1,n]$ 内的正整数 $i$、$j$ 满足 $a_i \le a_j$。然后选择一个 $0 \le x \le \frac{a_j-a_i}{2}$。

使 $a_i=a_i+x, a_j=a_j-x$，同时得到 $x$ 的分数。

求若干次操作后，你能得到的得分的最大值，在模 $998244353$ 意义下的值。可以证明这个最大值是存在的且为有理数。

问题中进行的操作不会真的改变 $a$ 的值，这些操作将在这次询问结束后被撤销。而进行的 $q$ 次修改会改变 $a$ 的值并保留下来，影响之后的答案。

Input

输入的第一行包含两个数 $n$、$q$，含义如上。

输入的第二行包含 $n$ 个数，第 $i$ 个表示 $a_i$，含义如上。

接下来 $q$ 行，其中第 $i$ 行包含两个数 $p_i$、$v_i$，表示一次修改。

Output

输出应包含 $q$ 行，第 $i$ 行包含一个数，表示你对第 $i$ 次修改后的 $a$ 求出的答案在模 $998244353$ 意义下的值。

Hint

$2 \le n \le 3 \times 10^5, 1 \le a_i,v_i \le 10^9, 1 \le p_i \le n$。

Solution

设 $S = \sum\limits _{i=1}^n \sum\limits _{j=i+1}^n |a_i-a_j|$，显然得分最大值不大于 $\frac{S}{2}$，因为每次操作会将 $S$ 减去至少 $2x$，然后将得分加上 $x$，下面给出一组操作方式使得得分达到 $\frac{s}{2}$。

考虑每次操作会将 $a_i,a_j$ 靠近它们的平均数，如果存在一个 $a_k$ 满足 $a_i \le a_k \le a_j$ ，那么这次操作后 $S$ 的减少量会大于 $2x$，如果不存在这样的 $a_k$ 那么 $S$ 的减少量就等于 $2x$。

所以我们每次选择两个排序后相邻的数操作即可使得分达到 $\frac{s}{2}$。

数据结构维护一下 $S$ 就行。

#include <cstdio>
#include <iostream>
using namespace std;
 
typedef long long ll;
const int N = 3e5+10;
const int P = 998244353;
const int inv2 = (P+1)/2;
 
namespace segtree {
    struct node {
        int ls, rs;
        ll cnt, sum;
    } t[N*32];
    int lim = 1e9, node_cnt, root;
     
    void add(int pos, int val, int &i = root, int l = 1, int r = lim);
    ll qsum(int ql, int qr, int i = root, int l = 1, int r = lim);
    ll qcnt(int ql, int qr, int i = root, int l = 1, int r = lim);
}
using namespace segtree;
 
int n, q;
int a[N];
ll ans;
 
void modify(int val, int t);
 
int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        modify(a[i], 1);
    }
    for(int i = 1; i <= q; i++)
    {
        int p, v; cin >> p >> v;
        modify(a[p], -1);
        modify(a[p]=v, 1);
        cout << ans%P * inv2%P << "\n";
    }
}
 
void modify(int val, int t)
{
    (ans += t * (qcnt(1, val-1)*val%P - qsum(1, val-1)) % P) %= P;
    (ans += t * (qsum(val+1, lim) - qcnt(val+1, lim)*val%P) % P) %= P;
    ans = (ans+P)%P;
    segtree::add(val, t);
}
 
namespace segtree {
    #define ls(i) t[i].ls
    #define rs(i) t[i].rs
    #define lmid ((l+r)>>1)
    #define rmid ((l+r+2)>>1)
    void add(int pos, int val, int &i, int l, int r)
    {
        if(!i) i = ++node_cnt;
        t[i].cnt += val;
        t[i].sum += val*pos;
        t[i].sum = (t[i].sum%P+P)%P;
        if(l == r) return void();
        if(pos <= lmid) add(pos, val, ls(i), l, lmid);
        if(pos >= rmid) add(pos, val, rs(i), rmid, r);
    }
    ll qsum(int ql, int qr, int i, int l, int r)
    {
        ll ans = 0;
        if(!i or (ql <= l and r <= qr)) return t[i].sum;
        if(ql <= lmid) ans += qsum(ql, qr, ls(i), l, lmid);
        if(qr >= rmid) ans += qsum(ql, qr, rs(i), rmid, r);
        return ans;
    }
    ll qcnt(int ql, int qr, int i, int l, int r)
    {
        ll ans = 0;
        if(!i or (ql <= l and r <= qr)) return t[i].cnt;
        if(ql <= lmid) ans += qcnt(ql, qr, ls(i), l, lmid);
        if(qr >= rmid) ans += qcnt(ql, qr, rs(i), rmid, r);
        return ans;
    }
}

Random IS

Description

给一个长度为 $N$ 的排列 $A$。

现在你要在序列上选一些数。

当前局面下，一个数可选当且仅当选完该数后已选的数构成的子序列单调递增。

若有可选的数，等概率选出一个，否则结束。

问期望选出多少个数。

Input

$N$

$A_1, A_2, \cdots, A_N$

Output

答案，对 $10^9+7$ 取模。

Hint

$1 \le N \le 2000$。

$1 \le A_i \le 2000$。

Solution

因为选数的顺序不固定，所以可以进行一个区间 DP 的做。

设 $F(l,r)$ 表示选了 $a_l,a_r$，$(l,r)$ 中期望选多少个。

设 $C = \sum\limits _{l<k<r, a_l<a_k<a_r} 1$

$F(l,r) = (\sum\limits_{l<k<r, a_l<a_k<a_r} F(l,k)+F(k,r))/C + 1$

直接暴力是 $O(n^3)$ 的，可以改变区间 DP 的枚举顺序，然后就可以树状数组优化成 $O(n^2 \log n)$ 。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
typedef long long ll;
 
const int N = 2005;
const int P = 1e9+7;
 
struct bit_array {
    ll a[N];
    #define lowbit(i) (i&-i)
    void clear() { memset(a, 0, sizeof(a)); }
    void add(int pos, int val)
    {
        for(pos++; pos < N; pos += lowbit(pos))
            (a[pos] += val) %= P;
    }
    ll query(int pos)
    {
        ll ans = 0;
        for(pos++; pos >= 1; pos -= lowbit(pos))
            (ans += a[pos]) %= P;
        return ans;
    }
    ll query(int ql, int qr)
    {
        return (query(qr) - query(ql-1) + P) % P;
    }
} tl[N], tr, t;
 
int n;
int a[N];
ll f[N][N];
 
ll qpow(ll a, ll b);
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    a[n+1] = n+1;
    for(int i = 0; i <= n+1; i++)
        f[i][i] = 1;
    for(int r = 1; r <= n+1; r++)
    {
        t.clear(); tr.clear();
        for(int l = r-1; l >= 0; l--)
        {
            int cnt = t.query(a[l]+1, a[r]-1);
            f[l][r] += tl[l].query(a[l]+1, a[r]-1);
            f[l][r] += tr.query(a[l]+1, a[r]-1);
             
            if(cnt) f[l][r] = (f[l][r]*qpow(cnt, P-2)%P + 1) % P;
            t.add(a[l], 1);
            tl[l].add(a[r], f[l][r]);
            tr.add(a[l], f[l][r]);
        }
    }
    cout << f[0][n+1] << "\n";
}
 
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}