转自：https://blog.csdn.net/my_sunshine26/article/details/79831362
题目大意：
i从1开始
基本思路：
完全没思路，所以上来就二分，果不其然卡死在了第7个样例，然后认为是贪心，苦思冥想未果，然后就看了答案。
说是主席树模板题，但是可以用巧方法过了，大部分用的都是树状数组好像，然后想了想也没想出来用树状数组能好到那里去，
然后参考了下答案思路，嗯，这绝对不是我能想到的，难受，就很难受。
正确思路：
1.先记录满足i<=a[j]的最大下标idx(idx<j)，然后vec[idx].push_back(j)，这保证了第二个条件（下面的程序里处于习惯用的是i，实际上思维上是j）
2.然后依次在树状数组中插入a[i]，并查询满足a[i]>=j的j的个数。
3.为了利用树状数组，需要把a[i]压缩，因为大于n的a[i]等同于n
代码如下：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 200000+10;
const int inf = 0x3f3f3f3f;
int n;
ll arr[maxn],tree[maxn];
vector<int>vec[maxn];
ll lowbit(ll x){
return x&(-x);
}
ll query(int pos){
ll ans=0;
while(pos){
ans+=tree[pos];
pos-=lowbit(pos);
}
return ans;
}
void update(int pos,ll val){
while(pos<maxn){
tree[pos]+=val;
pos+=lowbit(pos);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%I64d",&arr[i]);
arr[i]=min(arr[i],(ll)n);
vec[min((ll)i-1,arr[i])].push_back(i);
}
ll ans=0;
for(int i=1;i<=n;i++){
update(arr[i],1);
int sz=vec[i].size();
for(int j=0;j<sz;j++){
int u=vec[i][j];
ans+=query(n)-query(u-1);
}
}
printf("%I64d
",ans);
return 0;
}