ZOJ 3453 Doraemon's Sweet Bullet（线段树区间更新+单点更新+最值询问）

悠悠 2022-06-10 11:27 137阅读 0赞

Doraemon likes to shoot his enemies with sweet bullets.

*n* "enemies" stand in a line, each with a life value *li* (the index *i* increases from left to right side and starts from 1). Each time Doraemon shoots a sweet bullet from the right side. The *i*th bullet has a "critical range" *ki*. That is to say, it attacks the first enemy from right side whose life value is equal to or greater than *ki*. The life value of the attacked enemy will decrease to 1 immediately.

However, Doraemon finds a terrible fact that after an enemy is attacked, it will distribute the sweets to his friends and his friends' life value will increase by 1. For the *i*th enemy, his friends are in a consecutive range from the *ai*th enemy to the *bi*th. Note that an enemy may be the friend of himself so that after being attacked his life value will be 2.

What's more, if a bullet can't find a target--there doesn't exist an enemy with life greater or equal than *ki*, all enemies' life will increase by 1.

Now Doraemon wants to know after *m* bullets were shot, what the maximum life value in all enemies is.

Input

The input contains multiple test cases.

Each test case begins with a line containing a single integer *n* (1 ≤ *n* ≤ 100000) indicating the number of enemies.

The following n lines describes enemies, one enemy each line. Each line contains three integers, the initial life value *li* (1 ≤ *li* ≤ 10000) and his range of friends *ai bi* (1 ≤ *ai* ≤ *bi*≤ n) - that is, enemies with index from *ai* to *bi*(inclusive) are all his friends.

The following line contains an integer *m* (1 ≤ *m* ≤ 100000) indicating the number of bullets Doraemon has shot. The last *m* lines follows, each with a single integer *ki*(1 ≤ *ki* ≤ 10000) describing the bullet's "critical range".

Different cases are separated by a blank line.

Process to the end of input.

Output

For each test case, output the maximum life value after shooting in a single line.

Sample Input

3
    3 1 2
    4 1 3
    5 1 1
    3
    4
    2
    1

Sample Output

Hint

Doraemon suggests that you should use *scanf* to read data.

题解：

题意：

多啦B梦有n个敌人，每个敌人有一个v值，每次他从右边开一枪，子弹有一个val值，只要最先大于或者等于val值的那个人v值就会变成1，然后刚开始输入的时候顺带有说这个人的同伙为\[l,r\]区域的人，这些人知道他中枪了v值就会++，如果子弹没打中任何一个人就会全体v值++，问最后最大的v值是多少

思路：

直接用区间最值更新就行了，就是查询的时候稍微变动一下，本来是不难的一题，结果比赛的时候因为一个pushup写成了pushdown，本来一个小时就应该秒掉的题目检查到了比赛2个小时才发现。。。我为什么那么智障

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct peo//存人的初始信息
    {
        int l,r;
        int v;
    }p[100005];
    struct node
    {
        int l,r;
        int tag;//lazy tag，表示要加的值
        int maxx;//区间极值
    }t[100005*4];
    void pushup(int k)//向上传递更新
    {
        t[k].maxx=max(t[lson].maxx,t[rson].maxx);
    }
    void Build(int l,int r,int k)//日常建树
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag=0;
        if(l==r)
        {
            t[k].maxx=p[r].v;
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        pushup(k);
    }
    void pushdown(int k)//日常下推标记
    {
        if(t[k].tag!=0)
        {
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            t[lson].maxx+=t[k].tag;
            t[rson].maxx+=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].maxx+=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);
    }
    void update1(int pos,int k)//日常单点更新
    {
        if(t[k].l==pos&&pos==t[k].r)
        {
            t[k].maxx=1;
            return;
        }
        pushdown(k);
        int mid=M;
        if(pos<=mid)
            update1(pos,lson);
        else
            update1(pos,rson);
        pushup(k);
    }
    int query(int l,int r,int k,int v)//有点变化的询问
    {
        if(l==r)
        {
            return l;
        }
        pushdown(k);
        int mid=M;
        if(t[rson].maxx>=v)//如果右边极值满足情况就询问右边
           return query(mid+1,r,rson,v);
        else
           return query(l,mid,lson,v);
    }
    int main()
    {
        int i,j,n,m,q,x;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=1;i<=n;i++)
            {
                scanf("%d%d%d",&p[i].v,&p[i].l,&p[i].r);
            }
            Build(1,n,1);
            scanf("%d",&m);
            while(m--)
            {
                scanf("%d",&x);
                if(t[1].maxx<x)//如果最大区间最大值都小于x
                {
                    update(1,n,1,1);
                }
                else
                {
                    int d=query(1,n,1,x);
                    update1(d,1);//注意是先单点更新。。一开始我还以为朋友不能包括自己
                    update(p[d].l,p[d].r,1,1);
                }
            }
            printf("%d\n",t[1].maxx);
        }
        return 0;
    }