Tiny Counting[计数]

$TinyCounting$Tiny   Counting

Description

样例输入:
4
1 4 3 2
样例输出:
3

Solution

对每个数字 $S_i$Si​, 可以将其在二维平面上表示 $\downarrow$↓

如图得到 $S_i$Si​ 与其他数字的 位置 与 值 的大小关系

1. 第一象限 的数字与 $S_i$Si​ 构成以 $S_i$Si​ 为 第二项的 顺序对
2. 第二象限 的数字与 $S_i$Si​ 构成以 $S_i$Si​ 为 第二项的 逆序对
3. 第三象限 的数字与 $S_i$Si​ 构成以 $S_i$Si​ 为 第一项的 逆序对
4. 第四象限 的数字与 $S_i$Si​ 构成以 $S_i$Si​ 为 第一项的 顺序对

每个数字都有 四个象限数字数量 的信息,
树状数组 维护各象限的 数字数量, 时间复杂度 $O(N\ast logN)$O(N∗logN)

接下来是 计算答案 的方法

$a$a 与 $b$b 是顺序对, 数量为 $su{m}_1$sum1​, $c$c 与 $d$d 是逆序对, 数量为 $su{m}_2$sum2​ .

$令Temp=su{m}_1\ast su{m}_2$令 Temp=sum1​∗sum2​, $Temp$Temp 为总方案数量, 包括不合法方案 ( $a,b,c,d$a,b,c,d 重复的方案) .

在使用 $Temp$Temp 逐个减去 不合法方案 :

1. $a=c=S_i$a=c=Si​, 此时 $b$b 为 第四象限, $d$d 为 第三象限 .
2. $a=d=S_i$a=d=Si​, 此时 $b$b 为 第四象限, $c$c 为 第二象限 .
3. $b=c=S_i$b=c=Si​, 此时 $a$a 为 第一象限, $d$d 为 第三象限 .
4. $b=d=S_i$b=d=Si​, 此时 $a$a 为 第一象限, $c$c 为 第二象限 .

$\therefore$∴ 对于 $S_i$Si​ ( $i\in [1,N]$i∈[1,N]), $Temp$Temp 需要减去

1. $L{U}_i\ast L{D}_i$LUi​∗LDi​ [ ( $a,b,c,d$a,b,c,d) $=$= ( $t_1,S_i,t_2,S_i$t1​,Si​,t2​,Si​) $t_1\in S_{Lu},t_2\in S_{Ld}$    t1​∈SLu​,  t2​∈SLd​ ]
2. $L{U}_i\ast R{U}_i$LUi​∗RUi​ […]
3. $L{D}_i\ast R{D}_i$LDi​∗RDi​ […]
4. $R{U}_i\ast R{D}_i$RUi​∗RDi​ […]

其中 $L,R$L,R 表示左, 右, $U,D$U,D 表示大, 小;
合起来共同表示符合条件的数字数量

统计答案 时间复杂度 $O\left(N\right)$O(N)
最后 $Temp$Temp 即是答案

Addition

Q: 为什么这样减去 不合法方案 会达到不重不漏的效果?
A: 这是因为每次减去的 不合法方案 都因 当前编号 重复而不合法,
在另一个位置时, 由于位置编号的唯一, 导致不合法的原因 一定不相同,
所以 不重不漏

Code

#include<bits/stdc++.h>
#define reg register

int read(){
        int s = 0, flag = 1;
        char c;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 1e5 + 50;
typedef long long ll;

int N;
int S[maxn];
int B[maxn];
int T[maxn];
int Lu[maxn], Ld[maxn];
int Ru[maxn], Rd[maxn];

void Modify(int k, int x){ while(k <= N) T[k] += x, k += k&-k; }
int Query(int k){ int s = 0; while(k > 0) s += T[k], k -= k&-k; return s; }
int Query_2(int l, int r){ return Query(r) - Query(l-1); }

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++) S[i] = read(), B[i] = S[i];
        std::sort(B+1, B+N+1);
        int Len = std::unique(B+1, B+N+1) - B-1;
        for(reg int i = 1; i <= N; i ++) S[i] = std::lower_bound(B+1, B+Len+1, S[i]) - B;
        for(reg int i = 1; i <= N; i ++){
                Ld[i] = Query_2(1, S[i]-1);
                Lu[i] = Query_2(S[i]+1, Len);
                Modify(S[i], 1);
        }
        memset(T, 0, sizeof T);
        for(reg int i = N; i >= 1; i --){
                Rd[i] = Query_2(1, S[i]-1);
                Ru[i] = Query_2(S[i]+1, Len);
                Modify(S[i], 1);
        }
        ll sgn_num = 0, ord_num = 0, illegal_num = 0;
        for(reg int i = 1; i <= N; i ++){
                sgn_num += Ru[i], ord_num += Rd[i];
                illegal_num += 1ll*Ru[i]*Rd[i] + 1ll*Ru[i]*Lu[i];
                illegal_num += 1ll*Ld[i]*Rd[i] + 1ll*Ld[i]*Lu[i];
        }
        printf("%lld\n", sgn_num*ord_num - illegal_num);
        return 0;
}