描述 Description
给定一个数字序列，求它的逆序对数，之后m条询问，格式为“A B”，表示假如把A位置的数改成B，逆序对数又是多少。注意是“假如”，也就是说，在处理完一条询问后，序列又恢复初始序列。
输入格式 InputFormat
第一行两个正整数m，n。
第二行有n个正整数，用空格隔开。
第三行到第m+2行，每行两个整数A,B,用空格隔开。
输出格式 OutputFormat
共m+1行，第一行为初始序列的逆序对数，接下来的m行分别对应每一条询问的新逆序对数。
样例输入 SampleInput [复制数据]
5 2 1 2 3 4 5 1 5 4 2
样例输出 SampleOutput [复制数据]
0 3 1
数据范围和注释 Hint
n<=100000
m<=100000
序列的每一元素<=500000
保证询问合法。
题解
改变一个数的大小，对逆序对的影响取决于改完后它前面有多少个比他大的数、后面有多少个比他小的数。所以我们考虑离线的做法。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXN 100002
using namespace std;
int n,m,a[MAXN],maxs;
struct ques{int l,s;} b[MAXN];
int last[MAXN],pre[MAXN];
ll tr[MAXN*5],tot,v[MAXN],cg[MAXN];
void init()
{
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++)
{scanf("%d",&a[i]); maxs=max(maxs,a[i]);}
for(i=1;i<=m;i++)
{scanf("%d%d",&b[i].l,&b[i].s);
pre[i]=last[b[i].l]; last[b[i].l]=i;
}
}
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<=500002;x+=lowbit(x)) tr[x]++;}
void work()
{
int i,j;
for(i=1;i<=n;i++)
{j=last[i];
v[i]+=find(maxs)-find(a[i]);
tot+=v[i];
while(j)
{cg[j]+=find(maxs)-find(b[j].s);
j=pre[j];
}
insert(a[i]);
}
memset(tr,0,sizeof(tr));
for(i=n;i>0;i--)
{j=last[i];
v[i]+=find(a[i]-1);
while(j)
{cg[j]+=find(b[j].s-1);
j=pre[j];
}
insert(a[i]);
}
printf("%lld\n",tot);
for(i=1;i<=m;i++)
printf("%lld\n",tot-v[b[i].l]+cg[i]);
}
int main()
{
init(); work();
return 0;
}