Anton and Permutation CF

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200003
#define mid (l+r>>1)

int sum[N*100], lc[N*100], rc[N*100], tot;
int num[N], n, root[N];


void add(int l, int r, int &rt, int val, int ad) {
    if (rt == 0) rt = ++tot;
    sum[rt] += ad;
    if (l == r) return;
    if (val <= mid) add(l, mid, lc[rt], val, ad);
    else add(mid+1, r, rc[rt], val, ad);
}

long long query(int l, int r, int rt, int val) {
    if (val < l || rt == 0) return 0;
    if (val == r) {
        return sum[rt];
    }
    if (val <= mid) return query(l, mid, lc[rt], val);
    else return sum[lc[rt]]+query(mid+1, r, rc[rt], val);
}

int lb(int k) {return k&(-k);}

void add(int k, int val, int ad) {
    while (k <= n) {
        add(1, n, root[k], val, ad);
        k += lb(k);
    }
}

long long query(int k, int val) {
    long long re = 0;
    while (k) {
        re += query(1, n, root[k], val);
        k -= lb(k);
    }
    return re;
}

int main() {
    int q, i, j, l, r;
    while (~scanf("%d%d", &n, &q)) {
        memset(sum, 0, sizeof(sum));
        memset(lc, 0, sizeof(lc));
        memset(rc, 0, sizeof(rc));
        memset(root, 0, sizeof(root));
        tot = 0;
        for (i = 1;i <= n;i++) num[i] = i, add(i, i, 1);
        long long ans = 0;
        while (q--) {
            scanf("%d%d", &l, &r);
            if (l > r) swap(l, r);
            if (l == r) {
                printf("%lld\n", ans);
                continue;
            }
            long long lans = query(r-1, num[l])-query(l, num[l]);
            long long rans = query(r-1, num[r])-query(l, num[r]);
            ans += 2*rans-(r-l-1);
            ans += (r-l-1)-2*lans;
            if (num[l] < num[r]) ans++;
            else ans--;
            add(l, num[l], -1);
            add(l, num[r], 1);
            add(r, num[r], -1);
            add(r, num[l], 1);
            swap(num[l], num[r]);
            printf("%lld\n", ans);
        }
    }
}