挺巧妙的數(shù)據(jù)結(jié)構(gòu)題（不過據(jù)說這是一種套路？

E. Tufurama

One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series "Tufurama". He was pretty surprised when he got results only for season 7 episode 3 with his search query of "Watch Tufurama season 3 episode 7 online full hd free". This got Polycarp confused — what if he decides to rewatch the entire series someday and won't be able to find the right episodes to watch? Polycarp now wants to count the number of times he will be forced to search for an episode using some different method.

TV series have?n?seasons (numbered?1?through?n), the?i-th season has?ai?episodes (numbered?1?through?ai). Polycarp thinks that if for some pair of integers?x?and?y?(x?<?y) exist both season?x?episode?y?and season?y?episode?x?then one of these search queries will include the wrong results. Help Polycarp to calculate the number of such pairs!

Input

The first line contains one integer?n?(1??≤?n??≤??2·10^5)?— the number of seasons.

The second line contains?n?integers separated by space?a1,?a2,?...,?an?(1?≤?ai?≤?10^9)?— number of episodes in each season.

Output

Print one integer — the number of pairs?x?and?y?(x?<?y) such that there exist both season?x?episode?y?and season?y?episode?x.

---

題目大意

有一部電視劇有n季，每一季有ai集。定義二元組(i,j)：存在第i季有第j集。求(i,j)與(j,i)同時(shí)合法(i<j)的對(duì)數(shù)。

真實(shí)題意就是：求<i,j>對(duì)數(shù)，使得a[i]≥j，a[j]≥i并且(i<j)

---

?看上去很可做的樣子，對(duì)吧……

題目分析

基礎(chǔ)的暴力

從1..n季，每一季都分別判斷對(duì)答案的貢獻(xiàn)。

例如對(duì)于?4 \n?3 5 1 2?，依次檢查(1,2)是否存在(2,1)；(1,3)是否存在(3,1)……

首先發(fā)現(xiàn)a[i]對(duì)于答案的貢獻(xiàn)最大也就是到n為止，那么讀入時(shí)候先取個(gè)min(n)。

考慮一下check()是O(n)的，所以總復(fù)雜度是O(n2)的。

BIT做法

像很多其他題一樣，對(duì)于這樣的、關(guān)于元素大小關(guān)系之間的限制的題目，先排個(gè)序總是能夠解決個(gè)一維限制掉去的。

我們使用一個(gè)結(jié)構(gòu)體node x，x.i表示季數(shù)；x.a表示該季的集數(shù)。首先對(duì)x.a排序。那么就變成這個(gè)樣子：

p[].a(j)　　3　　5　　1　　2
p[].i(i)　　1　　2　　3　　4
　　|
　　|
p[].a(j)　　1　　2　　3　　4 (取min之后)
p[].i(i)　　3　　4　　1　　2

先考慮每次的統(tǒng)計(jì)，那么只要ans+=query(a[i])就可以了。意思就是說ans加上1..a[i]季的貢獻(xiàn)（其中每一季的貢獻(xiàn)要么是0要么是1，但是由于之后會(huì)有修改，所以我們用BIT維護(hù)）

接著考慮修改，設(shè)立一個(gè)now指向當(dāng)前最小合法的p[]。這個(gè)now用來更新那些已經(jīng)?過氣?沒有貢獻(xiàn)的答案。

這里「沒有貢獻(xiàn)的答案」指的是p[now].a<i的情況。說人話就是p[now]的電視劇集數(shù)太小了，已經(jīng)不會(huì)再有貢獻(xiàn)了，因此now++，判斷下一個(gè)p[]是否可能會(huì)對(duì)答案有貢獻(xiàn)。個(gè)人感覺有那么一點(diǎn)相似 單調(diào)隊(duì)列 和 wqs二分 的情況（但是我不是非常清楚）？

為了去除這些沒有貢獻(xiàn)的季數(shù)的影響，我們只需將p[now].i位置在樹狀數(shù)組上-1即可。意思是說這個(gè)季數(shù)在之后的統(tǒng)計(jì)上都不會(huì)有貢獻(xiàn)了。

?

1 #include<bits/stdc++.h> 2 using namespace std; 3 long long ans; 4 int n,now,a[200035]; 5 struct node 6 { 7 int a,i; 8 bool operator < (node &xx) const 9 { 10 return a < xx.a; 11 } 12 }p[200035]; 13 int f[200035]; 14 int read() 15 { 16 char ch = getchar();int num = 0; 17 for (; !isdigit(ch); ch = getchar()); 18 for (; isdigit(ch); ch = getchar()) 19 num = (num<<3)+(num<<1)+ch-48; 20 return num; 21 } 22 int lowbit(int x){return x&-x;} 23 void add(int x, int c){for (; x<=n+1; x+=lowbit(x))f[x]+=c;} 24 int query(int x) 25 { 26 int ret = 0; 27 for (; x; x-=lowbit(x)) 28 ret += f[x]; 29 return ret; 30 } 31 int main() 32 { 33 n = read();now = 1; 34 for (int i=1; i<=n; i++) 35 a[i] = min(read(), n+1), p[i].a = a[i], p[i].i = i, add(i, 1); 36 sort(p+1, p+n+1); 37 for (int i=1; i<=n; i++) 38 { 39 while (now<=n && p[now].a < i)add(p[now++].i, -1); 40 ans += query(a[i]); 41 if (a[i] >= i)ans--; 42 } 43 cout << ans / 2 << endl; 44 return 0; 45 }

?

另附其他做法

其他人用BIT維護(hù)也挺巧妙的（但是我覺得初看時(shí)候有點(diǎn)云里霧里啊）

1.Educational Codeforces Round 41 E. Tufurama (961E)　　BIT做法

2.Codeforces 961E - Tufurama 【樹狀數(shù)組】　　BIT做法

3.Codeforces - 961E Tufurama　　set+BIT

4.CF 961E Tufurama　　跟我一樣的

?

?

END

?

轉(zhuǎn)載于:https://www.cnblogs.com/antiquality/p/8746718.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【树状数组】CF961E Tufurama的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。