学步园

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	long long x,v,owz;
	bool cmp;
} q[1000000];
bool cmp(node i,node j){
	return i.x>j.x;
}
long long an[1000000],n,m,maxn,i,ans,a[1000000],c[1000000],j,l[1000000],
r[1000000],ql[1000000],qr[1000000];

void insert(long long x,long long v){
	for (;x<=maxn;x+=x&-x)
	    c[x]+=v;
}
/*void insert2(int x,int v){
    for (;x>0;x-=x&-x)
        c[x]+=v;
}*/
long long sum(long long x){
	long long s=0;
	for (;x>0;x-=x&-x)
	    s+=c[x];
	return s;
}
/*int sum2(int x){
    int s=0;
    for (;x<=maxn;x+=x&-x)
        s+=c[x];
    return s;
}*/
int main(){
	cin>>n>>m;
	for (i=1;i<=n;i++){
	    cin>>a[i];
	    if (a[i]>maxn)
	        maxn=a[i];
	}
	for (i=1;i<=m;i++){
	    cin>>q[i].x>>q[i].v;
	    q[i].owz=i;
	    if (q[i].v>maxn)
	        maxn=q[i].v;
	}
	
	for (i=n;i>0;i--){        //the first answer
	    insert(a[i],1);
	    l[i]=sum(a[i]-1);
	    ans+=l[i];
	}
	memset(c,0,sizeof(c));
	for (i=1;i<=n;i++){
        insert(a[i],1);
        r[i]=sum(maxn)-sum(a[i]);
        ans+=r[i];
    }
	cout<<ans/2<<"\n";
	ans/=2;
	
	sort(q+1,q+m+1,cmp);
    q[0].x=n;
    memset(c,0,sizeof(c));
	for (i=1;i<=m;i++){
		for (j=q[i-1].x;j>=q[i].x+1;j--)
		    insert(a[j],1);
		insert(q[i].v,1);
		ql[i]=sum(q[i].v-1);
		insert(q[i].v,-1);
	}
	memset(c,0,sizeof(c));
	q[m+1].x=1;
	for (i=m;i>0;i--){
        for (j=q[i+1].x;j<=q[i].x-1;j++)
            insert(a[j],1);
        insert(q[i].v,1);
        qr[i]=sum(maxn)-sum(q[i].v);
        insert(q[i].v,-1);
    }
    for (i=1;i<=m;i++)
        an[q[i].owz]=ans-(l[q[i].x]+r[q[i].x])+ql[i]+qr[i];
    for (i=1;i<=m;i++)
        cout<<an[i]<<"\n";
}