CF1316 F - Battalion Strength

发表于 | 阅读数

很好的一道题，有概率从$a$数组中取出子序列。

将子序列排序，这个子序列的权值就是=$\sum_{i=1}^{n-1}a[i]*a[i+1]$

求期望权值。

先将$a$排序
对于一对$(i,j)$贡献=$\sum a_ia_j2^{n-(j-i+1)}$

没有查询的做法只需要

预处理前缀和就好了。

可以看到比$j$小的$(a_i*2^{i-1})$会对$j$产生影响。

设置一个线段树

  • $co=num[l,r]$
  • $lval=\sum_i^{co_{ls}}(a_i*2^{i-1})$
  • $rval=\sum_i^{co_{rs}}(a_i*2^{-j})$
  • $val=\sum_{i<j} (a_i2^{i-1})(a_j2^{-j})$

假设左右已经记录好$lval,rval,val,co$

  • 考虑$val$,左右两端都已经将自己的$val$，即$j>i$,每个的贡献。那么合并的时候还差右儿子中的数对左儿子中的的贡献。$val=val[ls]+val[rs]+lvar[ls]rval[rs]2^{-co[ls]}$
  • $lval$和$rval$的更新注意的是右儿子会发生的值会$*2^{co[ls]}$或$2^{-co[ls]}$

然后这道题线段树其实在维护一个区间，所有需要先把所有值读入，排好序确定之间的关系。查询的时候只需要把对于在线段树上维护那个区间的点删除或者修改即可

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
#define ls pos << 1
#define rs pos << 1 | 1
typedef long long ll;
const int N = 6e5 + 10;
const int mod = 1e9 + 7;
int qpow(int a, int b, int mo)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        b >>= 1;
    }
    return res;
}
struct seg
{
    int lval, rval, val;
    int co;
} tree[N << 2];
int pow2[N], inv2[N];
void pushup(int pos)
{
    tree[pos].val = (tree[ls].val + tree[rs].val) % mod + 1ll * tree[ls].lval * tree[rs].rval % mod * inv2[tree[ls].co] % mod;
    tree[pos].val %= mod;
    tree[pos].lval = tree[ls].lval + 1ll * tree[rs].lval * pow2[tree[ls].co] % mod;
    tree[pos].lval %= mod;
    tree[pos].rval = tree[ls].rval + 1ll * tree[rs].rval * inv2[tree[ls].co] % mod;
    tree[pos].rval %= mod;
    tree[pos].co = tree[ls].co + tree[rs].co;
}
void update(int pos, int x, int w, int l, int r)
{
    if (l == r)
    {
        if (w < 0)
        {
            tree[pos].val = 0;
            tree[pos].co = 0;
            tree[pos].rval = 0;
            tree[pos].lval = 0;
        }
        else
        {
            tree[pos].val = 0;
            tree[pos].co = 1;
            tree[pos].rval = 1ll * w * inv2[1] % mod;
            tree[pos].lval = w;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(pos << 1, x, w, l, mid);
    else
        update(pos << 1 | 1, x, w, mid + 1, r);
    pushup(pos);
}
struct node
{
    int v, id, pos;
} a[N], ask[N];
bool cmp(node d, node e)
{
    return d.v < e.v;
}
int n, p[N];
int res, q;
int main()
{
    int in2 = qpow(2, mod - 2, mod);
    pow2[0] = 1;
    inv2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        pow2[i] = 1ll * pow2[i - 1] * 2 % mod;
        inv2[i] = 1ll * inv2[i - 1] * in2 % mod;
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i].v), a[i].id = i;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        scanf("%d%d", &a[i + n].pos, &a[i + n].v), a[i + n].id = i + n;
        ask[i].pos = a[i + n].pos;
        ask[i].v = a[i + n].v;
    }

    sort(a + 1, a + 1 + n + q, cmp);
    for (int i = 1; i <= n + q; i++)
    {
        if (a[i].id <= n)
            update(1, i, a[i].v, 1, n + q);
        p[a[i].id] = i;
    }
    printf("%d\n", tree[1].val);
    for (int i = 1; i <= q; i++)
    {
        int k1 = p[ask[i].pos];
        int k2 = p[i + n];
        update(1, k1, -a[k1].v, 1, q + n);
        update(1, p[i + n], a[k2].v, 1, n + q);
        p[ask[i].pos] = k2;
        printf("%d\n", tree[1].val);
    }
}