萌新求教,过了样例,几乎全WA

P4513 小白逛公园

chen_zhe @ 2018-05-02 21:29:11

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int value;
    int left,right;
}son[2200000];

int father[2200000],n,m,Max;

void build(int id,int left,int right)
{
    son[id].left=left,son[id].right=right;
    if (left==right)
    {
        father[left]=id;
        return;
    }
    build(id<<1,left,(left+right)>>1);
    build((id<<1)+1,((left+right)>>1)+1,right);
}

void update_single(int r)
{
    if (r==1) return;
    int r1=r/2;
    int a=son[r1<<1].value;
    int b=son[(r1<<1)+1].value;
    son[r1].value=a>b?a:b;
    update_single(r>>1);
}

void query(int id,int left,int right)
{
    if (son[id].left>=left && son[id].right<=right)
    {
        Max=Max>son[id].value?Max:son[id].value;
        return;
    }
    id=id<<1;
    if (left<=son[id].right)
    {
        if (right<=son[id].right)
            query(id,left,right);
        else query(id,left,son[id].right);
    }
    id++;
    if (right>=son[id].left)
    {
        if (left>=son[id].left)
            query(id,left,right);
        else query(id,son[id].left,right);
    }
}

int main()
{
    //ios_base::sync_with_stdio(0);
    cin >> n >> m;
    build(1,1,n);
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >> a;
        son[father[i]].value=a;
        update_single(father[i]);
    }
    for (int i=1;i<=m;i++)
    {
        int k,a,b;
        cin >> k;
        if (k==1)
        {
            Max=-1<<30;
            cin >> a >> b;
            if (a>b)
            {
                int t=a;
                a=b;
                b=t;
            }
            query(1,a,b);
            cout << Max << endl;
        }
        else
        {
            cin >> a >> b;
            son[father[a]].value=b;
            update_single(father[a]);
        }
    }
    return 0;
}

by 长河落日 @ 2018-05-03 06:36:07

@Refun 自插双目


by 绝顶我为峰 @ 2018-06-16 16:31:18

看到chen_zhe大佬求助,本蒟蒻不敢说话

kkk


by 斗神_君莫笑 @ 2019-08-05 11:51:13

考古


by Mosher @ 2019-09-09 15:10:28

考古


by DarkValkyrie @ 2019-12-04 20:02:45

考古


by Velix @ 2020-06-24 23:09:01

考古


by 显微镜 @ 2021-07-14 08:17:08

考古


by 黄哟哟哟 @ 2022-02-09 14:38:07

考古


by 岂非 @ 2022-03-21 22:33:22

考古

顺便%峰队


by luoyx @ 2022-11-05 19:05:03

考古


上一页 | 下一页