题目链接:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1400
结构体排序+树状数组模板..
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c[];
struct point
{
int x;
int v;
} p[];
bool cmp(point p1,point p2)
{ if(p1.x !=p2.x)
return p1.x>p2.x;
else
return p1.v<p2.v;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int i,int val)
{
while(i<=)
{
c[i]+=val;
i+=lowbit(i);
} }
int Sum(int i)
{
int s=;
while(i>)
{
s += c[i];
i -= lowbit(i);
}
return s;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,n;
while(scanf("%d",&n)!=EOF)
{ memset(c,,sizeof(c));
long long int ans = ;
for(i=; i<n; i++)
scanf("%d%d",&p[i].x,&p[i].v);
sort(p,p+n,cmp);
for(i=; i<n; i++)
{
ans += Sum(p[i].v);
update(p[i].v+,);
}
printf("%lld\n",ans);
}
return ;
}