WUST 1255 巧克力（线段树的单点区间更新查询）

╰+哭是因爲堅強的太久メ 2022-06-11 09:58 196阅读 0赞

## 1355: 巧克力 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 190 Accepted: 26  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

TY最喜欢做的事情就是吃巧克力，经常幻想拥有吃不完的巧克力，作为一个acmer(菜机），IcY出了个问题准备考考她，如果回答出来，那巧克力自然是源源不断的啦。

IcY给出了一列排好的的巧克力，有的是德芙，有的是费列罗，它们都拥有不同的美味值……现在IcY通过魔法更改了这些巧克力，TY必须能指出排列中第K个是巧克力的美味值是多少和某一段巧克力中最美味的值是多少，才能吃到巧克力，否则，哼哼，就去乖乖的做题吧。现在，TY来寻求你的帮助，你能让poor TY吃上巧克力吗？

## Input ##

输入数据有很多组，以EOF结尾。

每组数据第一行是2个整数N，M。N代表初始的巧克力数目，M代表操作数。

第二行含有n个正整数，代表每块巧克力的美味值wi。每块巧克力的下标从0--n-1。

接下来的M行，表示M个操作。

操作分4种：

Query x y 代表查询某一个区间内的美味最大值。

Ask x 代表查询某一块巧克力的美味值。

Change x y 代表将第x块的美味值变成y

Add x y 代表讲从第x块到第y块巧克力的美味值分别增加1.

（1 <= N<= 1000001<= M <= 100000Wi <= 5000 ）

## Output ##

对于每一个Query输出一个整数，代表区间内的美味最大值。

对于每一个Ask 输出一个整数，代表这块巧克力的美味值。

## Sample Input ![copy.gif][] ##

10 4
    1 2 3 4 5 6 7 8 9 10
    Ask 0
    Change 0 1
    Add 0 2
    Query 0 2

##     ##

## Sample Output ##

1
    4

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

这是我们学校oj的一题，老赵看到很多人tle就让我做了，第一次数组开小了就TLE了，改了下就过了。。。考察的比较基础，还有就是要lazy tag不然会超时，对于经历过线段树专题的我这题还是很水的hhhhh，500ms过的

代码：

#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 maxx;//区间极值
        int tag;//延迟标记
    }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)
        {
            scanf("%d",&t[k].maxx);
            return;
        }
        int mid=M;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
        pushup(k);
    }
    void pushdown(int k)//向下更新
    {
        if(t[k].tag)
        {
            t[lson].maxx+=t[k].tag;
            t[rson].maxx+=t[k].tag;
            t[lson].tag+=t[k].tag;
            t[rson].tag+=t[k].tag;
            t[k].tag=0;
        }
    }
    void update1(int l,int r,int k,int v)//线段树的区间更新
    {
        if(t[k].l==l&&t[k].r==r)
        {
            t[k].maxx+=v;
            t[k].tag+=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update1(l,r,lson,v);
        else if(l>mid)
            update1(l,r,rson,v);
        else
        {
            update1(l,mid,lson,v);
            update1(mid+1,r,rson,v);
        }
        pushup(k);
    }
    void update2(int x,int k,int v)//线段树的单点更新
    {
        if(t[k].l==t[k].r)
        {
            t[k].maxx=v;
            return;
        }
        pushdown(k);
        int mid=M;
        if(x<=mid)
            update2(x,lson,v);
        else
            update2(x,rson,v);
        pushup(k);
    }
    int query1(int l,int r,int k)//线段树的区间查询
    {
        if(t[k].l==l&&t[k].r==r)
        {
            return t[k].maxx;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            return query1(l,r,lson);
        else if(l>mid)
            return query1(l,r,rson);
        else
        {
            return max(query1(l,mid,lson),query1(mid+1,r,rson));
        }
    }
    int query2(int x,int k)//线段树的单点查询
    {
        if(t[k].l==t[k].r)
        {
            return t[k].maxx;
        }
        pushdown(k);
        int mid=M;
        if(x<=mid)
            return query2(x,lson);
        else
            return query2(x,rson);
    }
    int main()
    {
        int n,m,i,j,x,y,z;
        char s[10];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Build(0,n-1,1);
            for(i=0;i<m;i++)
            {
                scanf("%s",s);//可以跳掉空格换行
                if(strcmp(s,"Ask")==0)
                {
                    scanf("%d",&x);
                    printf("%d\n",query2(x,1));
                }
                else if(strcmp(s,"Change")==0)
                {
                    scanf("%d%d",&x,&y);
                    update2(x,1,y);
                }
                else if(strcmp(s,"Add")==0)
                {
                    scanf("%d%d",&x,&y);
                    if(x>y)
                        swap(x,y);
                    update1(x,y,1,1);
                }
                else
                {
                    scanf("%d%d",&x,&y);
                    if(x>y)
                        swap(x,y);
                    printf("%d\n",query1(x,y,1));
                }
            }
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1355&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1355&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1355&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif