萌新求助QAQ!!!

P4513 小白逛公园

resftlmuttmotw @ 2019-08-09 10:54:55

题目

只有第一个点对了

#include <cmath>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
#define isdigit(x) ('1' <= (x)&&(x) <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0;
    bool f = 0;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = 1;a = getchar();}
    while(isdigit(a)) x = (x << 1) + (x << 3) + a - '0',a = getchar();
    if(f) x *= -1;
    return x;
}
const int MAXN = 500005;
int Left,Right,a[MAXN];
struct Node
{
    int maxl,L_max,R_max,Mid_max,sum;
}Tree[MAXN << 2];
inline void Tree_build(int l,int r,int k)
{
    if(l == r)
    {
        Tree[k].sum = Tree[k].maxl = Tree[k].L_max = Tree[k].Mid_max = Tree[k].R_max = a[l];
        return;
    }
    int mid = l + r >> 1,k1 = k << 1;
    int k2 = k1 ^ 1;
    Tree_build(l,mid,k1);
    Tree_build(mid + 1,r,k2);
    Tree[k].sum = Tree[k1].sum + Tree[k2].sum;
    Tree[k].maxl = max(Tree[k1].maxl,Tree[k2].maxl);
    Tree[k].L_max = max(Tree[k1].L_max,Tree[k1].sum + Tree[k2].L_max);
    Tree[k].R_max = max(Tree[k2].R_max,Tree[k2].sum + Tree[k1].R_max);
    Tree[k].Mid_max = Tree[k1].R_max + Tree[k2].L_max;
    Tree[k].maxl = max(Tree[k].maxl,Tree[k].Mid_max);
    //printf("%d %d %d %d %d\n",l,r,Tree[k].maxl,Tree[k].L_max,Tree[k].R_max);
}
inline void modify(int l,int r,int k,int p,int s)
{
    if(l == r)
    {
        Tree[k].sum = Tree[k].maxl = Tree[k].L_max = Tree[k].Mid_max = Tree[k].R_max = s;
        return;
    }
    int mid = l + r >> 1,k1 = k << 1;
    int k2 = k1 ^ 1;
    if(p <= mid) modify(l,mid,k1,p,s);
    else modify(mid + 1,r,k2,p,s);
    Tree[k].sum = Tree[k1].sum + Tree[k2].sum;
    Tree[k].maxl = max(Tree[k1].maxl,Tree[k2].maxl);
    Tree[k].L_max = max(Tree[k1].L_max,Tree[k1].sum + Tree[k2].L_max);
    Tree[k].R_max = max(Tree[k2].R_max,Tree[k2].sum + Tree[k1].R_max);
    Tree[k].Mid_max = Tree[k1].R_max + Tree[k2].L_max;
    Tree[k].maxl = max(Tree[k].maxl,Tree[k].Mid_max);
    //printf("%d %d %d\n",l,r,Tree[k].maxl);
}
inline Node query(int l,int r,int k)
{
    if(Left <= l&&r <= Right) return Tree[k];
    int mid = l + r >> 1;
    if(Right <= mid) return query(l,mid,k << 1);
    else if(mid < Left) return query(mid + 1,r,k << 1 ^ 1);
    else {
        Node New,a1 = query(l,mid,k << 1),a2 = query(mid + 1,r,k << 1 ^ 1);
        New.maxl = max(a1.maxl,a2.maxl);
        New.Mid_max = a1.R_max + a2.L_max;
        New.maxl = max(New.maxl,New.Mid_max);
        New.L_max = max(a1.L_max,a1.sum + a2.L_max);
        New.R_max = max(a2.R_max,a2.sum + a1.R_max);
        New.sum = a1.sum + a2.sum;
        return New;
    }
}
int main()
{
    int i,n = Read(1),m = Read(1);
    for(i = 1;i <= n;i++) a[i] = Read(1);
    Tree_build(1,n,1);
    while(m--)
    {
        int k = Read(1);
        Left = Read(1),Right = Read(1);
        if(k == 1)
        {
            if(Left > Right) swap(Left,Right);
            Node Ans = query(1,n,1);
            printf("%d\n",Ans.maxl);
        } else modify(1,n,1,Left,Right);
    }
    return 0;
}

by lx_zjk @ 2019-08-20 21:32:54

query有问题啊


by resftlmuttmotw @ 2019-08-21 18:34:15

@Hock

其实是读入优化写错了


|