Codechef SEAARC.Sereja and Arcs

· · 个人记录

不是很懂网上的补集转化题解是在淦什么……

正难则反的确很有道理啊……

但是有句话叫反难则正是不是……

根本没必要正难则反，直接正着做即可

题意相当简单，给你一个序列每个点有一些颜色，让你统计这样的4元组(a,b,c,d)的数目

1.a,b的颜色相同,c,d的颜色相同,并且(a,b)和(c,d)的颜色是不同的

2.a<c<b<d

换句话说就是同色点对之间会连一条圆弧，问你有多少对弧是相交的

直接做显然是没法做的，我们开始考虑把暴力拼到一起形成一个优秀的乱搞做法

我们是基于这样一个性质进行暴力拼合的，对于一个总数为n的序列，出现次数大于\sqrt{n}的颜色不会超过\sqrt{n}种

所以我们将所有的颜色分为两类，第一类是大颜色,也就是出现次数大于\sqrt{n}的颜色,第二类是小颜色,也就是出现次数小于\sqrt{n}的颜色

那么我们将所有的(a,b,c,d)四元组分为4类分别进行统计

1.大颜色-大颜色的四元组

2.大颜色-小颜色的四元组

3.小颜色-大颜色的四元组

4.小颜色-小颜色的四元组

那么我们分别统计这四类四元组就好了

暴力1

我们先来统计最好统计的第4类四元组

首先根据我也不知道为什么的一个推论是所有的小颜色-小颜色之间的点对数目是O(n\sqrt{n})的，那么我们就可以直接开始大力的暴力统计了，相当于对于每一个点对(a,b)求有多少个合法的点对(c,d)满足a<c<b<d这个东西是一个类似于2维偏序的东西，我们用树状数组搞一搞就可以了

第一个需要注意的事情就是我们如果用树状数组+扫描线来做这个东西的话我们就不要大力sort了(因为你发现你的限制条件是严格小于，你需要写一个非常恶心的写法才可以写出来)

我们不如直接枚举左端点，那么所有合法的右端点就是这个点右侧所有的同色点那么我们可以记一个nxt_{i}表示i右侧第一个同色点的位置，那么我们就可以像链表一样遍历所有合法的右端点(同时这样做的话我们就愉快的规避了严格小于的限制问题)

第二个需要注意的事情就是我们刚才会将同色点对相交的情况计数进去，因此我们需要额外容斥一发，假如某个颜色的出现次数是n,那么同色点对出现的 次数就是这个和式

\sum_{i=1}^{n}\sum_{j=1}^{i}(i-j-1)(j-1)

然后我懒得拆这个式子了就直接暴力容斥了

总之这样做我们可以在O(N\sqrt{N}logN)的时间内算出所有的第4类点对数目

暴力2

现在让我们来想一个精妙的算法来处理剩余的几类点对关系

我们发现另外的几类点对都和大颜色有关，因此让我们来尝试O(\sqrt{N}) 的枚举大颜色,考虑这种颜色和其他颜色的关系,这样我们就可以在O(N\sqrt{N})的时间内解决这个问题

那怎么办呢？

我们假设正在处理颜色a和其他所有颜色的关系

那么我们令pre_{i}表示(1~i)这段区间种颜色a出现的次数

接下来我们枚举所有合法4元组的d值(也就是最右边的点)

那么对于一个点i它的贡献就是

\sum_{j=1}^{i-1}[col_{j}==col_{i}](pre_{i}-pre_{j})pre_{j}

换句话就是说(i,j)和(1,j)这段区间内的颜色a可以自由匹配,限制i,j的颜色相等是为了符合题意要求

那么我们简单的拆一下式子会变成

\sum_{j=1}^{i-1}[col_{j}==col_{i}](pre_{i}pre_{j}-pre_{j}^{2})

那么我们的算法就变得非常简单了我们从左向右的扫一遍维护一下每种颜色的pre_{j}之和和pre_{j}^2之和就可以了

然后你写上去一交发现WA了

为什么呢？

我们发现刚才的算法只能统计大颜色-任意颜色的点对

那么所有大颜色-大颜色的点对会被左侧的颜色恰好统计一次,所有大颜色-小颜色的点对也会被统计一次

于是我们的小颜色-大颜色点对就被无视了……

解决这个问题也相当的简单，我们只需要反着扫一遍，枚举左端点a的时候如果a是一个大颜色就跳过就ok了

最后我们把暴力拼合到一起就可以得到一个高效算法辣~

本题中我们可以通过改变阈值使得复杂度被平衡至O(N\sqrt{NlogN})

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int S=250;typedef long long ll;const ll mod=1e9+7;
int n;int col[N];int cnt[N];ll res;ll sp[N];ll spp[N];int nxt[N];int tr[N];
inline void subsolve1(int co)
{
    for(int i=1;i<=1e5;i++)sp[i]=0;for(int i=1;i<=1e5;i++)spp[i]=0;int pre=0;
    for(int i=1;i<=n;i++)
    {
        if(col[i]==co){pre++;continue;}
        (res+=pre*sp[col[i]]+mod-spp[col[i]])%=mod;
        (sp[col[i]]+=pre)%=mod;(spp[col[i]]+=(ll)pre*pre)%=mod;
    }
    for(int i=1;i<=1e5;i++)sp[i]=0;for(int i=1;i<=1e5;i++)spp[i]=0;pre=0;
    for(int i=n;i>=1;i--)
    {
        if(col[i]==co){pre++;continue;}if(cnt[col[i]]>=S)continue;
        (res+=pre*sp[col[i]]+mod-spp[col[i]])%=mod;
        (sp[col[i]]+=pre)%=mod;(spp[col[i]]+=(ll)pre*pre)%=mod;
    }
}
struct treearray
{
    int ta[N];
    inline void c(int x){for(;x<=n;x+=x&(-x))ta[x]++;}
    inline int q(int x){int r=0;for(;x;x-=x&(-x))r+=ta[x];return r;}
}ta;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&col[i]),cnt[col[i]]++;
    for(int i=1;i<=1e5;i++)if(cnt[i]>=S)subsolve1(i);
    for(int i=1;i<=1e5;i++)tr[i]=n+1;
    for(int i=n;i>=1;i--)nxt[i]=tr[col[i]],tr[col[i]]=i;
    for(int i=1;i<=n;i++)
    {
        if(cnt[col[i]]>=S)continue;int nv=ta.q(i);
        for(int j=nxt[i];j!=n+1;j=nxt[j])(res+=ta.q(j-1)-nv)%=mod;
        for(int j=nxt[i];j!=n+1;j=nxt[j])ta.c(j);
    }
    for(int i=1;i<=1e5;i++)
    {
        if(cnt[i]>=S||cnt[i]==0)continue;
        for(int t=1;t<=cnt[i];t++)
            for(int j=0,p=t-2;j<=t-2;j++,p--)(res+=mod-p*j)%=mod;
    }
    printf("%lld",res);return 0;
}