首页 > 其他分享 >ABC261F 题解

ABC261F 题解

时间:2023-05-26 19:55:12浏览次数:47  
标签:return int 题解 sum ABC261F ans lowbit mod

前言

题目传送门!

更好的阅读体验?

非常好的数据结构优化题。

思路

对于第 \(x\) 次询问,答案为 \(\dfrac{\sum\limits_{i=1}^x\sum\limits_{j=1}^x \max(a_i, a_j)}{x^2}\)。分母显然可以用逆元求,所以看上面那一坨。

看上面这幅图就比较显然了,我们只需要在线维护数据结构,支持:

  • 求出有多少个 \(a_j \le a_i\)。
  • 求出所有满足 \(a_j > a_i\) 的 \(\sum a_j\)。
  • 加入一个元素 \(a_i\)。

注意到 \(\forall a_i \le 2 \times 10^5\),所以直接上权值树状数组即可,一个维护数量,一个维护总和。

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int inv(int x, int y = mod - 2)
{
	int ans = 1;
	while (y)
	{
		if (y & 1) ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return ans;
}
struct BIT { //权值树状数组 
	int idx[N];
	int lowbit(int x) {return x & -x;}
	void update(int i, int k) {for (; i < N; i += lowbit(i)) (idx[i] += k) %= mod;}
	int query(int i) {int ans = 0; for (; i; i -= lowbit(i)) ans = (ans + idx[i]) % mod; return ans;}
} cnt, sum;
int main()
{
	int n, total = 0, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int a;
		scanf("%d", &a);
		ans += (2ll * cnt.query(a) + 1) * a % mod;         ans %= mod;
		ans += (2ll *(total - sum.query(a)) % mod + mod) % mod; ans %= mod;
		
		printf("%d\n", 1ll * ans * inv(1ll * i * i % mod) % mod);
		total = (total + a) % mod;
		cnt.update(a, 1), sum.update(a, a);
	}
	return 0;
}

希望能帮助到大家!

标签:return,int,题解,sum,ABC261F,ans,lowbit,mod
From: https://www.cnblogs.com/liangbowen/p/17435683.html

相关文章

  • Educational Codeforces Round 149 (Rated for Div. 2) 题解
    https://codeforces.com/contest/1837https://codeforces.com/contest/1837/problems利益相关:上紫祭。真的不要以为这道题放在F就不敢做。压线过题的感觉真好。ABC题都过水,就不写了。代码丢在这里:A:https://codeforces.com/contest/1837/submission/207156920B:https:......
  • 华为OD机试 本篇题解:找数字 or 找等值元素
    最近更新的博客华为od2023|什么是华为od,od薪资待遇,od机试题清单 https://dream.blog.csdn.net/article/details/128980730华为OD机试真题大全,用Python解华为机试题|机试宝典 https://dream.blog.csdn.net/article/details/129221789【华为OD机试】全流程解析......
  • ubauntu18.04下出现Invalid YAML: inconsistent indentation: version: 2问题解决
    在配置网卡信息时候遇到如上问题查询后有几种可能错误的地方:未能通过yaml语法和缩进,YAML在解释命令、配置参数这方面十分注重语法和缩进,只有适当缩进才能够解析YAML配置网络配置出现故障,IP地址的网关不正确,或者掩码配置失误那么我们现在在网络配置正确前提下最重要就是了解缩进工作......
  • P4557 [JSOI2018]战争 题解
    闵可夫斯基和前言入门建议看吉老师(吉如一)的计算几何入门到放弃。感觉应该是讲的最通俗易懂的了。本文借鉴了Winxp的博客,以及吉老师视频中的思路。写这篇博客的初衷是因为我作为一个初学者,此题里的题解对我来说理解起来不算太难,但是实现起来细节比较多,题解里也没有很详细地去解......
  • P4288 [SHOI2014]信号增幅仪 题解
    感谢审核人Description给定\(n\)个点,椭圆长轴的方向\(a\)和放大倍数\(p\),求覆盖全部点的最小椭圆的半短轴长度。Solution让我们求最小覆盖椭圆,但是椭圆不具有什么好的性质,我们可以把椭圆转化成圆来做,这样,题目就转化成了最小覆盖圆,这个用随机增量法来做就可以了。接下来......
  • UVA10902 Pick-up Sticks 题解
    Description按顺序给出\(n\)个棍子两个端点的坐标。如果后来的棍子与前边的棍子相交,则说后面的把前面的挡住了。问最后有多少个棍子没被挡住。\(n\leq10^5\),且答案不超过\(1000\)。Solution叉积基本运用。定义:\(\overrightarrow{a}\times\overrightarrow{b}=|\over......
  • SP898 Transmitters 题解
    Description给定\(n\)个点的坐标、半圆的半径以及坐标。问半圆怎么放能覆盖最多的点,输出最多个数。Solution计算几何入门题。首先显然距离圆心超过半径的点是一定不会被覆盖的,舍去。再者我们考虑,半圆的放法是有无限多种的,我们要考虑哪些是有用的。我们可以想到,最优的半圆一......
  • P8943 Deception Point 题解
    Description题目给的很详细了。Solution首先\(n\)个点\(n\)条边,我们很容易就想到基环树(比正常的树多了一条边,形成了一个环),不会也没关系,这题跟基环树其实关系不大。首先,我们可以发现题目中说明了这个环不是一个四元及以下的环,这代表着如果\(A\)提前进入了这个环,那么他......
  • [ABC287D] Match or Not 题解
    Description翻译给的很明白了,就是让你判断\(S\)串的前\(x(0\leqx\leq|T|)\)个字符和后\(|T|-x\)个字符组成的字符串和\(T\)串是否相等,其中问号能代替所有字母。Solution很有意思的一道题。首先我们可以知道,如果前\(i-1\)位不能匹配的话,那么第\(i\)位不管它本......
  • P5446 [THUPC2018]绿绿和串串 题解
    Description给定一个串\(S\),要求串\(S\)是串\(R\)经过多次翻转后的前缀。问有多少种初始长度的串\(R\)。串\(R\)翻转的定义是将前\(|R|-1\)个字符倒序排列后,插入到串的最后。如\(\mathrm{aaa}\)翻转后得到\(\mathrm{abcdcba}\)。Solution我们先设以\(i\)为......