教育Codeforces轮41(额定Div。2)大肠Tufurama

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

题意： 一共有 $n$ Season TV,There are TV shows every season $a_i$ 集,有一天, Polycarp Want to search for the first $7$ 季第 $3$ 集时,Discovery can only search for the first $3$ 季第 $7$ 集.It was later discovered upon interrogation,如果搜索 $x$ 季 $y$ 集,Once it has appeared before $y$ 季 $x$ set then $x$ 季 $y$ The set can never be searched,给出 $n$ Season TV series and the number of episodes per season, Ask how many episodes exist but we couldn't search ？

思路： Because the number of episodes in each season will be less than the current one $a_i$ quarterly contribution,例如 $a_1=8$,那么如果 $2-8$ Season exists $1$ Sets will not be searchable then $1$ 集.那么第 $1$ Ji's contribution to the answer is that $8-2+1=7$ But if there are a few seasons without episodes $1$ 集,Then there will be no contribution,Then don't add it.So we can open a priority queue to store all numbers with the first key,The second key value is stored in the subscript.Once currently enumerated $i$ greater than the value of the top element of the heap,Then put the second key of the top element of the heap in the tree array $-1$ ,当用树状数组 $ask$ When the contribution of this element is naturally subtracted,直接开一个 $b$ Sorted array is equivalent to priority queue.

代码：

#include<bits/stdc++.h>
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;
}