P3309 [SDOI2014]向量集

    • 141通过
    • 610提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 凸包 向量 线段树 2014 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    维护一个向量集合,在线支持以下操作:

    • "A x y (|x|,|y| < =10^8)":加入向量(x,y);
    • " Q x y l r (|x|,|y| < =10^8,1 < =L < =R < =T,其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x,y)的点积的最大值。

    集合初始时为空。

    输入输出格式

    输入格式:

    输入的第一行包含整数N和字符s,分别表示操作数和数据类别; 接下来N行,每行一个操作,格式如上所述。

    请注意s≠'E'时,输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入: ··· inline int decode (int x long long lastans) {
    return x ^ (lastans & Ox7fffffff); }

    
    其中x为程序读入的数,lastans为之前最后一次询问的答案。在第一次询问之前,lastans=0。注:向量(x,y)和(z,W)的点积定义为xz+yw。

    输出格式:

    对每个Q操作,输出一个整数表示答案。

    输入输出样例

    输入样例#1: 复制
    6 A
    A 3 2
    Q 1 5 1 1
    A 15 14
    A 12 9
    Q 12 8 12 15
    Q 21 18 19 18
    输出样例#1: 复制
    13
    17
    17
    

    说明

    样例解释:解密之后的输入为

        6 E
        A 3 2
        Q 1 5 1 1
        A 2 3
        A 1 4
        Q 1 5 1 2
        Q 4 3 2 3

    1 < =N < =4*10^5

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