poj 3067 Japan(线段树 | 树状数组)

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-13


题目大意:
在Japan的东西两边都有海岸线,且都是南北方向的。两边分别有n,m个城市,他们的编号分别都为1....n, 1....m.
要在东西海岸的城市间建立一些高速路,求所有的交点有多少个(一个交点保证只有两条路穿过)。

分析与总结:
这题并不难想,把所有路按照以东海岸变为起点u,西海岸为终点v保存下来。然后按照u从小到大顺序排序(v的顺序不重要)。排完序之后,依次枚举就相当于从西海岸的城市1开始依次开始建立连接一直到n为止。
当处理到第i条边时,目标是v城市,这条边连接过去将会增加多少个交点呢? 只需要画画草图就可以发现了,是之前所有变连接到大于v的城市的边之和。
知道了这个后,就可以直接用树状数组或线段树切掉了。

有2个注意的地方:
1. 题目没直接给k的数据范围,数组要开到50W
2. 用long long

代码:
1.树状数组
[cpp]
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
 
typedef long long int64; 
const int MAXN = 1000000; 
int n,m,k; 
int64 c[MAXN]; 
 
struct node{ 
    int u,v; 
    friend bool operator<(const node&a,const node&b){ 
        if(a.u!=b.u) return a.u<b.u; 
        return a.v<b.v; 
    } 
}arr[MAXN]; 
 
inline int lowbit(int x){return x&(-x);} 
int64 sum(int x){ 
    int64 ret=0; 
    while(x>0){ 
        ret += c[x]; 
        x -= lowbit(x); 
    } 
    return ret; 

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

 
int main(){ 
    int T,cas=1; 
    scanf("%d",&T); 
    while(T--){ 
        printf("Test case %d: ",cas++); 
        memset(c, 0, sizeof(c)); 
        scanf("%d%d%d",&n,&m,&k); 
        for(int i=0; i<k; ++i)  
            scanf("%d%d",&arr[i].u,&arr[i].v) ; 
        sort(arr,arr+k); 
        int64 ans=0; 
        for(int i=0; i<k; ++i){ 
            ans += sum(m)-sum(arr[i].v) ; 
            add(arr[i].v); 
        } 
        printf("%lld/n",ans); 
    } 
    return 0; 


2. 线段树
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#define mid ((left+right)>>1) 
#define lson rt<<1,left,mid 
#define rson rt<<1|1,mid+1,right 
using namespace std; 
 
typedef long long int64; 
const int MAXN = 1000000; 
int n,m,k; 
int64 c[MAXN]; 
 
struct node{ 
    int u,v; 
    friend bool operator<(const node&a,const node&b){ 
        if(a.u!=b.u) return a.u<b.u; 
        return a.v<b.v; 
    } 
}arr[MAXN]; 
 
void update(int rt,int left,int right,int data){ 
    ++c[rt]; 
    if(left==right)return; 
    if(data <= mid) update(lson,data); 
    else update(rson,data); 

int query(int rt,int left,int right,int l,int r){ 
    if(left==l && right==r) return c[rt]; 
    int m = mid; 
    if(r <= m) return query(lson,l,r); 
    else if(l > m) return query(rson,l,r); 
    else return query(lson,l,m)+query(rson,m+1,r); 

 
int main(){ 
    int T,cas=1; 
    scanf("%d",&T); 
    while(T--){ 
        printf("Test case %d: ",cas++); 
        memset(c, 0, sizeof(c)); 
        scanf("%d%d%d",&n,&m,&k); 
        for(int i=0; i<k; ++i) { 
            scanf("%d%d",&arr[i].u,&arr[i].v) ; 
        } 
        sort(arr,arr+k); 
        int64 ans=0; 
        for(int i=0; i<k; ++i){ 
            ans += query(1,1,m+1,arr[i].v+1,m+1); 
            update(1,1,m+1,arr[i].v); 
        } 
        printf("%lld/n",ans); 
    } 
    return 0;