这个题还是不太懂，下面附上的是大佬的题解(https://zhanghuimeng.github.io/post/codeforces-1102e-monotonic-renumeration/) E. Monotonic Renumeration time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a consisting of n integers. Let’s denote monotonic renumeration of array a as an array b consisting of n integers such that all of the following conditions are met:
b1=0; for every pair of indices i and j such that 1≤i,j≤n, if ai=aj, then bi=bj (note that if ai≠aj, it is still possible that bi=bj); for every index i∈[1,n−1] either bi=bi 1 or bi 1=bi 1. For example, if a=[1,2,1,2,3], then two possible monotonic renumerations of a are b=[0,0,0,0,0] and b=[0,0,0,0,1].
Your task is to calculate the number of different monotonic renumerations of a. The answer may be large, so print it modulo 998244353.
Input The first line contains one integer n (2≤n≤2⋅105) — the number of elements in a.
The second line contains n integers a1,a2,…,an (1≤ai≤109).
Output Print one integer — the number of different monotonic renumerations of a, taken modulo 998244353.
Examples inputCopy 5 1 2 1 2 3 outputCopy 2 inputCopy 2 100 1 outputCopy 2 inputCopy 4 1 3 3 7 outputCopy 4
题意 给定一个长度为n的数组a，要求为a生成一个对应的数组b，满足： b[0] = 0 对于任意0 <= i < j <= n，如果满足a[i] == a[j]，必有b[i] == b[j]（不过a[i] != a[j]时也可能有b[i] == b[j]） 任取0 <= i < n - 1，必有b[i] = b[i 1]或b[i] 1 = b[i 1] 问共有多少种可能的b。 分析 显然b[i]是一个递增序列，因此可以自然推出，若a[i] == a[j]，则必有b[i] == b[i 1] == … = b[j]，也就是说，对于a中任意位置两个相等的元素，它们在b中对应的是一整段相等的元素。显然这种元素相等是可能会发生重叠的，因此一个自然的想法就是，把重复的元素建模成线段，然后合并发生overlap的线段以得到相等元素的最长长度。 我的做法是，从后向前遍历a，如果发现当前元素和后面的元素重复了，则取index最靠后的元素，组成一条线段，插入到栈中与其他元素合并；否则把它自己的index作为一条线段插入到栈中。最后栈中留下的就是几条互不相交（且并组成了整个区间）的线段。 对于（除了第一条之外）每条线段，我们可以选择让它的值和前一条相等，也可以选择让它的值是前一条 1。每种选择都会导致生成一种新的b。于是结果是2^{线段数-1}。 例子：对于a = {1, 2, 1, 2, 3}，1对应的线段是[0, 2]，2对应的线段是[1, 3]，3对应的线段是[4, 4]；合并之后得到两条线段，[0, 3]和[1, 4]；只有两种b，分别是{0, 0, 0, 0, 0}和{0, 0, 0, 0, 1}。
代码语言：javascript复制#include <iostream>
#include <vector>
#include <map>
using namespace std;
int a[200005];
int n;
typedef long long int LL;
const LL P = 998244353;
LL pow2(LL x) {
LL pow = 2, ans = 1;
while (x > 0) {
if (x & 1)
ans = (ans * pow) % P;
pow = (pow * pow) % P;
x >>= 1;
}
return ans;
}
int main() {
map<int, int> indMap;
vector<pair<int, int>> s;
cin >> n;
for (int i = 0; i < n; i ) {
cin >> a[i];
if (indMap.find(a[i]) == indMap.end()) {
indMap[a[i]] = i;
}
}
for (int i = n - 1; i >= 0; i--) {
pair<int, int> interval;
if (indMap.find(a[i]) != indMap.end() && indMap[a[i]] < i) {
interval = make_pair(indMap[a[i]], i);
}
else {
interval = make_pair(i, i);
}
if (!s.empty() && s.back().first <= interval.first && s.back().second >= interval.second)
continue;
if (!s.empty() && interval.second >= s.back().first) {
interval.second = s.back().second;
s.pop_back();
s.push_back(interval);
}
if (s.empty() || interval.second < s.back().first)
s.push_back(interval);
}
int cnt = 0;
if (!s.empty() && s.front().second < n - 1) cnt ;
if (!s.empty() && s.back().first > 0) cnt ;
for (int i = 0; i < s.size(); i ) {
cnt ;
// 本条线段和前一条线段之间的间隔
if (i > 0 && s[i - 1].second < s[i].first - 1)
cnt ;
}
cout << pow2(cnt - 1) << endl;
return 0;
}
