TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6567
  • 题目
  • P6567数列计算
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB
    评测说明 : 3s,512m
    问题描述

    何老板给你一个整数数列 \(A\) 。数列初始长度为 \(n\) 。你需要进行如下4种操作:
    $1 \ l \ r$ : 取出 \(A\) 的左起第 \(l\) 到第 \(r\) 个元素,排序,去重,设所得数列为 \(S\) ,你需要计算:

    $2 \ x \ y$ :将 \(A\) 的左起第 \(x\) 个元素的值改为 \(y\)
    $3 \ x$ : 将 \(A\) 的左起第 \(x\) 个元素删除;
    $4 \ x \ y$ : 在 \(A\) 的左起第 \(x\) 个元素后插入 \(y\) ,若 $x==0 $,则把$y$ 插入在数列开头;

    输入格式

    第一行,两个整数 \(n\)\(q\) ,分别表示数列初始长度和操作总数。
    第二行, \(n\) 个整数,表示数列A的初始状态。
    接下来 \(q\) 行,每行表示一个操作。对于第1号操作,你需要输出它们的操作结果。

    输出格式

    若干行,每行对应一个第1号操作的结果。

    样例输入 1

    5 7
    1 2 3 2 1
    1 1 3
    2 2 4
    1 2 4
    3 3
    4 0 5
    1 1 2
    1 1 5

    样例输出 1

    6
    24
    0
    78

    样例说明:

    操作 1,第 1 个到第 3 个元素之间不同的元素排序后得到 S = {1, 2, 3},故答案为 1 × 2 × 3 = 6。
    操作 2,序列 A 变为 [1, 4, 3, 2, 1]。
    操作 3,第 2 个到第 4 个元素之间不同的元素排序后得到 S = {2, 3, 4},故答案为 2×3×4 = 24。
    操作 4,序列 A 变为 [1, 4, 2, 1]。
    操作 5,序列 A 变为 [5, 1, 4, 2, 1]。
    操作 6,第 1 个到第 2 个元素之间不同的元素排序后得到 S = {1, 5},故答案为 0。
    操作 7,第 1 个到第 5 个元素之间不同的元素排序后得到 S = {1, 2, 4, 5},故答案为 1 × 2 × 4 +1 × 2 × 5 + 1 × 4 × 5 + 2 × 4 × 5 = 78。

    样例输入 2

    10 15
    5 4 3 5 4 1 5 4 3 1
    2 8 580347
    4 6 503576
    1 2 5
    1 8 11
    1 2 6
    4 7 565239
    3 6
    3 11
    3 3
    2 9 674360
    1 1 6
    2 2 589693
    4 5 236488
    1 8 9
    1 2 7

    样例输出 2

    60
    13347996
    107
    788510349
    0
    806255740

    提示

    对于20%的数据:\(n,q<=1000\)
    对于100%的数据:$1<=n,q<=100000;1<=A_i,y<=10^9+7;0<=x<=|A|;1<=l<=r<=|A|; $
    保证对于2,3操作:\(x>=1\)


    来源  jz6441简化版