当前位置:编程学习 > C/C++ >>

poj 2481


树状数组 和2352 差不多,先按E从大到小,E相同按S从小到大,对于相同的点要特殊处理一下。。有两种方法判断。。详细见代码
[cpp] 
#include <cmath> 
#include <ctime> 
#include <iostream> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <cctype> 
#include <stack> 
#include <deque> 
using namespace std; 
typedef long long LL; 
#define EPS 10e-9 
#define INF 0x3f3f3f3f 
#define REP(i,n) for(int i=0; i<(n); i++) 
const int maxn = 100100; 
struct node{ 
    int l,r,id; 
    bool operator <(const node & b) const { 
        if(r==b.r) return l<b.l; 
        return r>b.r; 
    } 
  www.zzzyk.com
}a[maxn]; 
int ans[maxn],c[maxn]; 
int lowbit(int x){ return x&-x; } 
int sum(int x){ 
    int ret=0; 
    while(x>0){ 
       ret+=c[x]; x-=lowbit(x); 
    } 
    return ret; 

void add(int x){ 
    while(x<maxn){ 
       c[x]+=1;   x+=lowbit(x); 
    } 

int main(){ 
    int n; 
    while(scanf("%d",&n)!=EOF){ 
        if(n==0) break; 
        memset(c,0,sizeof(c)); 
        for(int i=0;i<n;i++){ 
            scanf("%d %d",&a[i].l,&a[i].r);  a[i].l++; a[i].r++; 
            a[i].id=i; 
        } 
        sort(a,a+n); 
        for(int i=0;i<n;i++){ 
             if(i>0&&a[i].l==a[i-1].l&&a[i].r==a[i-1].r){ 
                 ans[ a[i].id ]=ans[ a[i-1].id]; 
             } 
             else 
             ans[a[i].id]=sum(a[i].l); 
//             int j=i-1; 
//             while(j>=0&&a[j].l==a[i].l&&a[j].r==a[i].r){ 
//                ans[a[i].id ]--; 
//                j--; 
//             } 
 
             add(a[i].l); 
 
 
        } 
        printf("%d",ans[0]); 
        for(int i=1;i<n;i++) 
          printf(" %d",ans[i]); printf("\n"); 
 
    } 
   return 0; 

 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,