Menu
Article

【JZOJ 5951】锋芒毕露 / 题解

Zepto

Zepto

• 2 min read

题目描述

在二维平面上有 $n$ 个点，第 $i$ 个点的位置为 $(i, \ 0)$ ，第 $i$ 个点的颜色为 $a_i$。
两个颜色相同的点 $A$ 和 $B$ 会产生一个以 $AB$ 为直径的圆，该圆的颜色和这两个点的颜色相同，求有多少对颜色不同的圆相交。

思路

这里是官方题解。

其实没有官方讲得那么复杂啦。。。我们大力简化这个问题，先直接寻找所有相交的圆，再减去相交的同色圆个数。我们首先记录对于每个位置，下一个同色点出现的位置。那么我们从左到右枚举每条可能的直径，计算左右端点之间，越过端点的另一条直径的数量。

具体实现，我们开一个树状数组，记录每个位置作为右端点可以构成几个圆。对于一个新增的点，它对右边每一个同色点的贡献都是 1，单点修改即可；更新答案其实就是区间求和。

注意一个小细节，为了避免出现如图的情况被误记录，我们在每次查询前减去这种颜色的数量即可。

代码

#include <bits/stdc++.h>
#define md 19260817
#define maxn 666667
#define inv 18458283
using namespace std;
inline int inc(int &a,int b){a=(a+b>=md?a+b-md:a+b);}
inline int dec(int &a,int b){a=(a-b<0?a-b+md:a-b);}
int a[maxn],t[maxn],cnt[maxn],head[maxn],next[maxn],ans,n;
inline void add(int a,int b){while(a<=n)t[a]+=b,a+=(a&-a);}
inline int sum(int a){int r=0;while(a)r+=t[a],a-=(a&-a);return r;}
int main(){
    scanf("%d",&n);
    for (register int i=1;i<=n;++i)
        scanf("%d",a+i),
        next[head[a[i]]]=i,head[a[i]]=i;
    for (register int i=1;i<=n;++i){
        add(i,-cnt[a[i]]),cnt[a[i]]++;
        for (register int j=next[i];j;j=next[j])
            inc(ans,sum(j-1));
        for (register int j=next[i];j;j=next[j])
            add(j,1);
    }
    for (register int i=1;i<=n;++i) if (cnt[i]>3)
        dec(ans,1ll*cnt[i]*(cnt[i]-1)%md*(cnt[i]-2)%md*(cnt[i]-3)%md*inv%md);
    printf("%d\n",ans);
}

And in the end, the love you take, is equal to the love you make.

Share