D Pashmak and Pamida‘s problem’

2593 ワード
ツリー配列 データ構造
https://codeforces.com/problemset/problem/459/D
Pamida is a clever girl and s he wants to participad te in Olympiads this year.Of course she wants her partner to be clever too(although he's not)!Pashmak.
The re is a sequence a. that consists of n integers a. 1,̵a 2,̵…,̵a n.Let's denote f(l,̵r,̵x) the number of indices k such that: l̵≦̵k𔎅≦𔎅r and a. k̵=̵x.His task to calculate the number of pairs of indicies i,̵j (1̵≦̵i𔎅j𔎅≦̵n) such that f(1,̵i,̵a i)̵f(j,̵n,̵a j)
Help Pashmak with the test.
Input
The first line of the input contains an integer n (1̵≦̵n≦𔎅106).The second line contains n space-separated integers a. 1,̵a 2,̵…,̵a n (1̵≦̵a i̵≦𔎅109).
Output
Print a single integer-the answer to the proble.
Examples
input
Copy
7
1 2 1 1 2 2 1
out put
Copy
8
input
Copy
3
1 1 1
out put
Copy
1
input
Copy
5
1 2 3 4 5
out put
Copy
0
 
考え方:樹状配列は逆順の対を求める.
まずmapで求められているものを先に処理して、二つの求められているものを逆順を求めるものとします.逆順を求めてシミュレーションの過程をよく理解すると思います.あまりできないなら、luoguに行って逆順のボードの問題をしてもいいです.
シミュレーションの過程はブログから来ました.https://www.cnblogs.com/yuiffy/p/3916512.html
「
n=7
A 1 2 1 1 2 2 2 2 1 1 2 1 1
R 4 3 3 3 2 1
L 1 1 1 2 3 3 4
ここで、Aは所与の配列であり、Rjはf(j,n,a［j］)、Liはf(1,i,a［i］)である.
各Liに対して、私達が統計したいのは事実上(j＞iに合致し、Rj
  • である.
    このように、ツリー配列を使って、Rjの個数をすべてツリー配列に保存してもいいです.例えば、この例は4が1つあり、3が2つあり、2が2つあり、1が2つあります.そして左から右へLiを遍歴して、ツリー配列からRjを削除し、sum(Li-1)を求めます.つまり、ツリー配列の中の1～Li-1の和です.つまり、Liより小さい元素です.
    例えば、この例では、L 3になると、樹状配列に2つの1と2つの2つ(1つの4と2つの3が前に削除されました)が記録されています.L 3=2なら、sum(L 3-1)＝sum(2)＝1の数＋2の数＝3です.ans+=3です.
    」
    #include
#include
#include
#include
#include
#include
#include
#include
#include
#define debug(a) cout<map1,map2;
LL add(LL x,LL d){
	while(x<=n){
		tree[x]+=d;
		x+=lowbit(x);
	}
}
LL sum(LL x){
	LL ans=0;
	while(x>0){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n;
  for(LL i=1;i<=n;i++){
  	 cin>>a[i];
  }
  for(LL i=1;i<=n;i++){
  	f1[i]=++map1[a[i]];
  }
  for(LL i=n;i>=1;i--){
  	f2[i]=++map2[a[i]];
  }
  for(LL i=1;i<=n;i++){
  	add(f2[i],1);
  }
  LL res=0;
  for(LL i=1;i<=n;i++){
  	add(f2[i],-1);
  	res+=sum(f1[i]-1);
  }
  cout<
     
    • 黒馬プログラマ--集合フレーム(Collection、Iterator、泛型)