25pts，AC+RE+TLE

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,NN=505;
int n,q,a[N],l[NN],r[NN],id[NN],len,ans;
multiset<int>b[NN],t;
void upd(int id1,int id2)
{
    if(id[id1]!=id[id2])
    {
        b[id[id1]].erase(b[id[id1]].find(a[id1]));
        b[id[id2]].erase(b[id[id2]].find(a[id2]));
        b[id[id2]].insert(a[id1]);
        b[id[id1]].insert(a[id2]);
    }
    swap(a[id1],a[id2]);
}
int query(int x,int y,int val)
{
    if(x>y)
        return 0;
    int res=0;
    if(id[x]==id[y])
    {
        for(int i=x;i<=y;i++)
            if(a[i]<val)
                res++;
        return res;
    }
    for(int i=x;i<=r[id[x]];i++)
        if(a[i]<val)
            res++;
    for(int i=id[x]+1;i<id[y];i++)
    {
        multiset<int>::iterator j=b[i].lower_bound(val);
        int cnt=0;
        while(j!=b[i].begin())
            cnt++,j--;
        res+=cnt;
    }
    for(int i=l[id[y]];i<=y;i++)
        if(a[i]<val)
            res++;
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        multiset<int>::iterator j=t.upper_bound(a[i]);
        int cnt=0;
        while(j!=t.end())
            cnt++,j++;
        ans+=cnt;
        t.insert(a[i]);
    }
    len=sqrt(n);
    for(int i=1;i<=len;i++)
        l[i]=(i-1)*len+1,r[i]=i*len;
    if(r[len]!=n)
        l[len+1]=r[len]+1,r[len+1]=n,len++;
    for(int i=1;i<=len;i++)
        for(int j=l[i];j<=r[i];j++)
            b[i].insert(a[j]);
    scanf("%d",&q);
    printf("%d\n",ans);
    while(q--)
    {
        int id1,id2;
        scanf("%d%d",&id1,&id2);
        if(id1>id2)
            swap(id1,id2);
        if(id1==id2)
        {
            printf("%d\n",ans);
            continue;
        }
        ans+=2*(query(id1+1,id2-1,a[id2])-query(id1+1,id2-1,a[id1]));
        ans+=(a[id2]>a[id1])?1:-1;
        upd(id1,id2);
        printf("%d\n",ans);
    }
    return 0;
}