首页 > 代码库 > codeforces 261 D

codeforces 261 D

2024-07-17 21:55:49   216人阅读

题目链接：

解题报告：给出一个序列a1,a2,a3.........an，f(i , j ,x) ak 等于x的个数(i <= k <= j)，令i < j，求有多少对 i 和 j 使得 f(1,i,ai) > f(j,n,aj)。

从左往右扫一遍这个序列，num1[i] 等于从1到i有多少个等于a[i]的，同理从右往左扫一遍得到num2[i]，然后把从右往左扫的num2[i]的个数用一个树状数组维护，先全部加到树状数组里面去，然后从左往右扫一遍num1[i]，每次判断在num2中有多少个小于num1[i]的数，同时判断完之后要把对应的num2[i]的个数减去1，因为这时候num1[i]的位置已经超过这个num2的位置了，所以以后的算个数的时候这个num2[i]不能算进去，应该删掉。用树状数组的目的就是为了能快速判断num2[i]中有多少个小于num1[i]的，这样可以做到在log2(n)的时间内完成查找和删除操作。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<map> 5 #include<algorithm> 6 using namespace std; 7 #define LL long long 8 #define maxn 1000005 9 LL n,tot;10 map<LL,LL> mp1,mp2;11 LL a[maxn],num1[maxn],num2[maxn],num3[maxn];12 LL tree[maxn];13 LL find(LL d,int l,int r)14 {15     while(l < r)16     {17         int mid = (l + r) / 2;18         if(d <= num1[mid]) r = mid;19         else l = mid + 1;20     }21     if(num1[l] != d) return l - 1;22     else return l;23 }24 void insert(int l,int d)25 {26     for(int i = l;i <= n;i += (-i & i))27     tree[i] += d;28 }29 LL sum(int l)30 {31     LL tot = 0;32     for(int i = l;i > 0;i -= (-i & i))33     tot += tree[i];34     return tot;35 }36 37 int main()38 {39     40     while(scanf("%lld",&n)!=EOF)41     {42         for(int i = 1;i <= n;++i)43         scanf("%lld",&a[i]);44         memset(tree,0,sizeof(tree));45         memset(num1,0,sizeof(num1));46         memset(num2,0,sizeof(num2));47         mp1.clear();48         mp2.clear();49         for(int i  = 1;i <= n;++i)50         {51             if(mp1.insert(pair<LL,LL> (a[i],1)).second == 1)52             num1[i] = 1;53             else54             {55                 mp1[a[i]] = mp1[a[i]] + 1;56                 num1[i] = mp1[a[i]];57             }58         }59         for(int i = n;i >= 1;--i)60         {61             if(mp2.insert(pair<LL,LL> (a[i],1)).second == 1)62             num2[i] = 1;63             else64             {65                 mp2[a[i]] = mp2[a[i]] + 1;66                 num2[i] = mp2[a[i]];67             }68         }69         for(int i = 1;i <= n;++i)70         insert(num2[i],1);71         tot = 0;72         for(int i = 1;i <= n;++i)73         {74             insert(num2[i],-1);75             tot += sum(num1[i]-1);76         }77         printf("%lld\n",tot);78     }79     return 0;80 }
View Code

 


联系
我们