优化树状数组 + 反向处理。
Solution
- 发现直接做不好下手。难点主要在求出所有的上升子序列并计算它们分别的贡献。
所以需要反向考虑每个单点在什么情况下产生贡献。一个单点会产生多少贡献。 - 一个单点产生贡献的条件很容易得到。一个是在一个上升子序列中;一个是它小于该序列后面的最大值。
发现第二个条件是可以转化为一个“一般化”的限制的:对于每个点 \(i\) 都能找到 \(r_i\) 表示最后一个大于它的项。
所以能让 \(i\) 产生贡献的一定是结尾在 \(r_i\) 前、包含 \(i\) 的上升子序列。 - 然后考虑能使 \(i\) 产生贡献的上升子序列个数。
根据乘法分配律,这个个数为:以 \(i\) 结尾的上升子序列个数 \(\times\) 以 \(i\) 开头结尾在 \(r_i\) 前的上升序列个数。 - 前者可以直接使用树状数组 \(O(n\log n)\) 得到。
后者可以转化一下。使用同样的方法求出以 \(i\) 为开头的上升子序列个数 \(-\) 以 \(i\) 开头且 \(r_i\) 结尾的上升序列个数。
显然 \(r_i\) 之后的数对上升序列不会产生任何贡献影响。 - 如果直接暴力求“以 \(i\) 开头且 \(r_i\) 结尾的上升序列个数”,那么复杂度将是 \(O(n^2\log n)\) 的。
考虑优化。考虑省去一些无用的转移——即转移项对 \(i\) 的上升序列不会产生贡献。 - 考虑什么样的项会对“以 \(i\) 开头 \(r_i\) 结尾的上升序列”产生贡献。
不妨设这样的项下标为 \(j\),那么:\(a_i<a_j<a_{r_i}\)。所以显然 \(r_j=r_i\)。
设 \(r_i=x\)。
所以对于一个 \(x\),所有能对以它结尾的上升序列产生影响的项 \(i\),\(r_i=x\)。
所以只需要在所有 \(r_i=x\) 的项 \(i\) 考虑上升序列的方案数,一起考虑它们“以自身开头以 \(x\) 结尾的上升序列”的个数即可。那么对这些项遍历用树状数组求一遍即可。 - 因为每个 \(i\) 只会有一个对应的 \(r_i\),所以单次询问复杂度是 \(O(n\log n)\) 的。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define init rep(i, 1, n) t[i] = 0
const int maxn = 2e5 + 5, mod = 1e9 + 7;
int n, a[maxn], id[maxn];
int t[maxn], pre[maxn], suf[maxn], f[maxn];
int s[maxn], tp;
vector<int> d[maxn];
inline int lb(int x){ return x & (-x);}
inline void add(int x, int k){
for(int i = x; i <= n; i += lb(i)) (t[i] += k) %= mod;
}
inline int qry(int x){ int res = 0;
for(int i = x; i; i -= lb(i)) (res += t[i]) %= mod;
return res;
}
inline bool cmp(int x, int y){
return a[x] == a[y] ? x > y : a[x] < a[y];
}
inline void slv(){
scanf("%lld", &n), tp = 0;
rep(i, 1, n) d[i].clear();
rep(i, 1, n) scanf("%lld", &a[i]), id[i] = i;
sort(id + 1, id + n + 1, cmp); rep(i, 1, n) a[id[i]] = i;//离散化
init; rep(i, 1, n) add(a[i], pre[i] = qry(a[i] - 1) + 1);
init; per(i, n, 1) add(n - a[i] + 1, suf[i] = qry(n - a[i]) + 1);//nlogn 求上升序列个数
per(i, n, 1) if(a[i] > a[s[tp]]) s[++tp] = i;
per(i, n, 1){ int l = 1, r = tp, pos;
while(l <= r){
int mid = (l + r) >> 1;
if(a[i] <= a[s[mid]]) r = mid - 1, pos = mid;
else l = mid + 1;
}
if(i != s[pos]) d[s[pos]].push_back(i);
} init;
rep(i, 1, tp){
add(n - a[s[i]] + 1, f[s[i]] = 1);
for(int v : d[s[i]]) add(n - a[v] + 1, f[v] = qry(n - a[v]));
for(int v : d[s[i]]) add(n - a[v] + 1, -f[v]);
add(n - a[s[i]] + 1, -1);
}
int ans = 0;
rep(i, 1, n) (ans += 1ll * (suf[i] - f[i] + mod) % mod * pre[i] % mod) %= mod;
printf("%lld\n", ans);
}
signed main(){
int T; scanf("%lld", &T);
while(T--) slv();
return 0;
}
Thanks for reading.
- 题解 数组 Subsequences Increasing Weighted题解subsequences increasing weighted subsequences increasing weighted 1621g subsequences increasing weighted报告 题解 数组subsequences increasing 题解subsequences 83e two 题解weighted matching general 题解increasing times 267g 题解subsequence increasing maxim 题解subsequence increasing longest 题解increasing sequences strictly