Codeforces 961E - Tufurama

961E - Tufurama

思路：

线段树或者分块

遍历 1 - n - 1，求 区间[i + 1, min(a[i], n)]大于等于 i 的个数，累加起来

线段树：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define ls rt << 1, l, m

#define rs rt << 1 | 1, m + 1, r

#define mem(a, b) memset(a, b, sizeof(a))

const int N = 2e5 + ;

vector<int> vc[N<<];

int a[N];

void build(int rt, int l, int r) {

    if (l == r) {

        vc[rt].pb(a[l]);

        return ;

    }

    for (int i = l; i <= r; i++) vc[rt].pb(a[i]);

    sort(vc[rt].begin(), vc[rt].end());

    int m = l + r >> ;

    build(ls);

    build(rs);

}

int query(int L, int R, int rt, int l, int r) {

    if (L > R) return ;

    if (L <= l && r <= R) {

        return vc[rt].size()-(lower_bound(vc[rt].begin(), vc[rt].end(), L - ) - vc[rt].begin());

    }

    int ans = ;

    int m = l + r >> ;

    if (L <= m) ans += query(L, R, ls);

    if (R > m) ans += query(L, R, rs);

    return ans;

}

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    build(, , n);

    LL ans = ;

    for (int  i = ; i < n; i++) {

        ans += query(i + , min(a[i], n), , , n);

    }

    printf("%lld\n",ans);

    return ;

}

分块：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define mem(a, b) memset(a, b, sizeof(a))

const int N = 2e5 + ;

int a[N], block[], belong[N];

int blo;

vector<int> vc[];

int query(int L, int R){

    if (R < L) return ;

    int ans = ;

    if (belong[L] == belong[R]) {

        for (int i = L; i <= R; i++) {

            if (a[i] >= L - ) ans++;

        }

        return ans;

    }

    for (int i = L; i <= belong[L] * blo; i++){

        if (a[i] >= L - ) ans++;

    }

    for (int i = belong[L] + ; i <= belong[R] - ; i++) {

        ans += vc[i].size() - (lower_bound(vc[i].begin(), vc[i].end(), L - ) - vc[i].begin());

    }

    for (int i = (belong[R] - ) * blo + ; i <= R; i++) {

        if (a[i] >= L - ) ans++;

    }

    return ans;

}

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    blo = sqrt(n);

    for (int i = ; i <= n; i++) {

        belong[i] = (i - ) / blo + ;

    }

    for (int i = ; i <= n; i++) {

        vc[belong[i]].pb(a[i]);

    }

    for (int i = ; i <= belong[n]; i++) {

        sort(vc[i].begin(), vc[i].end());

    }

    LL ans = ;

    for (int i = ; i <= n - ; i++) {

        ans += query(i + , min(n, a[i]));

        //cout << ans << endl;

    }

    printf("%lld\n", ans);

    return ;

}