2020-2021:teams:legal_string:jxm2001:contest:arc_126
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:arc_126 [2021/10/09 19:45] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:arc_126 [2021/10/09 22:03] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 85: | 行 85: | ||
| </hidden> | </hidden> | ||
| + | ===== E - Infinite Operations ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个序列 $A$，定义一次操作为选定两个 $a_i,a_j(a_i\gt a_j)$，将两个数赋值为 $a_i-x,a_j+x$，其中 $0\lt x\le \frac {a_i-a_j}2$，并得到 $x$ 分。 | ||
| + | |||
| + | 定义 $F(A)$ 表示序列 $A$ 经过无限次操作后能得到的最大得分。接下来若干次单点修改操作，每次操作后求 $F(A)$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 定义势能函数 $G(A)=\sum_{i=1}^n\sum_{j=1}^{i}|a_i-a_j|$，不难发现一次操作得 $x$ 分至少使得 $G(A)$ 减少 $2x$。 | ||
| + | |||
| + | 同时如果假定 $a_1\le a_2\le\cdots a_n$，则选定相邻两个值操作恰好可以得 $x$ 分同时使得 $G(A)$ 减少 $x$。 | ||
| + | |||
| + | 任意取两个相邻数取平均，易知经过无数次操作后有 $G(A)=0$。因此答案为 $\frac {G(A)}2$，树状数组维护答案即可，时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e5+5,MAXV=6e5+5,mod=998244353,inv2=(mod+1)/2; | ||
| + | int a[MAXN],b[MAXV]; | ||
| + | pair<int,int> opt[MAXN]; | ||
| + | LL c1[MAXV],c2[MAXV]; | ||
| + | #define lowbit(x) ((x)&(-x)) | ||
| + | void update(int pos,int v1,int v2){ | ||
| + | while(pos<MAXV){ | ||
| + | c1[pos]+=v1; | ||
| + | c2[pos]+=v2; | ||
| + | pos+=lowbit(pos); | ||
| + | } | ||
| + | } | ||
| + | pair<LL,LL> query(int pos){ | ||
| + | pair<LL,LL> ans=make_pair(0LL,0LL); | ||
| + | while(pos){ | ||
| + | ans.first+=c1[pos]; | ||
| + | ans.second+=c2[pos]; | ||
| + | pos-=lowbit(pos); | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),q=read_int(); | ||
| + | _rep(i,1,n) | ||
| + | a[i]=b[i]=read_int(); | ||
| + | _rep(i,1,q){ | ||
| + | opt[i].first=read_int(); | ||
| + | opt[i].second=read_int(); | ||
| + | b[n+i]=opt[i].second; | ||
| + | } | ||
| + | sort(b+1,b+n+q+1); | ||
| + | int m=unique(b+1,b+n+q+1)-b; | ||
| + | LL ans=0,sum=0; | ||
| + | _rep(i,1,n){ | ||
| + | int v=lower_bound(b+1,b+m,a[i])-b; | ||
| + | update(v,b[v],1); | ||
| + | sum+=b[v]; | ||
| + | pair<LL,LL> t=query(v); | ||
| + | ans+=1LL*b[v]*t.second-t.first+sum-t.first-1LL*b[v]*(i-t.second); | ||
| + | ans%=mod; | ||
| + | } | ||
| + | _rep(i,1,q){ | ||
| + | int p=opt[i].first; | ||
| + | int v=lower_bound(b+1,b+m,a[p])-b; | ||
| + | pair<LL,LL> t=query(v); | ||
| + | ans-=1LL*b[v]*t.second-t.first+sum-t.first-1LL*b[v]*(n-t.second); | ||
| + | ans%=mod; | ||
| + | update(v,-b[v],-1); | ||
| + | sum-=b[v]; | ||
| + | a[p]=opt[i].second; | ||
| + | v=lower_bound(b+1,b+m,a[p])-b; | ||
| + | update(v,b[v],1); | ||
| + | sum+=b[v]; | ||
| + | t=query(v); | ||
| + | ans+=1LL*b[v]*t.second-t.first+sum-t.first-1LL*b[v]*(n-t.second); | ||
| + | ans%=mod; | ||
| + | enter(1LL*(ans+mod)*inv2%mod); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_126.1633779959.txt.gz · 最后更改: 2021/10/09 19:45 由 jxm2001
