代码

#include <algorithm>
#include <stdlib.h>
const unsigned *globalX, *globalY;
struct foo { unsigned i; unsigned x(){return globalX[i]; }unsigned y(){return globalY[i]; }bool operator<(foo& o) {return x()!=o.x()?x()<o.x():y()>o.y();}} r[10000007];
unsigned z[10000007];
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
for (int i=0; i<n; ++i) [i].i=i;
std::sort(r, r+n);
for (int i=0; i<n; ++i) {
// get
{
int j=r[i].y();
int cnt = 0;
if(j) for (; cnt+=z[j], j&=j-1; );
out[r[i].i] = cnt; }
// set
{
int j=r[i].y()+1;
for (; j<n; j+=j&-j) z[j]+=1;
}
}
}

评测结果