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; } ``` ``` ```