//POJ 2352 Stars 线段树 单点更新 成段求和
/*
题意:给一系列点(按y递增,y相同时按x递增排列),level指不超过当前点的高度且不在当前点右边的点的个数
求level值分别为0,1,2,..n-1的个数
思路:由于题意已经是按顺序给的点,所以直接按x轴建树
注意x从0开始,线段树从1开始,所以x全部+1处理
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 32005
#define M 15005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int sum[N<<2],ans[M];
int n;
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]++;
return ;
}
int mid = (l + r) >> 1;
if(x <= mid) Update(lson,x);
if(x > mid ) 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;
int x,y;
while(scanf("%d",&n)!=EOF){
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
for(i = 1; i <= n; ++i){
scanf("%d %d",&x,&y);
++x;
++ans[Query(1,1,32001,1,x)];
Update(1,1,32001,x);
}
for(i = 0; i < n; ++i)
printf("%d\n",ans[i]);
}
return 0;
}
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1739733
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj 2482 Stars in Your Window.md
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739064
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and ...
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
线段树、树状数组算法入门 加 poj解题报告 pdf文档
POJ3468,线段树处理,注意longlongint
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同...poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算,框不一定要整数起点,可另左下落在框上算。求亮度和最大的点即可。...每次用线段树更新和求最大值。
北大POJ2002-Squares 解题报告+AC代码