Tufurama

直接按题意模拟计数即可,拿个单调栈和树状数组维护下...
题目不是求二元组的数量吗?i<j&&ai>=j&&aj>=i.
这是一个二维问题对吧,我们一维一维的解决.首先对于ai>n的直接取n就好,因为n一定是满足条件的.
然后我们令val和id,字面意思呐.我们都排序一下,对于原数组按val升序排序.当然在排序之前,我们需要存下它的值对吧,因为我们后面要枚举的.
后面枚举的话也是一个一个处理的,我们考虑枚举i=1到n.然后对于每个i判断下ai这个位子合法的数量,我们很容易知道,假如aj<i当前,那么这个j就不可能作为贡献,且以后也不会成为贡献.这个j就可以在树状数组中删除.然后对于其他的,直接query(a[i])即可.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
struct vv{
    ll id,val;
}a[N];
bool cmp(vv x,vv y)
{
    return x.val<y.val;
}
ll n,ca[N],sum[N],vis[N];
ll lowbit(ll x) { return x&(-x); }
void add(ll pos,ll val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}

ll query(ll pos)
{
    ll res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }return res;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].val);
        a[i].id=i;
        ca[i]=min(a[i].val,n);
        add(i,1);
    }
    sort(a+1,a+1+n,cmp);
    ll ans=0;
    for(int i=1,num=1;i<=n;i++)
    {
        if(!vis[i]) {add(i,-1);vis[i]=1;};//假如这个数没有被淘汰.就淘汰它.
        while(num<=n&&i>a[num].val)
        {
            if(!vis[a[num].id]) add(a[num].id,-1),vis[a[num].id]=1;
            num++;
        }
        ans+=query(ca[i]);
    }
    printf("%lld\n",ans);
    return 0;
}