JZOJ 6386 C

由题意可得方程 m∑i=1wiS|i−x|=x，其中 x 表示答案，S=m∑i=1wi。
（其实我也不知道是怎么得的）

设 F(x)=m∑i=1|i−x|⋅wi−S⋅x，问题即求 F 的零点。
注意到其中有绝对值，不好直接求。
但是由于 i 均为整数，故若能求得答案的整数部分即可去绝对值。

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

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

代码：

#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));
}