//POJ 3067 Japan 线段树 转化
/*
题意:
有一幅图,左边m个结点,右边n个结点,给出k条边连接左边结点和右边结点
求这些边相互交叉的个数,一个点只会有两条边经过
思路:
同样将线段转化成点然后放在二维平面图上,对于两条线段[si,ei],[sj,ej]
满足交叉的条件是si<sj&&ei>ej || si>sj&&ei<ej
两条线段如果同起点或者同终点是不会相交的
所以这样就转化为类似POJ 2352 Stars
不一样的是要同起点和同终点的不能算进去
1、对于同起点,即x相同的,只要在线段树里面多一个a[]数组,记录这个数出现几次,然后查询后扣除就行;
2、对于同终点,即y相同的,由于排序后y相同的连在一起,所以在查询前记录这个结点与上一结点的y是否相同,
如果形同就++res,表示出现的次数,查询后扣除,如果不同就res=0
3、一个点只会有两条边经过,这句话表明没有重边,discuss里面肯定没看题目是乱说的...
PS:没用__int64会爆
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1010
#define M 1000010
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int T,n,m,k;
int sum[N<<2],a[N];
__int64 ans;
struct node{
int x;
int y;
}s[M];
int cmp(const void *a,const void *b){
if((*(node *)b).y != (*(node *)a).y)
return (*(node *)b).y - (*(node *)a).y;
return (*(node *)a).x - (*(node *)b).x;
}
void Pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void Update(int rt,int l,int r,int x){
if(l == r){
++sum[rt];
++a[l];
return ;
}
int mid = (l + r) >> 1;
if(x <= mid) Update(lson,x);
else Update(rson,x);
Pushup(rt);
}
int Query(int rt,int l,int r,int L,int R){
if(L <= l && R >= r){
return sum[rt];
}
int mid= (l + r) >> 1;
int res= 0;
if(L <= mid) res += Query(lson,L,R);
if(R > mid ) res += Query(rson,L,R);
return res;
}
int main(){
int i,j,res,ca = 1;
scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&m,&k);
memset(sum,0,sizeof(sum));
memset(a,0,sizeof(a));
ans = 0;
res = 0;
for(i = 1; i <= k; ++i)
scanf("%d %d",&s[i].x,&s[i].y);
qsort(s+1,k,sizeof(s[0]),cmp);
for(i = 1; i <= k; ++i){
int tmp = s[i].y;
if(i>1 && s[i].y == s[i-1].y)
++res;
else
res = 0;
ans += Query(1,1,n,1,s[i].x)-a[s[i].x]-res;
Update(1,1,n,s[i].x);
}
printf("Test case %d: %I64d\n",ca++,ans);
}
return 0;
}
分享到:
相关推荐
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
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
NULL 博文链接:https://128kj.iteye.com/blog/1744555
POJ3468,线段树处理,注意longlongint
线段树、树状数组算法入门 加 poj解题报告 pdf文档
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类