Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

树状数组的简单应用

Posted by yc5_yc at 2012-11-10 22:17:07 on Problem 2481
先对区间排序,在B[i]升序的情况下A[i]降序
从后往前扫描,因为对于任意B[j]在B[i]之后的情况下,j不可能比i更强
所以,每次扫描只需要统计小于等于A[i]的情况即可,这时使用树状数组
注意当前后A,B均相同时的特判
#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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator