Solution -「ARC 126E」Infinite Operations
2024-09-03 09:42:57
\(\mathcal{Description}\)
Link.
给定序列 \(\{a_n\}\),定义一次操作为:
- 选择 \(a_i<a_j\),以及一个 \(x\in\mathbb R_+\),使得 \(a_i+x\le a_j-x\);
- 令 \(a_i\leftarrow a_i+x,a_j\leftarrow a_j-x\),本次操作的得分为 \(x\)。
定义序列的得分为进行任意次操作能得到的最大得分和,现给定 \(m\) 次形如 \(a_x\leftarrow y\) 的修改操作,在每次修改操作后求出当前序列的得分。
\(\mathcal{Solution}\)
定义序列的势能 \(\Phi=\sum_{i<j}|a_i-a_j|\),设进行一次操作后得到新势能 \(\Phi'\),显然有 \(\Phi'-\Phi\le-2x\),其中 \(x\) 即操作时所选取的正数。同时,取等条件容易看出为 \(\not\exist a_k,a_k\in(a_i,a_j)\),由此,又能得到只要 \(\Phi>0\),我们必然能以势能减少 \(2x\) 的代价增加 \(x\) 分。所以答案就是 \(\frac{\Phi}{2}\)。
选用平衡树来动态维护 \(\Phi\) 即可支持修改。复杂度 \(\mathcal O((n+m)\log n)\)。
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef long long LL;
const int MAXN = 6e5, MOD = 998244353, INV2 = 499122177;
int n, m, root, a[MAXN + 5];
inline int mul( const int u, const int v ) { return 1ll * u * v % MOD; }
inline int sub( int u, const int v ) { return ( u -= v ) < 0 ? u + MOD : u; }
inline int add( int u, const int v ) { return ( u += v ) < MOD ? u : u - MOD; }
struct Treap {
int node, root, ch[MAXN + 5][2], aux[MAXN + 5], val[MAXN + 5];
int siz[MAXN + 5], sum[MAXN + 5];
Treap() { srand( 20120712 ); }
inline int newnd( const int v ) {
++node, aux[node] = rand(), sum[node] = val[node] = v, siz[node] = 1;
return node;
}
inline void pushup( const int u ) {
siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;
sum[u] = add( add( sum[ch[u][0]], sum[ch[u][1]] ), val[u] );
}
inline int merge( const int u, const int v ) {
if ( !u || !v ) return u | v;
if ( aux[u] < aux[v] ) {
return ch[u][1] = merge( ch[u][1], v ), pushup( u ), u;
} else {
return ch[v][0] = merge( u, ch[v][0] ), pushup( v ), v;
}
}
inline void vsplit( const int u, const int k, int& x, int& y ) {
if ( !u ) return void( x = y = u );
if ( val[u] <= k ) vsplit( ch[u][1], k, ch[x = u][1], y ), pushup( x );
else vsplit( ch[u][0], k, x, ch[y = u][0] ), pushup( y );
}
inline int erase( const int v ) {
int x, y, z; vsplit( root, v, x, z );
int ret = add( sub( mul( sub( siz[x], siz[z] ), v ), sum[x] ), sum[z]);
vsplit( x, v - 1, x, y ), y = merge( ch[y][0], ch[y][1] );
return root = merge( x, merge( y, z ) ), ret;
}
inline int insert( const int v ) {
int x, y = newnd( v ), z; vsplit( root, v, x, z );
int ret = add( sub( mul( sub( siz[x], siz[z] ), v ), sum[x] ), sum[z]);
return root = merge( x, merge( y, z ) ), ret;
}
} trp;
int main() {
scanf( "%d %d", &n, &m );
int ans = 0;
rep ( i, 1, n ) scanf( "%d", &a[i] ), ans = add( ans, trp.insert( a[i] ) );
for ( int x, v; m--; ) {
scanf( "%d %d", &x, &v );
ans = sub( ans, trp.erase( a[x] ) );
ans = add( ans, trp.insert( a[x] = v ) );
printf( "%d\n", mul( ans, INV2 ) );
}
return 0;
}
最新文章
- 微服务与Docker介绍
- 浅谈Linux内存管理机制
- windows10下sql server 2005 无法运行或sql server服务无法启动的完美解决方案
- php模拟http请求的方法
- ionic cordova 热更新(引用自www.zyyapp.com/post/116.html)
- U盘10分钟安装linux系统
- lvs之ip-tun(ip隧道)技术的学习与实践
- c语言结构体保存并输出学生信息
- ProgressBarLayoutView
- Android之线程终止
- 一、JSP、Servlet 概要
- mysql选择联合索引还是单索引?索引列应该使用哪一个最有效?深入測试探讨
- tomcat 支持https
- css 图片 圆形显示区域
- javascript call()函数
- 堆和栈(java内存)
- 移动应用/APP的测试流程及方法
- 手把手教你如何用eclipse搭建前端开发环境
- linux下插入的mysql数据乱码问题及第三方工具显示乱码问题
- chrome不能安装adblock插件