首页 > 其他分享 >AtCoder-abc351_f讲解

AtCoder-abc351_f讲解

时间:2024-04-28 21:11:33浏览次数:26  
标签:AtCoder 结点 log 复杂度 abc351 讲解 区间 mathcal rk

原题翻译

给定一个序列 \(A\),求出:

\[\sum \limits_{i=1}^N \sum \limits_{j=i+1}^N \max(A_j-A_i,0) \]

答案小于 \(2^{63}\)。

思路

这里提供三种思路(分块经 XXR 尝试,卡常卡不过)

1 权值树状数组

将 \(A\) 离散化,设 \(rk_i\) 为 \(A_i\) 离散化后的排名,去重后元素个数为 \(M\)。

每个结点维护两个值:区间和、区间元素个数。

倒序遍历 \(A\),遇到 \(A_i\) 时,先将答案加上 \(rk_{A_i}+1 \sim M\) 区间的区间和,然后减去区间元素个数 \(\times A_i\)。接着将 \(rk_{A_i}\) 结点的区间和加上 \(A_i\),区间元素个数加上 \(1\)。

可以发现,操作为单点修改、区间查询,可以用树状数组。

时间复杂度为 \(\mathcal{O}(N \log N)\)。

代码

2 权值线段树

既然有树状数组,那么就有线段树。

时间复杂度为 \(\mathcal{O}(N \log N)\)。

3 平衡树

可以用 FHQ_Treap。每个结点维护子树和子树大小。

倒序遍历 \(A\),遇到 \(A_i\) 时,将平衡树分裂为两棵树,\(x\) 存小于等于 \(A_i\) 的结点,\(y\) 存大于等于 \(A_i\) 的结点。让答案加上 \(y\) 子树的子树和,然后减去子树大小 \(\times A_i\)。接着将 \(A_i\) 插入平衡树,并合并 \(x,y\)。

分裂和合并的时间复杂度为 \(\mathcal{O}(\log N)\),因此时间复杂度为 \(\mathcal{O}(N \log N)\)。

代码

标签:AtCoder,结点,log,复杂度,abc351,讲解,区间,mathcal,rk
From: https://www.cnblogs.com/lrxmg139/p/18164491

相关文章

  • AtCoder-abc351_d 题解
    原题翻译题意简述给定\(H\timesW\)的网格图,如果一个字符是#,则不能走到该字符上;如果是.,则可以走到该字符上,但如果它周围\(4\)个格子中有#字符,则不能再继续行走了。自由度是指从一个格子出发,能走到不同格子的数量(可以出发多次)。求出所有格子的最大自由度。思路考虑......
  • Linux Centos7 虚拟环境安装Mysql数据库(超详细图文讲解)
    LinuxCentos7虚拟环境安装Mysql数据库(超详细图文讲解)1、进入Centos7虚拟机,使用wget下载Mysql相应的rpm包下载:wgethttp://repo.mysql.com/mysql57-community-release-el7-8.noarch.rpm如果没有wget命令,可以使用yum安装,yuminstallwget2、执行rpm命令,安装rpmrpm-ivhmys......
  • AtCoder Beginner Contest 208 E
    E-DigitProducts点击查看代码map<int,int>f[20];voidsolve(){intn,k;cin>>n>>k;autos=to_string(n);intm=s.size();function<int(int,int,int,int)>dfs=[&](inti,intlimit,intis_num,intmul)->int{if(i......
  • AtCoder Beginner Contest 351 E - Jump Distance Sum 切比雪夫距离与曼哈顿距离的转
    先说知识点。曼哈顿距离:横纵坐标距离差的绝对值的和,即|X1-X2|+|Y1-Y2|,离(0,0)点曼哈顿距离为1的点形成的是一个旋转45度后的正方形切比雪夫距离:横纵坐标距离差的绝对值的最大值,即max(|X1-X2|,|Y1-Y2|),离(0,0)点切比雪夫距离为1的点形成的是一个不旋转的正方形曼哈......
  • abc351g 题解
    这场abcF、G质量堪忧。怎么能扔板子上来呢?板子:P4719【模板】"动态DP"&动态树分治Solution这种每次修改对后面询问有影响,又每次都要输出答案的,离线就基本做不了了,这时候就往动态算法想,其实做过几道ddp的题就看出来这是个板子。由于题目中的式子性质优良,我们很明显可以把......
  • atcoder集
    AtCoderBeginnerContest351A-Thebottomoftheninth(签到题) Code:#include<bits/stdc++.h>usingnamespacestd;#definedebug(x)cerr<<#x<<":"<<x<<'\n';intmain(){ios::sync_w......
  • ABC351
    A.Thebottomoftheninth答案为\(\suma_i-\sumb_i+1\)B.SpottheDifference模拟C.Mergetheballs直接按题意模拟就是\(O(n)\)的,那么这题的瓶颈就在于两个球做合并,注意到\(2^a+2^a=2^{a+1}\),那么我们就可以不考虑底数\(2\),而直接处理指数即可代码实......
  • ABC351G题解
    考虑动态dp的套路,先树剖一下,令\(son(x)\)为点\(x\)的重儿子。\(g_x=\prod\limits_{u\inC(x)\landu\neqson(x)}f_u\)。于是有\(f_x=f_{son(x)}g_x+a_x\)。于是\(\begin{bmatrix}f_x&1\end{bmatrix}=\begin{bmatrix}f_{son(x)}&1\end{bmatrix}\begin{bmatrix}g_......
  • 【BFS】abc351D Grid and Magnet 题解
    传送门D-GridandMagnet题意:给定h行w列的图表,其中部分位置有磁铁,人物会在磁铁四周((x+1,y),(x-1,y),(x,y+1),(x,y-1))停止,某点的自由度定义为从该点出发最多可到的方块数目可以走重复路前置例题:求连通块大小洛谷P1141思路:由自由度的定义联想到连通块的大小,从而决定用BFS......
  • ABC351
    我多久没更新这个系列了啊E把格子分成两类,每一类之间的坐标均可互相走到。然后将这里面的点都旋转\(45\)度,于是这个问题就被转换成曼哈顿距离的问题了。我们可以把\(x\)和\(y\)拆开计算。然后我们排个序,求个差分,然后对于每一个区间算贡献即可。code......