POJ 3263 Tallest Cow(线段树)
Description FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow. FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17. For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints. Input
Line 1: Four space-separated integers: N, I, H and R
Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B. Output
Lines 1..N: Line i contains the maximum possible height of cow i.
Sample Input 9 3 5 5 1 3 5 3 4 3 3 7 9 8 Sample Output 5 4 5 3 4 4 5 5 5 线段树的思想是对的,卧槽。比赛wa了8发都没过。还以为算法错了。看了discuss。
POJ,你的节操了,弄的重边。无力吐槽。。。
题意:n个牛排队,给你两个牛的编号x,y,要求x能看见y.且中间牛的高度要小。 求所 牛的最大可能身高。线段树思想:先将全部牛的高度设为最高的H,对于给定的区间 x,y,将(x,y)中的值都减1.最后输出就能够了=-=
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> using namespace std; const int maxn=10000+100; int LL[maxn],RR[maxn]; long long N,H,R,I; long long add[maxn<<2],ans[maxn]; struct node{ int l,r; int sum; }t[maxn<<2]; void pushdown(int rs)//向下更新lazy积累的值 { if(add[rs]) { add[rs<<1]+=add[rs]; add[rs<<1|1]+=add[rs]; add[rs]=0; } } void build(int rs,int l,int r) { t[rs].l=l; t[rs].r=r; add[rs]=0; if(l==r) { t[rs].sum=H; return ; } int mid=(l+r)>>1; build(rs<<1,l,mid); build(rs<<1|1,mid+1,r); } void update(int l,int r,int rs)//更新操作 { // cout<<"fuck "<<t[rs].l<<" "<<t[rs].r<<endl; if(t[rs].l>=l&&t[rs].r<=r) { // cout<<"fuck2"<<endl; add[rs]+=1; return ; } pushdown(rs); int mid=(t[rs].l+t[rs].r)>>1; if(l<=mid) update(l,r,rs<<1); if(r>mid) update(l,r,rs<<1|1); } int query(int k,int rs) { if(t[rs].l==t[rs].r) { return t[rs].sum-=add[rs]; } pushdown(rs); int mid=(t[rs].l+t[rs].r)>>1; if(k<=mid) return query(k,rs<<1); else return query(k,rs<<1|1); } int main() { int u,v; while(~scanf("%I64d%I64d%I64d%I64d",&N,&I,&H,&R)) { build(1,1,N); int k=0; while(R--) { scanf("%d%d",&u,&v); if(u>v) swap(u,v); int flag=1; for(int i=0;i<k;i++)//推断重边,在poj做题一定要防这东西 { if(u==LL[i]&&v==RR[i]) { flag=0; break; } } if(!flag) continue; LL[k]=u;RR[k]=v; k++; if(v-u==1)//相邻的话就不用更新了 continue; update(u+1,v-1,1);//注意是开区间的值更新 } for(int i=1;i<=N;i++) ans[i]=query(i,1); for(int i=1;i<=N;i++) printf("%I64d\n",ans[i]); } return 0; }
|
相关文章
- 【POJ 1850】 Code
- POJ 1144 Network(无向图连通分量求割点)
- poj 1088 滑雪
- POJ 1785 Binary Search Heap Construction (线段树)
- POJ 1655 Balancing Act
- POJ 2229 Sumsets
- POJ 2828 Buy Tickets (线段树)
- POJ 2311 Cutting Game (博弈)
- POJ 1127 Jack Straws (线段相交)
- POJ 2823 Sliding Window (单调队列)
- POJ 3468 A Simple Problem with Integers (线段树)
- POJ 1458 Common Subsequence (DP+LCS,最长公共子序列)
- POJ 3278 Catch That Cow
- 【POJ 1269】判断两直线相交
- POJ 1961 Period
- [ACM] POJ 3253 Fence Repair (Huffman树思想,优先队列)
- POJ 1088: 滑雪(经典 DP+记忆化搜索)
- [ACM] POJ 2689 Prime Distance (筛选范围大素数)