JZOJ 6386 C

发表于 | 分类于 |

由题意可得方程 \(\sum\limits_{i=1}^m\frac{w_i}{S}|i-x|=x\)，其中 \(x\) 表示答案，\(S = \sum\limits_{i=1}^m w_i\)。
（其实我也不知道是怎么得的）

设 \(F(x) = \sum\limits_{i=1}^m|i-x|\cdot w_i-S\cdot x\)，问题即求 \(F\) 的零点。
注意到其中有绝对值，不好直接求。
但是由于 \(i\) 均为整数，故若能求得答案的整数部分即可去绝对值。

又注意到 \(F\) 单调递减，因为当 \(x\) 增大时，前一项增大的量必然不如后一项减小的量。
故可以二分求得最大的使得 \(F(x)\ge0\) 的 \(x\)。

还要动态的话，可以使用线段树维护右端点的 \(F\) 值。

代码： 

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
#include <cstdio>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e6;
const int mod = 998244353;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,m;
int w[N + 5];
struct node
{
    int f;
    long long g;
} seg[(N << 2) + 10];
void insert(int x,int k,int p,int tl,int tr)
{
    if(tl == tr)
    {
        seg[p].f = k,seg[p].g = k * tl;
        return ;
    }
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,ls,tl,mid) : insert(x,k,rs,mid + 1,tr);
    seg[p].f = seg[ls].f + seg[rs].f,seg[p].g = seg[ls].g + seg[rs].g;
}
int query(int f,long long g,int p,int tl,int tr)
{
    if(tl == tr)
        return (2 * g % mod - seg[1].g % mod + mod) % mod * fpow(2LL * (f - seg[1].f + mod) % mod,mod - 2) % mod;
    int mid = tl + tr >> 1;
    long long sum = 2LL * (f + seg[ls].f - seg[1].f) * mid + seg[1].g - 2 * (g + seg[ls].g);
    return sum < 0 ? query(f,g,ls,tl,mid) : query(seg[ls].f + f,seg[ls].g + g,rs,mid + 1,tr);
}
int main()
{
    freopen("c.in","r",stdin),freopen("c.out","w",stdout);
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",w + i),insert(i,w[i],1,1,n);
    scanf("%d",&m);
    for(int x,k;m;--m)
        scanf("%d%d",&x,&k),insert(x,k,1,1,n),printf("%d\n",query(0,0,1,1,n));
}

Gitalking ...