首页 > 代码库 > POJ 3263 Tallest Cow（线段树）

POJ 3263 Tallest Cow（线段树）

2024-07-16 09:10:02   218人阅读

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;
}




联系
我们