poj 3067 Japan(线段树 | 树状数组)
题目大意:
在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;
}
补充:软件开发 , C++ ,