【Foreign】异色弧 [树状数组]

　　异色弧

Time Limit: 20 Sec Memory Limit: 256 MB

Description

Input

Output

　　仅一行一个整数表示答案。

Sample Input

　　8
　　1 2 3 1 2 3 2 1

Sample Output

HINT

Main idea

　　给定若干个点，每个点有一个颜色，颜色一样的可以组成一个区间，询问有几个交。

Solution

　　BearChild只会70分的做法，记录N表示区间个数，效率为O(Nlog(N))。这里介绍一下。

　　我们基于将所有区间提取出来计算，可以用一个vector存一下记录相同颜色的，然后相同颜色的任意组合即可组成可行的区间。

　　首先我们考虑容斥：颜色不同的相交个数 = 不考虑颜色的总相交个数 - 颜色相同的相交个数。然后我们分段来解：

　　1. 不考虑颜色的总相交个数：
　　　　我们考虑带log的算法，先将所有区间按照右端点（细节：若相同则将左端点大的放在前面，保证不会算入答案）排序，然后顺序往后做，每次用树状数组在区间左端点+1，区间(右端点-1)处-1（细节：右端点-1处是为了处理前一个的右端点=这一个的左端点情况），然后每次只要查询(左端点-1)的前缀和，显然就是在这个区间前和这个区间的交的个数。这样我们就可以计算出总相交个数了。

　　2.颜色相同的相交个数：
　　　　我们考虑如何计算颜色相同的相交个数，设a表示一个颜色的个数，显然个数就是：C(a,4)。也就是任意4个相同颜色点可以组成一个交。

　　然后我们相减一下，就可以得到答案啦。注意一下细节。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<vector>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int MOD = 1e9+;

 vector <int> q[ONE];

 int n;

 int A[ONE];

 int cnt,Ans;

 int Max,vis[ONE];

 int Jc[ONE],inv[ONE];

 struct power

 {

         int l,r;

 }a[];

 bool cmp(const power &a,const power &b)

 {

         if(a.r == b.r) return a.l > b.l;

         return a.r < b.r;

 }

 void Moit(int &a)

 {

         if(a<MOD) a+=MOD;

         if(a>MOD) a-=MOD;

 }

 int get()

 {

         int res=,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 namespace D

 {

         int Quickpow(int a,int b)

         {

             int res=;

             while(b)

             {

                 if(b&) res=(s64)res*a%MOD;

                 a=(s64)a*a%MOD;

                 b>>=;

             }

             return res;

         }

         void Deal_Jc(int k)

         {

             Jc[]=;

             for(int i=;i<=k;i++) Jc[i] = (s64)Jc[i-]*i%MOD;

         }

         void Deal_inv(int k)

         {

             inv[]=;    inv[k] = Quickpow(Jc[k],MOD-);

             for(int i=k-;i>=;i--) inv[i] = (s64)inv[i+]*(i+)%MOD;

         }

         void pre(int k)

         {

             Deal_Jc(k);    Deal_inv(k);

         }

 }

 int C(int n,int m)

 {

         if(n < m) return ;

         return (s64)Jc[n]*inv[m]%MOD*inv[n-m]%MOD;

 }

 namespace Bit

 {

         int C[ONE];

         int lowbit(int x)

         {

             return x&-x;

         }

         void Add(int R,int x)

         {

             for(int i=R;i<=n;i+=lowbit(i))

                 C[i]+=x, Moit(C[i]);

         }

         int Query(int R)

         {

             int res=;

             for(int i=R;i>=;i-=lowbit(i))

                 res+=C[i], Moit(res);

             return res;

         }

 }

 int main()

 {

         n=get();    D::pre(n+);

         for(int i=;i<=n;i++)

         {

             A[i]=get();

             q[A[i]].push_back(i);

             Max=max(Max,A[i]);

         }

         for(int k=;k<=Max;k++)

         {

             if(!q[k].size()) continue;

             Ans-=C(q[k].size(),);    Moit(Ans);

             for(int i=;i< q[k].size();i++)

             for(int j=i+;j< q[k].size();j++)

                 a[++cnt].l=q[k][i], a[cnt].r=q[k][j];

         }

         sort(a+,a+cnt+,cmp);

         for(int i=;i<=cnt;i++)

         {

             Ans += Bit::Query(a[i].l-);

             Moit(Ans);

             Bit::Add(a[i].l,), Bit::Add(a[i].r-,-);

         }

         printf("%d",Ans);

 }

巴特西