https://codeforces.com/gym/106495/problem/I

赛时思路：

1.先标记并删除所有的'='；
2.再按照<、>运算符构造出一个初始的 b1 数组；
3.然后找出其中所有的“坑”，将“坑”中除了最高点的部分全部都往下移直到 b1[k]_min == 1；
4.最终根据之前记录的 '=' 的位置还原出数组 b。

但是，如果纯纯按照这个思路去写，整体代码太过繁琐，需要不断地进行平移、补齐操作

于是，浅浅优化之后，AC思路：

题目要求最小化 \(\sum a_i b_i\)，由于给定的 \(a_i > 0\)，原问题等价于在满足相邻关系约束的前提下，使每一个 \(b_i\) 的值都最小化。

1.连通块压缩（处理 =）：

由于由 = 连接的 \(b_i\) 必须完全相等，我们首先将原序列中由 = 连通的段合并为一个“块”，只保留块与块之间的 < 或 > 关系。

2.确定下界（处理 < 和 >）：

压缩后，这就是一个经典的依赖关系求极值问题（可以看作 DAG 上的最长路）。我们建立一个新数组 b1，初始值全置为 1。通过两次线性遍历来满足所有的不等式约束：

从左到右遍历：处理 < 关系。如果块 \(i <\) 块 \(i+1\)，则要求 \(b1[i+1] = \max(b1[i+1], b1[i] + 1)\)。
从右到左遍历：处理 > 关系。如果块 \(i >\) 块 \(i+1\)，则要求 \(b1[i] = \max(b1[i], b1[i+1] + 1)\)。

两次遍历结束后，b1 数组中的每个元素必然是满足所有约束的最小正整数。（也就是将所有的波谷沉到底部取 1）。

3.还原并计算答案：

根据步骤 1 记录的映射关系，将各个块的最佳取值赋给原数组 \(b\) 中的对应区间，最后遍历一遍计算 \(\sum a_i b_i\) 即可。整个算法的时间复杂度为 \(\mathcal{O}(N)\)，空间复杂度为 \(\mathcal{O}(N)\)。

总结：

过两次线性遍历来满足所有的不等式约束建立一个新数组 b1，初始值全置为 1。通过两次线性遍历***来满足所有的不等式约束

此法实在绝妙orzorzorz
完美解决了赛时正确思路却无法实现的苦恼

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e9+5;
#define all(a) (a).begin(), (a).end()void solve(){int n;cin >> n;vector<ll> a(n);for(int i=0; i<n; ++i) cin >> a[i];string s;cin >> s;string s1;int curl = 0;vector<int> L, R; // L[i] 和 R[i] 分别记录第 i 个块在原数组中的左右边界for(int i=0; i<n-1; ++i){ // 1. 压缩连续的 '='if(s[i] != '='){L.push_back(curl);R.push_back(i);curl = i+1;s1 += s[i];}}L.push_back(curl);R.push_back(n-1);int sz = s1.size();vector<int> b1(sz+1, 1);for(int i=0; i<sz; ++i){ // 2. 从左向右遍历，处理 '<'if(s1[i] == '<'){b1[i+1] = b1[i] + 1;}}for(int i=sz-1; i>=0; --i){ // 3. 从右向左遍历，处理 '>'if(s1[i] == '>'){b1[i] = max(b1[i], b1[i+1] + 1);}}ll ans = 0;vector<ll> b(n);for(int i=0; i<=sz; ++i){for(int j=L[i]; j<= R[i]; ++j){b[j] = b1[i];ans += a[j]*b[j];}}cout << ans << '\n';for(int i=0; i<n; ++i) cout << b[i] << " ";
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;
//	cin>>t;while(t--) solve();
}
/*
5
2 1 3 1 4
>>>> 29
5 4 3 2 1 6
3 1 4 1 5 9
<=>><43
1 3 3 2 1 2 8
8 2 2 8 3 7 4 6
=<<=>>=71
1 1 2 3 3 2 1 1 9
3 1 4 1 5 9 7 8 6
<=>><<<<126
1 3 3 2 1 2 3 4 5 
*/