Skip to content

11562: 【原1562】different

题目

题目描述

author: Zhijian Liu 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1562

Description

输入一个数列,每次可以进行如下操作:

  1. 查询区间[l, r]中有多少个不同的数
  2. 在第i个位置插入一个数k(i可能为当前数列长度+1,即在最后插入一个数)
  3. 删除处于第i个位置的数
  4. 将处于第i个位置的数改为k

Input Format

第1行共两个整数n, q代表原数列的长度和操作的个数

第2行有n个整数代表原数列

第3行-q+2行,每行一个操作,第一个数代表操作的种类,后面的数代表具体操作,格式:

  • 操作1: 1 l r
  • 操作2: 2 i k
  • 操作3: 3 i
  • 操作4: 4 i k

Output Format

对于所有的操作1, 输出结果,每行一个。

Sample Input

5 7
3 3 2 5 5
1 1 5
4 3 3
1 2 4
2 6 3
1 3 6
3 1
1 1 2

Sample Output

3
2
2
1

HINT

对于10%的数据,n,q<=1000, 所有的数<=1000。

对于40%的数据,只包含操作1

对于80%的数据,只包含操作1,4

对于100%的数据,包含操作1,2,3,4, 且数列的长度在任何时候<=500000,数列中的数保证在long long范围内。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!