Main » 2013 September 16 » 坑爹的逆序对
3:48 PM 坑爹的逆序对 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #define N 500010 #define L 600010 using namespace std; vector<int> pos[N]; vector<int> Q[N]; long long c[L],a[N],M=0; long long LC[N][2],RC[N][2],D[N],P[N]; long long lowbit(long long x){return x&(-x);} long long getsum(long long x) {long long res=0;for (long long i=x;i>0;i-=lowbit(i)) res+=c[i];return res;} void modify(long long x,long long delta) {for (long long i=x;i<=M;i+=lowbit(i)) c[i]+=delta;} int main() { int n,m,i,j; scanf("%d %d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]>M) M=a[i]; } for (i=1;i<=m;i++) { scanf("%d %d",&P[i],&D[i]); if (D[i]>M) M=D[i]; pos[P[i]].push_back(D[i]); Q[P[i]].push_back(i); } memset(c,0,sizeof(c)); long long sum=0; for (i=1;i<=n;i++) { for (j=0;j<pos[i].size();j++) { long long numq=Q[i][j]; LC[numq][0]=getsum(M)-getsum(pos[i][j]); LC[numq][1]=getsum(M)-getsum(a[i]); } sum+=getsum(M)-getsum(a[i]); modify(a[i],1); } memset(c,0,sizeof(c)); for (i=1;i<=n;i++) { for (j=0;j<pos[n-i+1].size();j++) { long long numq=Q[n-i+1][j]; RC[numq][0]=getsum(pos[n-i+1][j]-1); RC[numq][1]=getsum(a[n-i+1]-1); } modify(a[n-i+1],1); } printf("%lld\n",sum); for (i=1;i<=m;i++) { long long ans; ans=sum-LC[i][1]-RC[i][1]+LC[i][0]+RC[i][0]; printf("%lld\n",ans); } } |
|
|
| Total comments: 0 | |