异色弧

Time Limit: 20 Sec  Memory Limit: 256 MB

Description

　　

Input

　　

Output

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

Sample Input

　　8

　　1 2 3 1 2 3 2 1

Sample Output

　　8

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

1 #include
      
           2 #include
       
            3 #include
        
             4 #include
         
              5 #include
          
               6 #include
           
             7 #include
            
              8 using namespace std; 9 10 typedef long long s64; 11 const int ONE = 100010; 12 const int MOD = 1e9+7; 13 14 vector 
             
               q[ONE]; 15 16 int n; 17 int A[ONE]; 18 int cnt,Ans; 19 int Max,vis[ONE]; 20 int Jc[ONE],inv[ONE]; 21 22 struct power 23 { 24 int l,r; 25 }a[20000001]; 26 27 bool cmp(const power &a,const power &b) 28 { 29 if(a.r == b.r) return a.l > b.l; 30 return a.r < b.r; 31 } 32 33 void Moit(int &a) 34 { 35 if(a
              
               MOD) a-=MOD; 37 } 38 39 int get() 40 { 41 int res=1,Q=1; char c; 42 while( (c=getchar())<48 || c>57) 43 if(c=='-')Q=-1; 44 if(Q) res=c-48; 45 while((c=getchar())>=48 && c<=57) 46 res=res*10+c-48; 47 return res*Q; 48 } 49 50 namespace D 51 { 52 int Quickpow(int a,int b) 53 { 54 int res=1; 55 while(b) 56 { 57 if(b&1) res=(s64)res*a%MOD; 58 a=(s64)a*a%MOD; 59 b>>=1; 60 } 61 return res; 62 } 63 64 void Deal_Jc(int k) 65 { 66 Jc[0]=1; 67 for(int i=1;i<=k;i++) Jc[i] = (s64)Jc[i-1]*i%MOD; 68 } 69 70 void Deal_inv(int k) 71 { 72 inv[0]=1; inv[k] = Quickpow(Jc[k],MOD-2); 73 for(int i=k-1;i>=1;i--) inv[i] = (s64)inv[i+1]*(i+1)%MOD; 74 } 75 76 void pre(int k) 77 { 78 Deal_Jc(k); Deal_inv(k); 79 } 80 } 81 82 int C(int n,int m) 83 { 84 if(n < m) return 0; 85 return (s64)Jc[n]*inv[m]%MOD*inv[n-m]%MOD; 86 } 87 88 namespace Bit 89 { 90 int C[ONE]; 91 92 int lowbit(int x) 93 { 94 return x&-x; 95 } 96 97 void Add(int R,int x) 98 { 99 for(int i=R;i<=n;i+=lowbit(i))100 C[i]+=x, Moit(C[i]);101 }102 103 int Query(int R)104 {105 int res=0;106 for(int i=R;i>=1;i-=lowbit(i))107 res+=C[i], Moit(res);108 return res;109 }110 }111 112 int main()113 { 114 n=get(); D::pre(n+1);115 for(int i=1;i<=n;i++)116 {117 A[i]=get();118 q[A[i]].push_back(i);119 Max=max(Max,A[i]); 120 }121 for(int k=1;k<=Max;k++)122 {123 if(!q[k].size()) continue;124 Ans-=C(q[k].size(),4); Moit(Ans);125 for(int i=0;i< q[k].size();i++)126 for(int j=i+1;j< q[k].size();j++)127 a[++cnt].l=q[k][i], a[cnt].r=q[k][j];128 }129 130 sort(a+1,a+cnt+1,cmp);131 for(int i=1;i<=cnt;i++)132 {133 Ans += Bit::Query(a[i].l-1);134 Moit(Ans);135 Bit::Add(a[i].l,1), Bit::Add(a[i].r-1,-1);136 }137 138 printf("%d",Ans); 139 }