点击打开链接poj2481
思路:线段树+单点更新
分析:
1 题目给定n头牛所在的区间,然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei],牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话那么就有Si <= Sj && Ei >= Ej && Si-Ei != Sj-Ej;
3 那么根据上面的条件,我们应该要先对n头牛的区间排序”按照S从小到大,相同S按照E从大到小排序“,然后就可以利用线段树求了。
4 有一个地方需要注意的是当排完序后相邻的两个相等,那么只须更新不用求和。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
struct Segment{
int x;
int y;
int number;
bool operator==(const Segment &a)const{
if(a.x == x && a.y == y)
return true;
return false;
}
};
Segment s[MAXN];
struct Node{
int left;
int right;
int sum;
};
Node node[4*MAXN];
int n;
int vis[MAXN];
bool cmp(Segment s1 , Segment s2){
if(s1.x < s2.x)
return true;
else if(s1.x == s2.x && s1.y > s2.y)
return true;
return false;
}
void buildTree(int left , int right , int pos){
node[pos].left = left;
node[pos].right = right;
node[pos].sum = 0;
if(left == right)
return;
int mid = (left+right)>>1;
buildTree(left , mid , pos<<1);
buildTree(mid+1 , right , (pos<<1)+1);
}
int query(int left , int right , int pos){
if(node[pos].left == left && node[pos].right == right)
return node[pos].sum;
int mid = (node[pos].left+node[pos].right)>>1;
if(right <= mid)
return query(left , right , pos<<1);
else if(left > mid)
return query(left , right , (pos<<1)+1);
else
return query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);
}
void update(int index , int pos){
if(node[pos].left == node[pos].right){
node[pos].sum++;
return;
}
int mid = (node[pos].left+node[pos].right)>>1;
if(index <= mid)
update(index , pos<<1);
else
update(index , (pos<<1)+1);
node[pos].sum = node[pos<<1].sum+node[(pos<<1)+1].sum;
}
int main(){
while(scanf("%d" , &n) && n){
memset(vis , 0 , sizeof(vis));
for(int i = 0 ; i < n ; i++){
scanf("%d%d" , &s[i].x , &s[i].y);
s[i].number = i;
}
sort(s , s+n , cmp);
buildTree(1 , MAXN , 1);
for(int i = 0 ; i < n ; i++){
if(i && s[i] == s[i-1])
vis[s[i].number] = vis[s[i-1].number];
else
vis[s[i].number] += query(s[i].y , MAXN , 1);
update(s[i].y , 1);
}
printf("%d" , vis[0]);
for(int i = 1 ; i < n ; i++)
printf(" %d" , vis[i]);
printf("\n");
}
return 0;
}
思路:树状数组
分析:
1 题目给定n头牛所在的区间,然后问每头牛都有几头牛比它强壮
2 根据题目如果牛i的区间是[Si , Ei],牛j的区间是[Sj , Ej]那么牛i要比牛j强壮的话,那么就有Si <= Sj && Ei >= Ej && Si-Ei > Sj-Ej;
3 那么根据上面的条件,我们应该要先对n头牛的区间排序”按照S从小到大,相同S按照E从大到小排序“
4 显然排完序之后我们能够满足Si <= Sj && Ei >= Ej,但是我们应该要注意到Si-Ei > Sj-Ej,说明了排完序之后不能够相等
5 我们利用E做树状数组,如果前后两个相当那么直接更新即可
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100010;
struct Node{
int S;
int E;
int number;
bool operator<(const Node& tmp)const{
if(S < tmp.S)
return true;
else if(S == tmp.S && E > tmp.E)
return true;
return false;
}
bool operator==(const Node& tmp)const{
return S == tmp.S && E == tmp.E;
}
};
Node node[MAXN];
int n;
int ans[MAXN];
int treeNum[MAXN];
int lowbit(int x){
return x&(-x);
}
int getSum(int x){
int sum = 0;
while(x){
sum += treeNum[x];
x -= lowbit(x);
}
return sum;
}
void add(int x , int val){
while(x < MAXN){
treeNum[x] += val;
x += lowbit(x);
}
}
void solve(){
memset(ans , 0 , sizeof(ans));
memset(treeNum , 0 , sizeof(treeNum));
sort(node , node+n);
for(int i = 0 ; i < n ; i++){
int id = node[i].E;
if(i && node[i] == node[i-1])
ans[node[i].number] = ans[node[i-1].number];
else
ans[node[i].number] += i-getSum(id-1);
add(id , 1);
}
printf("%d" , ans[0]);
for(int i = 1 ; i < n ; i++)
printf(" %d" , ans[i]);
puts("");
}
int main(){
while(scanf("%d" , &n) && n){
for(int i = 0 ; i < n ; i++){
scanf("%d%d" , &node[i].S , &node[i].E);
node[i].number = i;
}
solve();
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj 2430 Lazy Cows.md
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。