与2299类似,求逆序数;
首先按x升序排列,再求y的逆序数;
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <stdlib.h> using namespace std; int b[1000005]; int n,m,k; struct q { int x; int y; }p[1000105]; bool cmp(q a ,q b) { if (a.x != b.x) return a.x < b.x; else return a.y <= b.y; } int lowbit(int i) { return i&-i; } int sum(int i) { long long ans =0; while (i>0) { ans += b[i]; i -= lowbit(i); } return ans; } void update(int i,int v) { while (i<=m) { b[i]+=v; i+=lowbit(i); } } int main () { int t ; int ss=1; scanf ("%d",&t); while (t--) { scanf ("%d%d%d",&n,&m,&k); for (int i=1;i<=k;i++) { scanf ("%d%d",&p[i].x,&p[i].y ); } sort (p+1,p+1+k,cmp); memset(b,0,sizeof(b)); long long ans =0 ; for (int i=1;i<=k;i++) { update(p[i].y,1); ans += i-sum( p[i].y ); } printf("Test case %d: ",ss++); printf("%lld\n",ans); } return 0; }