网上一段AC代码：
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=100000;
struct node
{
int l,r;
int id;
}nodes[maxn+20];
int tree[maxn];
int lowbit(int n)
{
return n&(n^(n-1));
}
void insert(int n)
{
while(n<=maxn+10)
{
tree[n]++;
n=n+lowbit(n);
}
}
int query(int n)
{
int ans=0;
while(n>0)
{
ans+=tree[n];
n=n-lowbit(n);
}
return ans;
}
bool operator<(const node p1,const node p2)
{
if(p1.l==p2.l) return p1.r>p2.r;
else return p1.l<p2.l;
}
int ans[maxn+20];
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
memset(ans,0,sizeof(ans));
memset(tree,0,sizeof(tree));
for(int i=0;i<n;i++)
{
scanf("%d%d",&nodes[i].l,&nodes[i].r);
nodes[i].id=i;
}
sort(nodes,nodes+n);
ans[nodes[0].id]=0;
insert(nodes[0].r);
int cnt=0;
for(int i=1;i<n;i++)
{
if(nodes[i].l==nodes[i-1].l&&nodes[i].r==nodes[i-1].r) cnt++;
else cnt=0;
ans[nodes[i].id]=i-cnt-query(nodes[i].r-1);
insert(nodes[i].r);
}
printf("%d",ans[0]);
for(int i=1;i<n;i++) printf(" %d",ans[i]);
printf("\n");
}
return 0;
}


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/logic_nut/archive/2009/09/21/4577167.aspx
**********************************************************************
测试：
4
0 100000
0 100000
1 2
1 2
2 0 2 2
正确结果应该为
0 0 2 2
难道不是么？

我的程序：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100010

typedef struct{
int l;
int r;
int loc;
}node;

node cow[MAX];
int c[MAX],num[MAX];

int cmp(const void *p1,const void *p2){
node *c1=(node *)p1;
node *c2=(node *)p2;
if(c1->l==c2->l)
return c2->r-c1->r;
else
return c1->l-c2->l;
}
int lowbit(int x){
return x&(x^(x-1));
}
void chang(int x){
while(x<=MAX){
c[x]+=1;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}

int main(void){
int n,i;
node *temp;

while(scanf("%d",&n)&&n!=0){
memset(c,0,sizeof(c));
memset(num,0,sizeof(num));
for(i=1;i<=n;i++){
scanf("%d %d",&cow[i].l,&cow[i].r);
cow[i].l++;
cow[i].r++;
cow[i].loc=i;
}
qsort(&cow[1],n,sizeof(cow[1]),cmp);

chang(cow[1].r);
num[cow[1].loc]=0;
for(i=2;i<=n;i++){
chang(cow[i].r);
num[cow[i].loc]=i-sum(cow[i].r);
}
for(i=1;i<=n;i++)
printf("%d ",num[i]);
printf("\n");
}
}
测试的几个例子都正确，结果却是WA 没有天理了
哪位同志看到 帮我测测如何 给我留言 谢谢

• Re:这个题目测试有问题没？ (1699) gnaggnoyil 2009-12-27 16:56:44