题解：P11197 [COTS/CETS 2021] 赛狗游戏 Tiket

fzitb7912 · 2024-10-17 14:27:19 · 题解

题解摘自 CSP2024 前做题情况。

参考文献，云浅老师好强。 /bx/bx/bx

分析

发现条件 1 没有什么用。令 a_i 为 i 在 P(1) 中的位置；b_i 为 i 在 P(2) 中的位置；c_i 为 i 在 P(3) 中的位置。若满足 a_i < a_j \land b_i < b_j \land c_i <c_j ，且 T 中 i 在 j 前面，则满足条件。若此时 T 中 i 在 j 后面，那么就可以把 i,j 交换一下，也满足条件。

所以原题就是求满足：a_i <a_j\land b_i < b_j\land c_i<c_j 的二元组 (i,j) 的数量。这是一个三位偏序的板子，使用 CDQ 分治可以做到 O(n \log^2 n)。需要细微卡常，但是能过。

在这里介绍一下时间复杂度为 O(n\log n) 的算法。该算法带了一个 3 倍的常数，不过不影响。我们考虑把一个三维偏序问题转化为 3 个二维偏序问题的交。令 S_1=\{(i,j)|a_i<a_j\},S_2=\{(i,j)|b_i<b_j\},S_3=\{(i,j)|c_i<c_j\}。那么有答案集合 S=S_1\cap S_2\cap S_3，则 (i,j) 的数量为 |S_1\cap S_2\cap S_3|。根据容斥有：|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-|S_1\cup S_2\cup S_3|}{2}。其中 S_1,S_2,S_3 分别能够算出来，难点在于维护 |S_1\cup S_2\cup S_3|。这里需要一点注意力。

对于一对 (i,j)，我们会发现若它们满足一维偏序，则 (j,i) 满足二维偏序；若它们满足二维偏序，则 (j,i) 满足一维偏序；若它们满足三维偏序，则 (j,i) 不满足任何偏序。而 S_1,S_2,S_3 中任何一对 (i,j) 至少满足二维偏序。所以 |S_1\cup S_2\cup S_3| 刚好是无序二元组 (i,j) 的数量，即 \frac{n\times (n-1)}{2}。

所以原式子可以写成：|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-\frac{n\times(n-1)}{2}}{2}。所以只需要算出来 |S_1\cap S_2|,|S_2\cap S_3|,|S_3\cap S_1| 就能求解三维偏序问题了。时间复杂度 O(n\log n)。

代码

il void solve(){
    n=rd;int ans=0;
    for(re int i=1;i<=n;++i) rd;
    for(re int i=1;i<=n;++i) a[rd]=i;
    for(re int i=1;i<=n;++i) b[rd]=i;
    for(re int i=1;i<=n;++i) c[rd]=i;

    for(re int i=1;i<=n;++i) d[a[i]]=b[i];
    for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
    for(re int i=1;i<=n;++i) tr[i]=0;

    for(re int i=1;i<=n;++i) d[b[i]]=c[i];
    for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
    for(re int i=1;i<=n;++i) tr[i]=0;

    for(re int i=1;i<=n;++i) d[c[i]]=a[i];
    for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
    for(re int i=1;i<=n;++i) tr[i]=0;

    printf("%lld\n",(ans-n*(n-1)/2)/2); 
    return ;
}