Rio and Inversions

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define CLR(x,y) memset(x,y,sizeof(x))
#define SZ(x) ((int)(x).size())
typedef long long vlong;
const vlong inf = 2147383647;
const vlong mod = 1000000007;

int n, q, a[10004], tt, uu, vv, ans;
int prec[102][102], csum[102], rt, c[102];

void countSegmentInversion(int seg) {
    int st = seg*rt;
    int en = min(n,(seg+1)*rt), ans;
    CLR(c,0); ans = 0;

    for (int i=st; i<en; i++) {
        int tmp = 0;
        for (int j = a[i]+1; j<100; j++) {
            tmp += c[j];
        }
        ans += tmp;
        c[a[i]]++;
    } csum[seg] = ans;

    for (int i=0; i<100; i++) prec[seg][i] = c[i];
}

int solve1(int st, int en, int c[]) {
    int tmp = st/rt, ans = 0;
    tmp++; tmp *= rt;

    if (en < tmp) {
        for (int i=st; i<=en; i++) {
            int tmp = 0;
            for (int j=a[i]+1; j<100; j++) {
                tmp += c[j];
            }
            ans += tmp;
            c[a[i]]++;
        } return ans;
    } else {
        for (int i=st; i<tmp; i++) {
            int tmp = 0;
            for (int j=a[i]+1; j<100; j++) {
                tmp += c[j];
            }
            ans += tmp;
            c[a[i]]++;
        }
        for ( ; tmp+rt<=en; tmp+=rt) {
            int tot = 0;
            for (int i=0; i<100; i++) tot += c[i];
            for (int i=0; i<100; i++) {
                tot -= c[i];
                ans += ( prec[tmp/rt][i] * tot );
                c[i] += prec[tmp/rt][i];
            }
            ans += csum[tmp/rt];
        }
        for (int i=tmp; i<=en; i++) {
            int tmp = 0;
            for (int j=a[i]+1; j<100; j++) {
                tmp += c[j];
            }
            ans += tmp;
            c[a[i]]++;
        }

    }
    return ans;
}

int solve0() {
    prec[uu/rt][a[uu]]--;
    prec[vv/rt][a[vv]]--;
    swap(a[uu],a[vv]);
    prec[uu/rt][a[uu]]++;
    prec[vv/rt][a[vv]]++;
    countSegmentInversion(uu/rt);
    countSegmentInversion(vv/rt);

    CLR(c,0);
    int ans = solve1(0,n-1,c);

    prec[uu/rt][a[uu]]--;
    prec[vv/rt][a[vv]]--;
    swap(a[uu],a[vv]);
    prec[uu/rt][a[uu]]++;
    prec[vv/rt][a[vv]]++;
    countSegmentInversion(uu/rt);
    countSegmentInversion(vv/rt);

    return ans;
}

int main () {
    scanf("%d", &n);

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

    rt = sqrt(n);
    for (int i=0; i*rt < n; i++) {
        countSegmentInversion(i);
    }

    scanf("%d", &q);
    while (q--) {
        scanf("%d %d %d", &tt, &uu, &vv);
        if (uu > vv) swap(uu,vv);
        ans = 0;
        CLR(c,0);

        if (tt == 0) {
            ans = solve0();
        } else {
            if (uu != 0) {
                ans = solve1(0,uu-1,c);
            }
            if (vv != n-1) {
                ans += solve1(vv+1,n-1,c);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}