2017华南理工华为杯H bx值（容斥问题）

jarod8016b

题目描述


　　对于一个nnn个数的序列 a1,a2,⋯,ana_1,a_2,\cdots,a_na​1​​,a​2​​,⋯,a​n​​，从小到大排序之后为ap1,ap2,⋯,apna_{p_1},a_{p_2},\cdots,a_{p_n}a​p​1​​​​,a​p​2​​​​,⋯,a​p​n​​​​，定义它的 bxbxbx 值为满足 api≠api−1+1,1<i≤na_{p_i} \neq a_{p_{i-1}}+1, 1 < i \leq na​p​i​​​​≠a​p​i−1​​​​+1,1<i≤n 的 iii 的个数。
　　给定 nnn 个数的一个排列，你需要计算它所有连续子序列的 bxbxbx 值之和。

输入格式


　　输入第一行包括一个正整数 TTT，表示数据组数。
对于每组数据，第一行一个整数 nnn，第二行 nnn 个整数，表示 nnn 个数的一个排列。
1≤T≤201 \leq T \leq 201≤T≤20
1≤n≤1000001 \leq n \leq 1000001≤n≤100000
1≤ai≤n1 \leq a_i \leq n1≤a​i​​≤n

输出格式


　　对每组数据输出一个整数表示答案。

样例数据


　　输入

2
3
1 2 3
4
3 1 4 2
　　输出

0
5

备注
　　题解：
　　先计算每个长度为 i 的连续子串的时候的全部bx值：（i-1个）， 每一个i有（n-i+1)个方案可以选择。 所以ans = ∑(n-i+1)*(i-1)。（1≤i≤n)。
　　然后就需要减去不合法的情况。就是找出相邻2个值在的连续子串。
　　我们就需要将a的值记录一下相应的位置。eg. a[3] = 6, a[6] = 7。所以我们需要将包含a[3]和a[6]的子串，每一个子串都减去1个。
　　而包含a[3]和a[6]的子串有:(n-6+1)个从1开始包含这两个数的子串，而且在这些字串中从1～3一共又有3个不同开头相同结尾的子串。所以一共就是：(n-6+1)*3。
　　推广一下：每2个相邻度的数，在a串中会有2个位置，一个在前面pre，一个在后面back， （n-back+1）*(pre)。ans 就需要减掉这些。





#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int a[maxn];
int c[maxn];
void init()
{

}
void solve()
{
     int n;
     LL ans = 0;
     scanf("%d", &n);
     for(int i = 1;i<=n;i++) scanf("%d", &a);
     for(int i = 1;i<=n;i++){
         c[a] = i;
         ans += 1LL*(n-i+1)*(i-1);
     }
     for(int i = 1;i<n;i++){
         int pre = c;
         int next = c[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();
     }
     return 0;
}
View Code　　你努力的时候，比你厉害的人也在努力。