day6

正睿提高

LZZ出的题！

T1 Tiny Counting

这里你需要解决一道微型计数题——关于人畜无害的四元组。
给定长度为 $n$ 的数组 $S$，下标为 $1 \sim n$，你需要统计有多少个四元组 $(a,b,c,d)$ 满足：$1 \leq a < b \leq n; 1 \leq c < d \leq n; S_a < S_b; S_c > S_d$，且 $a, b, c, d$ 互不相等。

容斥一下，首先求出所有$a < b$,和$c > d$的对数，两两组合，相乘。然后考虑去有相同数的情况。
一共四种情况：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200005;
struct BIT{
    int sum[N], n;
    void Clear() {
        memset(sum, 0, sizeof(sum));
    } 
    void update(int p,int v) {
        for (; p<=n; p+=(p&(-p))) sum[p] += v;
    }
    int query(int p) {
        int res = 0;
        for (; p; p-=(p&(-p))) res += sum[p];
        return res;
    }
    int Ask(int l,int r) {
        return query(r) - query(l - 1);
    }
}bit;
int a[N], b[N], Lx[N], Ld[N], Rx[N], Rd[N];
int main() {
    int n = read();
    bit.n = n;
    for (int i=1; i<=n; ++i) a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int cnt = 1;
    for (int i=2; i<=n; ++i) if (b[i] != b[cnt]) b[++cnt] = b[i];
    for (int i=1; i<=n; ++i) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    for (int i=1; i<=n; ++i) {
        Lx[i] = bit.Ask(1, a[i] - 1);
        Ld[i] = bit.Ask(a[i] + 1, n);
        bit.update(a[i], 1);
    }
    bit.Clear();
    for (int i=n; i>=1; --i) {
        Rx[i] = bit.Ask(1, a[i] - 1);
        Rd[i] = bit.Ask(a[i] + 1, n);
        bit.update(a[i], 1);
    }
//  for (int i=1; i<=n; ++i) cout << Lx[i] << " "; puts("");
//  for (int i=1; i<=n; ++i) cout << Ld[i] << " "; puts("");
//  for (int i=1; i<=n; ++i) cout << Rx[i] << " "; puts("");
//  for (int i=1; i<=n; ++i) cout << Rd[i] << " "; puts("");
    LL ans = 0, ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
    for (int i=1; i<=n; ++i) 
        ans1 += Rd[i], ans2 += Rx[i];
    ans = ans1 * ans2;
    ans1 = 0, ans2 = 0;
    for (int i=1; i<=n; ++i) {
        ans1 += (1ll * Lx[i] * Rx[i]);
        ans2 += (1ll * Ld[i] * Rd[i]);
        ans3 += (1ll * Lx[i] * Ld[i]);
        ans4 += (1ll * Rx[i] * Rd[i]);
    }
    ans = ans - ans1 - ans2 - ans3 - ans4;
    cout << ans;
    return 0;
}

T2 Medium Counting

这里你需要解决一道中型计数题——关于捉摸不定的字典序。
有 $n$ 个字符串，分别记为 $S_1, S_2, \cdots, S_n$，它们由小写字母和 $?$ 组成，你需要给每个 $?$ 都填上一个小写字母。
你需要统计，有多少种不同的给 $?$ 填上字母的方法，使得对于每个 $i \in [1, n-1]$，$S_i$ 的字典序严格小于 $S_{i+1}$ 的字典序。