codechef Chef and Swaps

徐冬丽

Problem Description
　　

This time, Chef has given you an array A containing N elements.

He had also asked you to answer M of his questions. Each question sounds like: "How many inversions will the array A contain, if we swap the elements at the i-th and the j-th positions?".

The inversion is such a pair of integers (i, j) that i < j and Ai > Aj.



Input



The first line contains two integers N and M - the number of integers in the array A and the number of questions respectively.

The second line contains N space-separated integers - A1, A2, ..., AN, respectively.

Each of next M lines describes a question by two integers i and j - the 1-based indices of the numbers we'd like to swap in this question.


Output



Output M lines. Output the answer to the i-th question of the i-th line.




Constraints

1 ≤ N, M ≤ 2 * 105

1 ≤ i, j ≤ N

1 ≤ Ai ≤ 109

Mind that we don't actually swap the elements, we only answer &quot;what if&quot; questions, so the array doesn't change after the question.




Example

Input:

6 3

1 4 3 3 2 5

1 1

1 3

2 5


Output:

5

6

0




Explanation



Inversions for the first case: (2, 3), (2, 4), (2, 5), (3, 5), (4, 5).

Inversions for the second case: (1, 3), (1, 5), (2, 3), (2, 4), (2,5), (4, 5).

In the third case the array looks like 1 2 3 3 4 5 and there are no inversions.
　　


题解

　　

tyvj《逆序对加强版》的加强版。同样的我们也考虑离线的做法。在那道题中，我们可以得到“修改一个点之后的逆序对”，这道题其实相当于同时改两个点。但要知道，每次交换算答案时要分情况讨论：当a[x]==a[y]和当a[x]!=a[y]时答案的计算是不一样的.　　

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXN 200002
using namespace std;
int n,m,a[MAXN],ha[MAXN],hs[MAXN],maxs,zz;
struct qus{int l,r;} b[MAXN];
int lastl[MAXN],prel[MAXN],lastr[MAXN],prer[MAXN];
ll v[MAXN],cgl[MAXN],cgr[MAXN],tot,tr[MAXN];
void init()
{
scanf(&quot;%d%d&quot;,&n,&m);
int i;
for(i=1;i<=n;i++)
{scanf(&quot;%d&quot;,&a);
ha=a;
}
sort(ha+1,ha+n+1);
for(i=1;i<=n;i++)
{if(ha!=ha[i-1])
hs[++zz]=ha;
}
for(i=1;i<=m;i++)
{scanf(&quot;%d%d&quot;,&b.l,&b.r);
prel=lastl[b.l]; lastl[b.l]=i;
prer=lastr[b.r]; lastr[b.r]=i;
}
}
int getw(int x)
{
int s=1,t=zz,mid;
while(s<=t)
{mid=(s+t)>>1;
if(hs[mid]<x) s=mid+1;
else t=mid-1;
}
return s;
}
int lowbit(int x) {return x&(-x);}
ll find(int x)
{
ll sum=0;
for(;x>0;x-=lowbit(x)) sum+=tr[x];
return sum;
}
void insert(int x)
{for(;x<=zz;x+=lowbit(x)) tr[x]++;}
void work()
{
int i,j,k,x,y;
maxs=zz;
for(i=1;i<=n;i++)
{j=lastl; k=lastr;
x=getw(a);
v+=find(maxs)-find(x);
tot+=v;
while(j)
{y=getw(a[b[j].r]);
cgl[j]+=find(maxs)-find(y);
j=prel[j];
}
while(k)
{y=getw(a[b[k].l]);
cgr[k]+=find(maxs)-find(y);
k=prer[k];
}
insert(x);
}
memset(tr,0,sizeof(tr));
for(i=n;i>0;i--)
{j=lastl; k=lastr;
x=getw(a);
v+=find(x-1);
while(k)
{y=getw(a[b[k].l]);
cgr[k]+=find(y-1);
k=prer[k];
}
while(j)
{y=getw(a[b[j].r]);
cgl[j]+=find(y-1);
j=prel[j];
}
insert(x);
}
for(i=1;i<=m;i++)
{x=b.l; y=b.r;
if(a[x]==a[y]) printf(&quot;%lld\n&quot;,tot);
else printf(&quot;%lld\n&quot;,tot-v[x]-v[y]+cgl+cgr+1);
}
}
int main()
{
init(); work();
return 0;
}