链接:
http://poj.org/problem?id=3067
题目大意:
在Japan的东西两边都有海岸线,且都是南北方向的。两边分别有n,m个城市,他们的编号分别都为1....n, 1....m.
要在东西海岸的城市间建立一些高速路,求所有的交点有多少个(一个交点保证只有两条路穿过)。
分析与总结:
这题并不难想,把所有路按照以东海岸变为起点u,西海岸为终点v保存下来。然后按照u从小到大顺序排序(v的顺序不重要)。排完序之后,依次枚举就相当于从西海岸的城市1开始依次开始建立连接一直到n为止。
当处理到第i条边时,目标是v城市,这条边连接过去将会增加多少个交点呢? 只需要画画草图就可以发现了,是之前所有变连接到大于v的城市的边之和。
知道了这个后,就可以直接用树状数组或线段树切掉了。
有2个注意的地方:
1. 题目没直接给k的数据范围,数组要开到50W
2. 用long long
代码:
1.树状数组
#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. 线段树
#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;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744555
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1747400
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
NULL 博文链接:https://128kj.iteye.com/blog/1745671
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ3468,线段树处理,注意longlongint
POJ题解 个人写法 线段树每个人都不一样
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://200830740306.iteye.com/blog/603493