脚本宝典收集整理的这篇文章主要介绍了「ABC221E」LEQ 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

E - LEQ

Time Limit: (2; sec) / Memory Limit: (1024; MB)

Score : (500; points)

Problem Statement|题目描述

• Given is a sequence of (N) integers: (A=(A_1 ,A_2 ,…,A_N )).

• 给定一个包含 (N) 个整数的序列: (A=(A_1 ,A_2 ,…,A_N ))。

• Find the number of (not necessarily contiguous) subsequences$ A′ =(A_1′ ,A_2′ ,…,A_k′ )$ of length at least (2) that satisfy the following condition:

(A_1′leq A_k′ .)

• 求子序列的个数(不一定是连续的)(A′ =(A_1′ ,A_2′ ,…,A_k′ ))，要求长度至少为 (2)，且满足以下条件：

(A_1′leq A_k′ .)

• Since the count can be enormous, print it modulo (998244353).

• 由于结果可能很大，所以将其对 (998244353) 取模输出。

• Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

• 在这里，当两个子序列来自不同的集合位置时，即使它们与序列相同，也可以区分它们。

Constraints|数据范围

• (2leq Nleq 3times 10^5)

• (1leq A_ileq 10^9)

• All values in input are integers.

• (2leq Nleq 3times 10^5)

• (1leq A_ileq 10^9)

• 输入中的所有值都是整数。

Input|输入

Input is given from Standard Input in the following format:

(N) (A_1 A_2 … A_N)

• 输入为以下格式的标准输入（中间有空格）：

(N) (A_1 A_2 … A_N)

Output|输出

• Print the number of (not necessarily contiguous) subsequences$ A′ =(A_1′ ,A_2′ ,…,A_k′ )$ of length at least (2) that satisfy the condition in Problem Statement.

• 输出子序列的个数(不一定是连续的)(A′ =(A_1′ ,A_2′ ,…,A_k′ ))，要求长度至少为(2)，且满足题目描述中的条件。

---

分析

AC代码

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int mod=998244353;
const int maxn=300010;
const int inf=0x3f3f3f3f;
int n;
inline ll power(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return ans%mod;
}
inline ll inv(ll x){return power(x,mod-2);}//逆元
ll a[maxn],b[maxn];
int sum[maxn];
inline int lowbit(int x){return x&(-x);}
inline void modify(int x,int k){
	while(x<=n){
		sum[x]=(sum[x]+k)%mod;
		x+=lowbit(x);
	}
}
inline ll ask(int x){
	ll res=0;
	while(x){
		res=(res+sum[x])%mod;
		x-=lowbit(x);
	}
	return res;
}
inline ll query(int l,int r){
	ll res=(ask(r)-ask(l-1)+mod)%mod;
//	printf("%dn",res);
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	cc_hash_table<int,int>rank;//哈希表
	for(int i=1;i<=n;i++)rank[b[i]]=i;//离散化
	for(int i=1;i<=n;i++)//树状数组
		modify(rank[a[i]],power(2,i));
	ll ans=0;
	for(int i=1;i<=n;i++){
		modify(rank[a[i]],mod-power(2,i));
		ans+=inv(power(2,i+1))*query(rank[a[i]],n);
		ans%=mod;
	}
	printf("%lld",ans);
	return 0;
}

$$-----CONTINUE------$$

< last 「ABC221D」Online games 题解

> catalogue 「ABC221」题解

脚本宝典总结

以上是脚本宝典为你收集整理的「ABC221E」LEQ 题解全部内容，希望文章能够帮你解决「ABC221E」LEQ 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。