ZOJ 3573 Under Attack （线段树两边维护最大值）

绝地灬酷狼 2022-06-11 09:11 137阅读 0赞

Doctor serves at a military air force base. One day, the enemy launch a sudden attack and the base is under heavy fire. The fighters in the airport must take off to intercept enemy bombers. However, the enemies know this clearly and they now focus on destroying the runway. The situation is becoming worse rapidly!

Every part of the runway has a damage level. On each bombing run, the damage level is increased by the bomb's damage . Fortunately, the enemy bombers has to stop bombing the runway when they run out of ammo. Then the ground crew have time to evaluate the situation of runway so that they can come to repair the runway ASAP after enemy attacks. The most heavily-damaged part on fighters' taking off and landing path should first be repaired. Assume that runway start from north and head to south , and fighters will take off or land only from north to south or vice versa.

Now that the task is clear, the ground crew need the cooridinates of two points: first that is the most damaged point from north to south, second is the most damaged point from south to north.The base's central mainframe is down under hacker attack. So Doctor could only use his poor little and shabby notebook to fulfill this task. Can you help him?

Input

The input consists of multiple cases.  
The first line is the runway length L. L can be up to 15000.  
Next lines will describe enemy bombing runs ,each line describes effect range startend of each bombing run and enemy bomb damage d.**if start is -1, this case ends.**.  
There can be up to 3000 bombing run, each time the damage is up to 100.  
Notice that the bombing range is from north to south, and runway range is **\[0,len\]**.

Output

Output the cooridinates of two points: first that is the most damaged point from north to south, second is the most damaged point from south to north.

Sample Input

10
    1 5 2
    6 9 2
    -1 -1 -1

Sample Output

1 9

题解：

题意：

给你个长度len,有条自北向南的铁路\[0，len\],每次输入x,y,z表示在\[x,y\]处炮轰z次，最后输入三个-1结束，问你最后从北向南数最大炮轰数的标号和从南到北数最大炮轰数的标号是哪些，很明显是线段树，就是区间合并的时候分情况讨论一下就好了

ps：

这是今天比赛的一题，无限迷之WA了好多次，比赛结束后我上午搜了十几份代码交上去都是WA，在vj上ac的都是2年前的事情了。。。后来在群里问了下是不是数据有问题，fth学长做了后也说的确数据有问题。。。好气哦，练了那么就的线段树，感觉做的也是对的因为题目数据问题就是A不了

不过感觉我的思路是对的：

就是每次区间合并下判断下情况来维护左右区间的最大值，最后的t\[1\]里面的左右最大标号就是答案了（zoj这题数据有问题是a不了的）

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        int l,r;
        int lid,rid;//表示左右第一个最大值的标号，如果该只有一个最大值则相同
        int maxc;//表示区间最大炮轰次数
        int tag;//lazy tag，延迟标志
    }t[150005*4];
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].maxc=0;
        t[k].tag=0;
        if(l==r)
        {
            t[k].lid=t[k].rid=l;//初始最下节点的左右最大id都是自己
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        t[k].lid=l;//这里要初始化一下为该区间的左右端点
        t[k].rid=r;
    }
    void pushup(int k)//区间合并，也是稍微的难点
    {
        t[k].maxc=max(t[lson].maxc,t[rson].maxc);//取最大炮轰数
        if(t[lson].maxc==t[rson].maxc)//如果相等，取左区间的左id和右区间的右id
        {
            t[k].lid=t[lson].lid;
            t[k].rid=t[rson].rid;
        }
        else if(t[lson].maxc>t[rson].maxc)//如果左区间大，全部改为左区间的左右端点
        {
            t[k].lid=t[lson].lid;
            t[k].rid=t[lson].rid;
        }
        else//如果右子区间大的情况
        {
            t[k].lid=t[rson].lid;
            t[k].rid=t[rson].rid;
        }
    }
    void pushdown(int k)//向下状态传递
    {
        if(t[k].tag)
        {
            t[lson].maxc+=t[k].tag;
            t[rson].maxc+=t[k].tag;
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            t[k].tag=0;
        }
    }
    void update(int l,int r,int k,int v)//日常更新
    {
        if(l==t[k].l&&t[k].r==r)
        {
            t[k].tag+=v;
            t[k].maxc+=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson,v);
        else if(l>mid)
            update(l,r,rson,v);
        else
        {
            update(l,mid,lson,v);
            update(mid+1,r,rson,v);
        }
        pushup(k);
    }
    int main()
    {
        int i,j,k,len,x,y,z;
        while(scanf("%d",&len)!=EOF)
        {
            Build(0,len,1);
            while(scanf("%d%d%d",&x,&y,&z)!=EOF)
            {
                if(x==-1)
                {
                    printf("%d %d\n",t[1].lid,t[1].rid);
                    break;
                }
                if(x>y)
                    swap(x,y);
                update(x,y,1,z);
            }
        }
        return 0;
    }