CF961E

· · 题解

题意

给你一个数组，求 i,j 满足：

题解思路

读入的时候，因为 j \le n 所以当 a_i > n 时，我们把 a_i 变成 n 就可以了。

然后我们可以用一个 vector 来维护 (1) 和 (3) 的最大可能值。

那么我们设 v_i 表示最大可能为 i 的数的下标是多少。

那么最大可能值就是 i - 1 与 a_i 取个最小值就行了。

因为 x \le a_y 所以一种最大的可能就是 x=a_y，另一种就是 i - 1，因为 x < y 所以 x 的最大值就是 y - 1。

然后就枚举 i，然后对于每个 i 枚举对应的 v_i，然后答案就加上 i - \sum_{a_i < v_j}。

AC CODE:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int &read(int &r){//快读
    r=0;bool w=0;char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
    return r=w?-r:r;
}
int n;
int a[N];
vector<int> v[N];//表示i最大的x是多少
template<class T>
struct BIT {//树状数组模板
    T c[N];
    void modify(int x, T d) {
        if (x <= 0) return;
        for (; x <= n; x += (x & -x))
            c[x] += d;
    }
    T query(int x) {
        T res = 0;
        for (; x; x -= (x & -x))
            res += c[x];
        return res;
    }
};
BIT<ll> c;
int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        a[i] = min(a[i], n);
        v[min(i - 1, a[i])].push_back(i);
        //因为要满足i>j那么i最大就是j-1,且i<=a[j]，所以还要与a[j]取个最小值
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        c.modify(a[i], 1);
        for (auto t : v[i]) {
            ans += i - c.query(t - 1);//答案加上总数- x<a[x]的数的个数
        }
    }
    printf("%lld\n", ans);
    return 0;
}