题目链接：https://scut.online/p/129
题解：
因为ai<=100000, 且ai只出现一次， 所以可以用pos[]数组保存ai的下标， 这样就不用向前遍历查找了，做到一步访问。 如果ai很大但仍只出现一次，亦可以用map存其下标。
设dp[i]为：以a[i]为结尾的所有子序列的bx值之和。
DP；
1假设已经求出了dp[i-1]，那么在a[1]~a[i-1]的基础上，再加上a[i]。先假设a[i]的存在并不能对bx值作出贡献， 即以a[i]为结尾的所有子序列的bx值之和dp[i] = dp[i-1] 。
2.经过分析，可知：以a[i]为子序列的结尾，往前溯。 当没有出现a[i]-1或者a[i]+1时，a[i]对当前的序列都贡献了1，所以每往前一步，dp[i]都能增加1。当出现a[i]+1 or a[i]-1其中的一个时， 每往前 溯一步， a[i]的作用无效或者拆散了一对又合成了一对，所以在这一区间，dp[i]无变化。 当a[i]+1 and a[i]-1都出现时， 每往前溯一步， a[i]都拆散了一对，所以dp[i]要减去1。
最后答案就是dp[i]之和。
代码如下：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <sstream> #include <algorithm> using namespace std; #define pb push_back #define mp make_pair #define ms(a, b) memset((a), (b), sizeof(a)) #define eps 0.0000001 typedef long long LL; const int INF = 2e9; const LL LNF = 9e18; const int mod = 1e9+7; const int maxn = 100000+10; LL a[maxn], pos[maxn], dp[maxn]; int n; void init() { scanf("%d",&n); for(int i = 1; i<=n; i++) scanf("%lld",&a[i]); ms(pos,0); ms(dp,0); } void solve() { int p; pos[a[1]] = 1; for(int i = 2; i<=n; i++) { dp[i] = dp[i-1]; //先假设a[i]的存在对bx值没有贡献。 p = max(pos[a[i]-1], pos[a[i]+1]); //找到a[i]+1 or a[i]-1 的下标， 都不存在时， p为0。 dp[i] += i-p-1; //对于以a[i]为结尾的，且不存在a[i]+1 or a[i]-1的子序列，a[i]的存在能增加一对，这样的序列有i-p-1对。 //由于只出现一个时， 对dp[i]没有影响， 所以跳过 //如果a[i]+1 and a[i]-1 都存在 if(pos[a[i]-1] && pos[a[i]+1]) { p = min(pos[a[i]-1], pos[a[i]+1]); //找到下标最小的哪一个 dp[i] -= p; //对于以a[i]为结尾的，且a[i]+1 and a[i]-1都存在的子序列，a[i]的存在拆散了一对，这样的序列有p对。 } pos[a[i]] = i; //记录a[i]出现的位置 } LL ans = 0; for(int i = 1; i<=n; i++) ans += dp[i]; printf("%lld\n",ans); } int main() { int T; scanf("%d",&T); while(T--){ init(); solve(); } }容斥：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #include <sstream> #include <algorithm> using namespace std; #define pb push_back #define mp make_pair #define ms(a, b) memset((a), (b), sizeof(a)) #define eps 0.0000001 typedef long long LL; const int INF = 2e9; const LL LNF = 9e18; const int mod = 1e9+7; const int maxn = 100000+10; LL a[maxn], pos[maxn], dp[maxn]; int n; void init() { scanf("%d",&n); for(int i = 1; i<=n; i++) scanf("%lld",&a[i]), pos[a[i]] = i; } void solve() { LL ans = 0; for(int len = 2; len<=n; len++) ans += 1LL*(len-1)*(n-len+1); for(int i = 1; i<n; i++) { int pre = pos[i]; int next = pos[i+1]; if(pre>next) swap(pre, next); ans -= 1LL*pre*(n-next+1); } printf("%lld\n",ans); } int main() { int T; scanf("%d",&T); while(T--){ init(); solve(); } }