SP1043 GSS1 - Can you answer these queries I

    • 807通过
    • 2.6K提交
  • 题目来源 SPOJ 1043
  • 评测方式 RemoteJudge
  • 标签 分治 前缀和 线段树
  • 难度 省选/NOI-
  • 时空限制 230ms / 1536MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    给出了序列 $A[1],A[2],…,A[N]$ 。 ($ a[i]≤15007,1≤N≤50000$ )。查询定义如下: 查询 $(x,y)=\max\{a[i]+a[i+1]+...+a[j];x≤i≤j≤y\}$。 给定$M$个查询,程序必须输出这些查询的结果。

    输入输出格式

    输入格式:

    • 输入文件的第一行包含整数$N$。
    • 在第二行,$N$个数字跟随。
    • 第三行包含整数$M$。
    • M行跟在后面,其中第1行包含两个数字$x_i$和$y_i$。

    输出格式:

    您的程序应该输出$M$查询的结果,每一行一个查询。

    感谢@何高琛 提供的翻译

    题目描述

    You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
    Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
    Given M queries, your program must output the results of these queries.

    输入输出格式

    输入格式:

    • The first line of the input file contains the integer N.
    • In the second line, N numbers follow.
    • The third line contains the integer M.
    • M lines follow, where line i contains 2 numbers xi and yi.

    输出格式:

    Your program should output the results of the M queries, one query per line.

    输入输出样例

    输入样例#1: 复制
    3 
    -1 2 3
    1
    1 2
    输出样例#1: 复制
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。