时间戳

首页 > 解决方案 > 为什么我会为 SPOJ 上的 GSS1 问题的此代码获取 TLE？（使用段树）

c++ - 为什么我会为 SPOJ 上的 GSS1 问题的此代码获取 TLE？（使用段树）

问题描述

问题链接：- https://www.spoj.com/problems/GSS1

  1. 我正在使用段树。

    节点信息：-

  2. maxSum --> 节点表示的段的最大总和。

  3. Sum ---> 段的总和。（虽然我觉得没必要）
  4. maxPrefixSum ---> 段中可能的最大前缀总和。即从段的第一个元素开始。
  5. maxSuffixSum ---> 与 maxPrefixSum 相同，但从段的最后一个元素开始。

节点值的计算：-

（“res”是新节点，“left”和“right”分别是它的左右孩子）
res.Sum = left.Sum + right.Sum;
res.maxSum = max(max(left.maxSum, right.maxSum), left.maxSuffixSum + right.maxPrefixSum);
res.maxSuffixSum = max(left.maxSuffixSum + right.Sum, right.maxSuffixSum);
res.maxPrefixSum = max(left.maxPrefixSum, left.Sum + right.maxPrefixSum);

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long int

class node
{
public:
    int Sum, maxSuffixSum, maxPrefixSum, maxSum;
    node()
    {
        Sum = maxSuffixSum = maxPrefixSum = maxSum = 0;
    }
};

node node_value(node left, node right)
{
    node res;
    res.Sum = left.Sum + right.Sum;
    res.maxSum = max(max(left.maxSum, right.maxSum), left.maxSuffixSum + right.maxPrefixSum);
    res.maxSuffixSum = max(left.maxSuffixSum + right.Sum, right.maxSuffixSum);
    res.maxPrefixSum = max(left.maxPrefixSum, left.Sum + right.maxPrefixSum);
    return res;
}

void makeSegmentTree(vector<int> arr, vector<node> &tree, int idx, int start, int finish)
{
    if(finish == start)
    {
        tree[idx].Sum = tree[idx].maxPrefixSum = tree[idx].maxSuffixSum = tree[idx].maxSum = arr[start];
        return;
    }

    int mid = start + (finish - start)/2;
    makeSegmentTree(arr, tree, 2*idx, start, mid);
    makeSegmentTree(arr, tree, 2*idx+1, mid+1, finish);
    tree[idx] = node_value(tree[2*idx], tree[2*idx + 1]);
}

node queryTree(vector<node> &tree, int idx, int start, int finish, int left, int right)
{
    if(start >= left && finish <= right)
    {
        return tree[idx];
    }
    else
    {
        int mid = start + (finish - start)/2;
        if(start <= left && right <= mid)
        {
            return queryTree(tree, 2*idx, start, mid, left, right);
        }
        else if(left > mid && right <= finish)
        {
            return queryTree(tree, 2*idx+1, mid+1, finish, left, right);
        }
        else
        {
            node ans1 = queryTree(tree, 2*idx, start, mid, left, mid);
            node ans2 = queryTree(tree, 2*idx+1, mid+1, finish, mid+1, right);
            return node_value(ans1, ans2);
        }
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int> arr(n+1, 0);
    for(int i=1;i<n+1;i++)
    {
        cin>>arr[i];
    }


    vector< node > tree(4*n);
    makeSegmentTree(arr, tree, 1, 1, n);

    int q;

    cin>>q;
    while(q--)
    {
        int x, y;
        cin>>x>>y;
        cout<<queryTree(tree, 1, 1, n, x, y).maxSum<<endl;
    }
    return 0;
}

标签： c++segment-tree

解决方案

推荐阅读