记录编号	539232	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排队(魏铭)	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.890 s
提交时间	2019-08-06 00:35:46	内存使用	19.71 MiB

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct data
{
    int h , p;
}a[20010];
int v[20010] , top , f[150][20010];
bool cmp1(data a , data b)
{
    return a.h < b.h;
}
bool cmp2(data a , data b)
{
    return a.p < b.p;
}
void update(int p , int x , int a)
{
    int i;
    for(i = x ; i <= top ; i += i & (-i))
        f[p][i] += a;
}
int query(int p , int x)
{
    int i , ans = 0;
    for(i = x ; i ; i -= i & (-i))
        ans += f[p][i];
    return ans;
}
int main()
{
    freopen("nt2011_queue.in","r",stdin);freopen("nt2011_queue.out","w",stdout);
    int n , m , i , j , si , ans = 0 , x , y;
    scanf("%d" , &n);
    si = (int)sqrt(n);
    for(i = 0 ; i < n ; i ++ )
        scanf("%d" , &a[i].h) , a[i].p = i;
    sort(a , a + n , cmp1);
    for(i = 0 ; i < n ; i ++ )
    {
        if(a[i].h != v[top]) v[++top] = a[i].h;
        a[i].h = top;
    }
    sort(a , a + n , cmp2);
    for(i = 0 ; i < n ; i ++ )
    {
        for(j = 0 ; j <= i / si ; j ++ ) ans -= query(j , a[i].h);
        ans += i;
        update(i / si , a[i].h , 1);
    }
    printf("%d\n" , ans);
    scanf("%d" , &m);
    while(m -- )
    {
        scanf("%d%d" , &x , &y);
        x -- ; y -- ;
        if(x > y) swap(x , y);
        if(x / si == y / si)
            for(i = x + 1 ; i < y ; i ++ )
                ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);
        else
        {
            for(i = x / si + 1 ; i < y / si ; i ++ )
                ans += (si - query(i , a[x].h)) + query(i , a[y].h - 1) - query(i , a[x].h - 1) - (si - query(i , a[y].h));
            for(i = x + 1 ; i < (x / si + 1) * si ; i ++ )
                ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);
            for(i = y / si * si ; i < y ; i ++ )
                ans += (a[i].h > a[x].h) + (a[i].h < a[y].h) - (a[i].h < a[x].h) - (a[i].h > a[y].h);
        }
        ans += (a[x].h < a[y].h) - (a[x].h > a[y].h);
        update(x / si , a[x].h , -1) , update(y / si , a[y].h , -1);
        swap(a[x].h , a[y].h);
        update(x / si , a[x].h , 1) , update(y / si , a[y].h , 1);
        printf("%d\n" , ans);
    }
    return 0;
}