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

## 树状数组的简单应用

Posted by yc5_yc at 2012-11-10 22:17:07 on Problem 2481
```先对区间排序，在B[i]升序的情况下A[i]降序

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
const int NMax=101000;
struct line {
int a,b,num,ret;
}A[NMax];
int N,F[NMax];
inline int lowbit(int a) {return a&(a^(a-1));}
void set(int a,int b) {
int tmp=a;
while(tmp<=100000) {
F[tmp]+=b;
tmp+=lowbit(tmp);
}
}
int query(int a,int b) {
if(a>b) swap(a,b);
int tmp=b,ret=0;
while(tmp>0) {
ret+=F[tmp];
tmp-=lowbit(tmp);
}
return ret;
}
bool cmp(line a,line b) {
return a.b<b.b||(a.b==b.b&&a.a>b.a);
}
int C[NMax];
int main()
{
while(scanf("%d",&N),N) {
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++) {
scanf("%d%d",&A[i].a,&A[i].b);
A[i].a++;A[i].b++;
A[i].num=i;
}
sort(A+1,A+N+1,cmp);
//for(int i=1;i<=N;i++) {printf("%d %d\n",A[i].a,A[i].b);}
for(int i=N;i>=1;i--) {
int tmp;
if(i!=N&&A[i].a==A[i+1].a&&A[i].b==A[i+1].b) tmp=A[i+1].ret;
else tmp=query(1,A[i].a);
A[i].ret=tmp;
set(A[i].a,1);
}
for(int i=1;i<=N;i++) C[A[i].num]=A[i].ret;
for(int i=1;i<N;i++) printf("%d ",C[i]);
printf("%d\n",C[N]);
}
getchar();getchar();
return 0;
}
```

Followed by: