낙 곡 P1637 3 원 상승 서브 시퀀스 (나무 모양 배열 인 데 나 는 블록 을 나 누 려 고 한다)

#include 
using namespace std;

const int MAXN = 50100;
const int INF = 0x3f3f3f3f;

typedef pair pii;
#define X first
#define Y second

template  inline void read(T &x) {
    int c = getchar();
    bool fg = false;
    for (x = 0; !isdigit(c); c = getchar()) {
        if (c == '-') {
            fg = true;
        }
    }
    for (; isdigit(c); c = getchar()) {
        x = x * 10 + c - '0';
    }
    if (fg) {
        x = -x;
    }
}

int n, a[MAXN], L[MAXN], R[MAXN];
long long ans;
int b[MAXN], belong[MAXN], cnt[MAXN / 10], len, tot;
pii ref[MAXN];

int calc_small(int pos) {
    int x = pos / len + 1;
    int sml = 0, lim = (x - 1) * len;
    for(int i = 1; i < x; i++) sml += cnt[i];
    for(int i = lim; i < pos; i++) sml += b[i];
    return sml;
}

int calc_Big(int pos) {
    int x = pos / len + 1;
    int Big = 0, lim = min(x * len - 1, n);
    for(int i = 1 + x; i <= tot; i++) Big += cnt[i];
    for(int i = pos + 1; i <= lim; i++) Big += b[i];
    return Big;
}

signed main() {
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]), ref[i].X = a[i], ref[i].Y = i;
    sort(ref + 1, ref + n + 1);
    for(int i = 1; i <= n; i++) {
        if(ref[i].X != ref[i - 1].X || i == 1) a[ref[i].Y] = i;
        else a[ref[i].Y] = a[ref[i - 1].Y];
    }
    len = (int) ceil(sqrt(n));
    tot = n / len + 1;
    for(int i = 1; i <= n; i++) {
        belong[i] = a[i] / len + 1;
        cnt[belong[i]] ++;
        L[i] = calc_small(a[i]);
        b[a[i]] ++;
    }
    memset(b, 0, sizeof(b)), memset(cnt, 0, sizeof(cnt));
    for(int i = n; i; i--) {
        cnt[belong[i]] ++;
        R[i] = calc_Big(a[i]);
        b[a[i]] ++;
    }
    for(int i = 2; i < n; i++) ans += (long long) L[i] * R[i];
    printf("%lld
", ans);
    return 0;

}