andyli

题解 UVA1400 【"Ray, Pass me the dishes!"】
本题看上去很像$RMQ$问题,但稍微琢磨一下就会发现本题和$RMQ$的重要区别:整个区间的解不能简单地通过各个子区...
扫描右侧二维码阅读全文
20
2019/06

题解 UVA1400 【"Ray, Pass me the dishes!"】

本题看上去很像$RMQ$问题,但稍微琢磨一下就会发现本题和$RMQ$的重要区别:整个区间的解不能简单地通过各个子区间的解合并得到,所以$Sparse-Table$算法中的预处理和查询部分均不适用于本题。
本题的静态版本最大连续和子序列,它有一个分治算法:最优解要么完全在左半序列,要么完全在右半序列,要么跨越中点。由于线性算法的存在,这个算法可能并没有引起很多人的重视,但这个思路却是解决本题的关键。
构造一棵线段树,其中每个结点维护$3$个值:最大连续和$max$_$sub$、最大前缀和$max$_$prefix$与最大后缀和$max$_$suffix$。具体来说,$max$_$sub(a,b)$是满足$a\le x\le y\le b$且$D_x+D_{x+1}+...+D_y$的最大二元组$(x,y)$;$max$_$prefix(a,b)$是满足$a\le x\le b$且$D_a+D_{a+1}+...+D_x$最大的整数$x$;$max$_$suffix(a,b)$是满足$a\le x\le b$且$D_x+D_{x+1}+...+D_b$最大的整数$x$。
比如,$n=64$,询问为$(20,50)$,则线段$[20,50]$在线段树的根结点处被分成了两条线段$[20,32]$和$[33,50]$。则$max$_$sub(20,50)$的起点和终点有$3$种情况。
情况1:起点和终点都在$[20,32]$中,则$max$_$sub(20,50)=max$_$sub(20,32)$。
情况2:起点和终点都在$[33,50]$中,则$max$_$sub(20,50)=max$_$sub(33,50)$。
情况3:起点在$[20,32]$中,终点在$[33,50]$中,则$max$_$sub(20,50)=(max$_$suffix(20,32),max$_$prefix(33,50))$。
类似地,$max$_$prefix$和$max$_$suffix$也可以这样递推。建树的时间复杂度为$O(n)$,单组查询的时间复杂度为$O(\log n)$。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005, maxnode = 1000005;
typedef long long LL;
typedef pair<int, int> Interval;

LL prefix_sum[maxn];

LL sum(int L, int R)
{
  return prefix_sum[R] - prefix_sum[L - 1];
}

LL sum(Interval p)
{
  return sum(p.first, p.second);
}

Interval better(Interval a, Interval b)
{
  if (sum(a) != sum(b))
    return sum(a) > sum(b) ? a : b;
  return a < b ? a : b; // 利用pair自带的字典序
}

int qL, qR;

struct IntervalTree
{
  int max_prefix[maxnode];
  int max_suffix[maxnode];
  Interval max_sub[maxnode];

  void build(int o, int L, int R)
  {
    if (L == R)
    {
      max_prefix[o] = max_suffix[o] = L;
      max_sub[o] = make_pair(L, L);
    }
    else
    {
      int M = L + (R - L) / 2;
      // 递归创建子树
      int lc = o * 2, rc = o * 2 + 1;
      build(lc, L, M);
      build(rc, M + 1, R);

      // 递推max_prefix
      LL v1 = sum(L, max_prefix[lc]);
      LL v2 = sum(L, max_prefix[rc]);
      if (v1 == v2)
        max_prefix[o] = min(max_prefix[lc], max_prefix[rc]);
      else
        max_prefix[o] = v1 > v2 ? max_prefix[lc] : max_prefix[rc];

      // 递推max_suffix
      v1 = sum(max_suffix[lc], R);
      v2 = sum(max_suffix[rc], R);
      if (v1 == v2)
        max_suffix[o] = min(max_suffix[lc], max_suffix[rc]);
      else
        max_suffix[o] = v1 > v2 ? max_suffix[lc] : max_suffix[rc];

      // 递推max_sub
      max_sub[o] = better(max_sub[lc], max_sub[rc]);                              // 完全在左子树或者右子树
      max_sub[o] = better(max_sub[o], make_pair(max_suffix[lc], max_prefix[rc])); // 跨越中线
    }
  }

  Interval query_prefix(int o, int L, int R)
  {
    if (max_prefix[o] <= qR)
      return make_pair(L, max_prefix[o]);
    int M = L + (R - L) / 2;
    int lc = o * 2, rc = o * 2 + 1;
    if (qR <= M)
      return query_prefix(lc, L, M);
    Interval i = query_prefix(rc, M + 1, R);
    i.first = L;
    return better(i, make_pair(L, max_prefix[lc]));
  }

  Interval query_suffix(int o, int L, int R)
  {
    if (max_suffix[o] >= qL)
      return make_pair(max_suffix[o], R);
    int M = L + (R - L) / 2;
    int lc = o * 2, rc = o * 2 + 1;
    if (qL > M)
      return query_suffix(rc, M + 1, R);
    Interval i = query_suffix(lc, L, M);
    i.second = R;
    return better(i, make_pair(max_suffix[rc], R));
  }

  Interval query(int o, int L, int R)
  {
    if (qL <= L && R <= qR)
      return max_sub[o];
    int M = L + (R - L) / 2;
    int lc = o * 2, rc = o * 2 + 1;
    if (qR <= M)
      return query(lc, L, M);
    if (qL > M)
      return query(rc, M + 1, R);
    Interval i1 = query_prefix(rc, M + 1, R); // 右半的前缀
    Interval i2 = query_suffix(lc, L, M);     // 左半的后缀
    Interval i3 = better(query(lc, L, M), query(rc, M + 1, R));
    return better(make_pair(i2.first, i1.second), i3);
  }
};

IntervalTree tree;

int main()
{
  int kase = 0, n, a, Q;
  while (scanf("%d%d", &n, &Q) == 2)
  {
    prefix_sum[0] = 0;
    for (int i = 0; i < n; i++)
    {
      scanf("%d", &a);
      prefix_sum[i + 1] = prefix_sum[i] + a;
    }
    tree.build(1, 1, n);
    printf("Case %d:\n", ++kase);
    while (Q--)
    {
      int L, R;
      scanf("%d%d", &L, &R);
      qL = L;
      qR = R;
      Interval ans = tree.query(1, 1, n);
      printf("%d %d\n", ans.first, ans.second);
    }
  }
  return 0;
}
Last modification:June 25th, 2019 at 11:24 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment