CF459D Pashmak and Parmida's problem (树状数组)

时间:2023-02-01 22:18:12

 

Codeforces Round #261 (Div. 2)

 

 

题意:给出数组A,定义f(l,r,x)为A[]的下标l到r之间,等于x的元素数。i和j符合f(1,i,a[i])>f(j,n,a[j]),求i和j的种类数。

题解:使用树状数组统计小于某数的元素数量。

我们可以先把f(1,i,a[i])和f(j,n,a[j])写出来,观察一下,例如样例1:

n=7

A  1  2  1  1  2  2  1

R  4  3  3  2  2  1  1

L  1  1  2  3  2  3  4

其中A为给定的数组,Rj为f(j,n,a[j]),Li为f(1,i,a[i])。

对每个Li,我们要统计的其实就是符合(j>i,且Rj<Li)的Rj的个数。就是这个Li右边有多少个比它小的Rj。

这样我们可以用树状数组,把Rj各个数的数量全存到树状数组里,例如这个样例就是4有1个,3有2个,2有2个,1有2个。然后从左到右遍历Li,每次从树状数组里删掉Rj,并且求sum(Li-1),也就是树状数组中1~Li-1的和,也就是比Li小的元素个数。

例如这个样例,到L3时,树状数组里记了2个1和2个2(1个4和2个3在之前被删掉了),L3=2,则sum(L3-1)=sum(2)=1的数量+2的数量=3。ans+=3。

核心代码(b和d是map,用来统计元素个数,超碉):

 1 ll farm(){
 2     int i;
 3     ll re=0;
 4     b.clear();d.clear();
 5     REPD(i,n){
 6         b[a[i]]++;
 7         update(b[a[i]],1);
 8     }
 9     REP(i,n){
10         d[a[i]]++;
11         update(b[a[i]],-1);
12         b[a[i]]--;
13         re+=sum(d[a[i]]-1);
14         //cout<<i<<' '<<d[a[i]]-1<<' '<<sum(d[a[i]]-1)<<' '<<re<<endl;
15     }
16     return re;
17 }

 

全代码:

CF459D Pashmak and Parmida's problem (树状数组)CF459D Pashmak and Parmida's problem (树状数组)
 1 //#pragma comment(linker, "/STACK:102400000,102400000")
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<cmath>
 8 #include<map>
 9 #include<set>
10 #include<stack>
11 #include<queue>
12 using namespace std;
13 #define ll long long
14 #define usll unsigned ll
15 #define mz(array) memset(array, 0, sizeof(array))
16 #define minf(array) memset(array, 0x3f, sizeof(array))
17 #define REP(i,n) for(i=0;i<(n);i++)
18 #define REPD(i,n) for(i=(n)-1;i>=0;i--)
19 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
20 #define RD(x) scanf("%d",&x)
21 #define RD2(x,y) scanf("%d%d",&x,&y)
22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
23 #define WN(x) prllf("%d\n",x);
24 #define RE  freopen("D.in","r",stdin)
25 #define WE  freopen("1biao.out","w",stdout)
26 #define mp make_pair
27 const int maxn=1123456;
28 ll c[maxn];
29 int a[maxn];
30 int n;
31 
32 int lowbit(int x){
33     return x&-x;
34 }
35 
36 void update(int x,int y){
37     if(!x)return;
38     while(x<=n){
39         c[x]+=y;
40         x+=lowbit(x);
41     }
42 }
43 
44 ll sum(int x){
45     ll re=0;
46     while(x>0){
47         re+=c[x];
48         x-=lowbit(x);
49     }
50     return re;
51 }
52 
53 map<int,int> b,d;
54 
55 ll farm(){
56     int i;
57     ll re=0;
58     b.clear();d.clear();
59     REPD(i,n){
60         b[a[i]]++;
61         update(b[a[i]],1);
62     }
63     REP(i,n){
64         d[a[i]]++;
65         update(b[a[i]],-1);
66         b[a[i]]--;
67         re+=sum(d[a[i]]-1);
68         //cout<<i<<' '<<d[a[i]]-1<<' '<<sum(d[a[i]]-1)<<' '<<re<<endl;
69     }
70     return re;
71 }
72 
73 int main(){
74     int i;
75     scanf("%d",&n);
76     REP(i,n) scanf("%d",&a[i]);
77     printf("%I64d\n",farm());
78     return 0;
79 }
View Code