## tyvj1744——by rfy

2018年05月02日 ⁄ 综合 ⁄ 共 1283字 ⁄ 字号 评论关闭
```#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";
}
```

【上篇】
【下篇】