[ABC221E] LEQ 题解

思路解析

很有思维量的一道题。首先根据题目要求发现，新求的子序列只跟子序列的头尾有关，而在确定头尾之后中间的元素选或不选没有任何关系。也就是确定新子序列的头尾下标分别为 \(i,j\)，那么以当前头尾的可行子序列个数就是 \(2^{j-i-1}=2^j \div 2^{i+1}\) 种可能。

接下来我们思考，根据题目要求，上方的 \(i,j\) 一定有 \(a_i \le a_j\)，于是我们要做的其实就是找固定 \(j\)，有多少个 \(i\) 使得 \(i<j,a_i \le a_j\)，也就是个二维偏序。但事实上不需要那么复杂，假设有 \(i_1,i_2,\dots,i_k\) 都满足题目的条件，那么以 \(j\) 结尾的子序列的个数就是 \(2^j \div 2^{i_1+1}+2^j \div 2^{i_2+1}+\dots+2^j \div 2^{i_k+1}=2^j \div (2^{i_1+1}+2^{i_2+1}+\dots+2^{i_k+1})\)。

那么接下来就很轻松了，由于上方的 \(i,j\) 一定有 \(a_i \le a_j\)，所以我们可以用一个 \(rk_i\) 存下 \(a_i\) 的排名，设 \(v_{rk_i}=2^{i+1}\)，然后求 \(\sum_{k=1}^{rk_j-1}v_k\)，这样我们就可以求得满足 \(a_i \le a_j\) 的条件所有的 \(i\) 对答案的贡献，还要继续考虑 \(i<j\) 这个条件。我们其实可以不先处理出来 \(v\) 的值，而是在 \(j \to j+1\) 时处理 \(v_j\) 的值，这样就能保证所有 \(v\) 当中有值的 \(v_{rk_i}\) 都有 \(i<j\)。由于 \(v\) 需要满足单点修改和区间求和的操作，所以需要使用树状数组优化。

注意：由于有取模和乘方，所以需要使用逆元和快速幂求解。

时间复杂度：需要遍历每个下标，都需要一次区间查询和单点修改，复杂度为 \(O(n \log n)\)。

code

//ABC211E
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const ll mod = 998244353;
int n, m;
ll a[N], c[N], b[N];
map<ll, int> rk;

ll ksm(ll a, ll b, ll p) {
	ll ans = 1;
	while(b) {
		if(b & 1) {
			ans = ans * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
ll niyuan(ll a, ll p) {
	return ksm(a, p - 2, p);
}

void add(ll x, ll y) {
	for(; x <= n; x += (x & -x)) {
		c[x] = (c[x] + y) % mod;
	}
}
ll ask(ll x) {
	ll sum = 0;
	for(; x > 0; x -= (x & -x)) {
		sum = (sum + c[x]) % mod;
	}
	return sum;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++) {
		rk[b[i]] = i;
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = (ans + (ksm(2, i, mod) * ask(rk[a[i]])) % mod) % mod;
		add(rk[a[i]], ksm(niyuan(2, mod), i + 1, mod));
	}
	cout << ans;
	return 0;
}