Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 尼玛！一道逆序数纠结我好几天，终于AC，庆祝一下，靠！！！

Posted by hncu110640108 at 2012-11-22 21:16:58 on Problem 2481
```#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,b[100010],c[100010];
int nima;
struct node{
int t1;
int t2;
int num;
}a[100010];
bool cmp(struct node a,struct node b)
{
if(a.t1==b.t1)
return a.t2<b.t2;
return a.t1>b.t1;
}
int lowbit(int x)
{
return x&(-x);
}
void insert(int x)
{
while(x<=nima)
{
c[x]+=1;
x=x+lowbit(x);
}
}
int sum(int x,int y)
{
int s=0;
while(y>=x)
{
s+=c[y];
y=y-lowbit(y);
}
return s;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF&&n)
{
nima=-1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].t1,&a[i].t2);
a[i].num=i;
if(nima<a[i].t2)
nima=a[i].t2;
}
memset(c,0,sizeof(c));
sort(a+1,a+n+1,cmp);
/*for(i=1;i<=n;i++)
printf("%d %d\n",a[i].t1,a[i].t2);*/
b[a[n].num]=sum(a[n].t2,nima)-sum(1,a[n].t2-1);
insert(a[n].t2);
for(j=1,i=n-1;i>=1;i--,j++)
{
if(a[i].t1!=a[i+1].t1||a[i].t2!=a[i+1].t2)
b[a[i].num]=j-sum(1,a[i].t2-1);
else
b[a[i].num]=b[a[i+1].num];
insert(a[i].t2);
}
/*  for(i=1;i<=n;i++)
printf("%d ",c[i]);
printf("\n");*/
for(i=1;i<n;i++)
printf("%d ",b[i]);
printf("%d\n",b[n]);
}
return 0;
}```

Followed by: