萌新求教,过了样例,几乎全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 TG178X @ 2023-01-16 12:03:34

考古


by 13402805827wuaiyang @ 2023-01-16 12:04:12

考古


by 大眼仔Happy @ 2023-10-07 21:11:02

烤咕


by loser_wanghan @ 2024-02-14 18:11:17

考古


by miffy_123 @ 2024-12-21 13:33:47

烤咕


上一页 |