P4528 [CTSC2008] 图腾题解

UKBwyx · 2025-10-17 11:55:14 · 题解

来一个比较优雅的做法。

约定在 y 轴上红点和其他点间的相对高度是重要的，黑点和黑点间的相对高度是不重要的，在 x 轴上任意两点的相对位置都是重要的。

首先考虑这种怎么数。

这个可以用这种情况：

减掉这种情况得到。

然后观察剩下的两个，它们分别长这样：

这种每出现一个答案 +1。

这种每出现一个答案 -1。

观察发现这两种的区别在于第 4 个点的高度。

这启发我们把四排列计数换成三排列计数。

也就是，把四个点的贡献拆到三个点上。

对于这种情况：

只要它的剩下一个点在第一个点右上方并且不与这两个红点重复，就直接把答案 +1。

而对于另一种情况：

只要它的剩下一个点在第一个点右上方并且不与这两个红点重复，就直接把答案 -1。

此时应该使答案 +1 的实际上会使答案 +1，使答案 -1 的实际上会使答案 -3，可以对于每一个这样的东西，都将答案 +1。

然后就可以考虑对于第一个点右上方三个点的每一种排列，对答案的贡献是多少。

这种情况贡献是 1+1+1=3，3+1=4。

这种情况贡献是 1+1-1=1，1+1=2。

这种情况贡献是 1-1-1=-1，-1+1=0。

这种情况贡献是 -1-1-1=-3，-3+1=-2。

发现除了我们要算入答案的情况 3 和情况 6，剩下的，刚好是我们刚才算的情况 1 和情况 2，以及对答案没有影响的情况 4 和情况 5。

非常妙的一题，出题人巧妙地用了 A 类山峰图腾来给最后答案的计算做铺垫，并且使最后的答案不能算的部分的贡献恰好为 0，给出题人点了。

然后这道题到这里就做完了，只需要跑三遍扫描线，代码也是不难的。

这里贴上代码

#include<bits/stdc++.h>
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
using namespace std;
unsigned int n,a[200005],b[200005],d[200005],ans=0,sum=0,ans1=0,ans2=0;
struct szsz {
    unsigned int v[200005];
    inline void change(int wz,unsigned x) {
        for(; wz<=n; wz+=wz&-wz)v[wz]+=x;
    }
    inline unsigned int check(int wz,unsigned int res=0) {
        for(; wz; wz-=wz&-wz)res+=v[wz];
        return res;
    }
};
szsz c,c1,c2;
int main() {
//  freopen("d.in","r",stdin);
//  freopen("d.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        d[i]=c2.check(a[i]);
        c2.change(a[i],1);
    }
    for(int i=n; i>=1; i--) {
        b[i]=(n-i)-c.check(a[i]);
        unsigned int t=sum-c1.check(a[i]);
        ans+=(__int128)b[i]*(b[i]-1)*(b[i]-2)/6;
        if(b[i]>2) {
            ans+=2*t*(b[i]-2);
            ans-=b[i]*(b[i]-1)/2*(b[i]-2);
        }
        ans1+=t*d[i];
        ans2+=b[i]*(b[i]-1)/2*d[i];
        sum+=b[i];
        c1.change(a[i],b[i]);
        c.change(a[i],1);
    }
//  cout<<ans1<<" "<<ans2<<"???\n";
    ans2-=ans1;
    ans-=4*ans1;
    ans-=2*ans2;
    ans>>=1;
    ans-=ans2;
    cout<<ans%(1<<24);
    return 0;
}

P4528 [CTSC2008] 图腾 题解

P4528 [CTSC2008] 图腾题解