Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama

Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama

---

题意： 一共有 $n$ 季电视剧，每季电视剧有 $a_i$ 集，有一天， Polycarp 想要搜索第 $7$ 季第 $3$ 集时，发现只能搜索到第 $3$ 季第 $7$ 集。后来经讯问发现，如果搜索 $x$ 季 $y$ 集，一旦前面出现过 $y$ 季 $x$ 集那么 $x$ 季 $y$ 集永远无法搜索到，给出 $n$ 季电视剧以及每季的集数， 问有多少集是存在但我们搜索不到的 ？

---

思路： 因为每一季的集数都会对小于当前 $a_i$ 的季产生贡献，例如 $a_1=8$，那么如果 $2-8$ 季存在 $1$ 集那么都会搜索不到第 $1$ 集。那么第 $1$ 季对答案带来的贡献就是 $8-2+1=7$ 但是如果其中有几季没有第 $1$ 集，那么就无法产生贡献，那么就不用加上。因此我们可以开一个优先队列将所有数以第一关键字存值，第二关键值存下标存入。一旦当前枚举的 $i$ 大于堆顶元素的值，那么就将树状数组中堆顶元素的第二关键字 $-1$ ，当用树状数组 $ask$ 时也就自然减去了该元素带来的贡献，直接开一个 $b$ 数组排序后和优先队列等效。

---

代码：

#include
using namespace std;
#define int long long 
typedef pair<int,int>PII;
const int N = 2e5+10;
int a[N];
PII b[N];
int tr[N];
int n;
int lowbit(int x){return x&-x;}
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))tr[i]+=v;
}
int ask(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=tr[i];
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];b[i]={a[i],i};}
    sort(b+1,b+1+n);
    int cnt=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        while(cnt<=n&&b[cnt].first<i){
            add(b[cnt].second,-1);
            cnt++;
        }
        ans+=ask(min(i-1,a[i]));
        add(i,1);
    }
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36