题意：
有n个人站成一排,每个人的身高为Hi。每次有人加入或者有人离开,就要判断有多少人站反了(i < j&&Hi>Hj)
第一行n,m,接下来n个整数(n,m<=2e4)
接下来m行,
0 x y 表示有一个身高为y的人插在x后面,x=0表示插在最前面。(1≤y≤n)
1 x 表示第x个人（从左到右）离开。
题解：
官方题解：
添加或者删除一个元素时，维护逆序对时，需要知道在它之前有多少个数比它大，在它之后有多少个数比他小。有下标和权值两个维度，可以使用两个数据结构嵌套。题目中n=20000，范围不大，外层可以使用分块维护下标，这样添加和删除元素的时候，
也很方便，直接暴力。查找权值个数时，使用树状数组比较方便。内层通过树状数组维护权值。设每块的大小为S，那么删除或者添加元素时，维护逆序对数的复杂度是O(S+P∗logn)，S是块内直接暴力更新逆序对的代价，
P/S∗logn在前面块找比它大和在后面块中找比它小的代价,P表示当前元素的个数。为了使这两部分复杂度尽量均摊让S=P/S∗logn，S取根号Plogn
。直接通过分块暴力添加和删除时，块的大小会退化，需要重构，。重构一次的复杂度是S*logn, 总的重构复杂度是,与添加和删除总的复杂度一至。因此整个问题的复杂度为O(m√nlogn).
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int N=,sqr=;
int ans,tot,n,flag,op,x,y,m; inline void add(int *c,int x,int v){while(x<=n)c[x]+=v,x+=x&-x;} inline int sum(int *c,int x){int an=;while(x>)an+=c[x],x-=(x&-x);return an;} struct node
{
int dt[sqr+],sz,c[N],nxt,pre;
void init(){memset(c,,sizeof(c)),sz=,pre=,nxt=;}
}b[]; int getpos(int &x)
{
int i=;
while(b[i].sz<x&&b[i].nxt)x-=b[i].sz,i=b[i].nxt;
return i;
} int cal(int x)
{
int an=;
int id=getpos(x);
F(i,,x-)if(b[id].dt[i]>b[id].dt[x])an++;
F(i,x+,b[id].sz)if(b[id].dt[i]<b[id].dt[x])an++;
for(int i=;i!=id;i=b[i].nxt)
an+=sum(b[i].c,n)-sum(b[i].c,b[id].dt[x]);
for(int i=b[id].nxt;i!=;i=b[i].nxt)
an+=sum(b[i].c,b[id].dt[x]-);
return an;
} void del(int x){
ans-=cal(x);
int id=getpos(x);
add(b[id].c,b[id].dt[x],-);
F(i,x+,b[id].sz)b[id].dt[i-]=b[id].dt[i];
b[id].sz--;
if(b[id].sz==)//删除块
{
int pre=b[id].pre,net=b[id].nxt;
b[net].pre=pre,b[pre].nxt=net;
}
} void ins(int x,int y)
{
int xx=x;
if(flag==)
{
b[].init(),b[].dt[++b[].sz]=y;
add(b[].c,b[].dt[],),flag=;
return;
}
int id=getpos(x);//在第几个块
if(b[id].sz==sqr)//块分裂
{
b[++tot].init(),b[id].sz++;
int cnt=;
for(int i=b[id].sz;i>x;i--)
b[id].dt[i]=b[id].dt[i-];
b[id].dt[x]=y;
add(b[id].c,b[id].dt[x],);
int len=b[id].sz/;
F(i,len+,b[id].sz)
{
b[tot].dt[++cnt]=b[id].dt[i];
add(b[tot].c,b[id].dt[i],);
add(b[id].c,b[id].dt[i],-);
}
b[tot].sz=cnt,b[tot].nxt=b[id].nxt;
b[id].nxt=tot,b[id].sz=len,b[tot].pre=id;
}
else{
b[id].sz++;
for(int i=b[id].sz;i>x;i--)
b[id].dt[i]=b[id].dt[i-];
b[id].dt[x]=y;
add(b[id].c,b[id].dt[x],);
}
ans+=cal(xx);
} int main(){
while(~scanf("%d%d",&n,&m))
{
ans=,tot=,b[].sz=,flag=;
F(i,,n)scanf("%d",&y),ins(i,y);
F(i,,m)
{
scanf("%d",&op);
if(op==)scanf("%d%d",&x,&y),ins(x+,y);
else scanf("%d",&x),del(x);
printf("%d\n",ans);
}
}
return ;
}