【题解】CF1621G Weighted Increasing Subsequences
题意：
给定长度为 $n$ 的序列 $\{a_n\}$，对于其一个长度为 $k$ 的上升子序列 $a_{i_1},a_{i_2}\cdots a_{i_k}$ 定义其权值为满足 $j\in[1,k]$，存在一个 $x\in(i_k,n]$ 使得 $a_x>a_{i_j}$ 的 $j$ 的个数。
计算所有上升子序列的权值和。
$1\le n\le 2\times 10^5, 1\le a_i\le 10^9$。
首先将序列离散化，计算每个上升子序列的权值是困难的，我们考虑每个位置 $a_p$ 的贡献。
对于一个 $a_p$，$i_k$ 最远可以到哪里，使得存在一个 $x\in(i_k,n]$ 满足 $a_x>a_i$？容易发现，若设 $r_p$ 表示最靠右的满足 $a_{r_p}>a_p$ 的下标，则 $i_k<r_p$。注意到 $a_{r_p}$ 必然在后缀单调栈上。
于是，对于每一个 $p$，我们需要计算 “经过 $p$，且最后一个元素在 $r_p$ 之前” 的上升子序列个数。容斥成 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的上升子序列个数。
本人做到这里的时候被卡住了，“经过定点，结尾在一段后缀的上升子序列个数” 看起来不是很可做。
继续观察性质，注意到我们设 $r_p$ 是最靠右的满足 $a_{r_p}>a_p$ 的位置，这意味着 $\forall i\in(r_p, n],\ a_i\le a_p$。说明，任意经过 $p$ 的上升子序列，都不可能在 $(r_p, n]$ 结束。
于是 “经过 $p$，且最后一个元素下标 $\in[r_p,n]$” 的限制就转变成了 “经过 $p$，且最后一个元素下标 $=r_p$”，相当于钦定了一个定点，钦定了结尾元素。
如何计算这样的子序列个数？首先肯定要把子序列拆成 $p$ 之前、之后。前面是好算的，$p$ 之后的部分，就相当于：
“第一个元素下标是 $p$，最后一个元素下标是 $r_p$” 的上升子序列个数。
接下来我的处理和官方的题解有一些区别：由于 $r_p$ 是最靠右的满足条件的下标，所以任意从 $p$ 开始延申的上升子序列，其结尾下标必然 $\le r_p$。
于是，我们只需要维护 “从 $p$ 开始，以最远的可行位置结尾” 的方案数即可，容易使用树状数组维护。
时间复杂度 $\mathcal{O}(n\log n)$。
//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1
const int MAXN = 2e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int T, n, m;
int a[MAXN], FT[MAXN], pre[MAXN], suf[MAXN];
int mx[MAXN], mxv[MAXN];
LL Ans;
vec<int> v;
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }
void add1(int x, int v) { for(; x <= n; x += lowbit(x)) (FT[x] += v) %= mod; }
int ask1(int x) { int res = 0; { for(; x; x -= lowbit(x)) (res += FT[x]) %= mod; } return res; }
void add2(int x, pii v) {
for(; x; x -= lowbit(x)) {
if(mx[x] < v.fst) mx[x] = v.fst, mxv[x] = 0;
if(mx[x] == v.fst) (mxv[x] += v.scd) %= mod;
}
}
pii ask2(int x) {
int _mx = 0, _mxv = 0;
for(; x <= n; x += lowbit(x)) {
if(_mx < mx[x]) _mx = mx[x], _mxv = 0;
if(_mx == mx[x]) (_mxv += mxv[x]) %= mod;
}
return mp(_mx, _mxv);
}
void solve() {
read(n); v.clear(); Ans = 0;
for(int i = 1; i <= n; ++i) read(a[i]), v.pb(a[i]);
for(int i = 1; i <= n; ++i) FT[i] = mx[i] = mxv[i] = 0;
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 1; i <= n; ++i) a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
for(int i = 1; i <= n; ++i) add1(a[i], pre[i] = ask1(a[i] - 1) + 1);
for(int i = 1; i <= n; ++i) FT[i] = 0;
for(int i = n; i >= 1; --i) {
add1(n - a[i] + 1, suf[i] = ask1(n - a[i]) + 1);
pii cur = ask2(a[i] + 1);
if(!cur.scd) cur = mp(i, 1);
(suf[i] -= cur.scd) %= mod; add2(a[i], cur);
}
for(int i = 1; i <= n; ++i) (Ans += 1ll * pre[i] * suf[i]) %= mod;
Ans = (Ans + mod) % mod;
printf("%lld\n", Ans);
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(T);
while(T--) solve();
return 0;
}