codeforces 261 D

題目鏈接：

解題報告：給出一個序列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             else
54             {
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             else
64             {
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

轉載于:https://www.cnblogs.com/xiaxiaosheng/p/3916290.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/376739.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/376739.shtml
英文地址，請注明出處：http://en.pswp.cn/news/376739.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！