[Ynoi2000] rfrqwq

Luogu

IDLGP9998

Time8000ms

Memory64MB

DifficultyP6

2000O2优化Ynoi

给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\le x<j$ 且 $a_x\neq a_{x+1}$。有 $m$ 次操作： `1 l r x`：表示将区间 $[l,r]$ 中所有元素都修改为 $x$。 `2 l r x`：表示查询区间 $[l,r]$ 中，对任意 $l\le i<j\le r$，且 $a_i=a_j=x$，$f(i,j)$ 的和。 ## Input 第一行两个数 $n,m$。第二行 $n$ 个用空格隔开的数表示序列 $a$。之后 $m$ 行，每行四个用空格隔开的数 $opt,l,r,x$ 表示一次操作。 ## Output 对每个 $2$ 操作，输出一行一个数表示答案。 [samples] ## Note Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078 对于 $20\%$ 的数据，满足 $1\le n,m\le 1000$。对于另外 $20\%$ 的数据，没有 $1$ 操作。对于另外 $10\%$ 的数据，数据中的操作类型在 $[1,2]$ 内， $a_i,x$ 在 $[1,100]$ 内均匀随机生成，区间 $[l,r]$ 两个端点为 $[1,n]$ 中均匀随机生成的整数，如果生成后 $l>r$，则将二者交换。对于另外 $30\%$ 的数据，满足 $1\le n,m\le 10^5$。对于 $100\%$ 的数据，满足 $1\le n,m \le 5\times10^5$，$1\le l\le r\le n$，$1\le a_i,x\le n$，所有输入均为整数。

Samples

Input #1

10 10
2 1 2 1 8 3 2 1 2 2
2 6 9 2
2 3 10 2
2 2 10 2
2 1 3 2
2 4 10 1
1 2 4 2
2 3 10 2
2 2 7 1
2 2 7 2
2 3 6 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi2000] rfrqwq",
    "description": {
      "content": "给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。 定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\\le x<j$ 且 $a_x\\neq a_{x+1}$。 有 $m$ 次操作： `1 l r x`：表示将区间 $[l,r]$ 中所有元素都修改为 $x$。 `2 l r x`：表示查询区间 $[l,r]$ 中，对任意 $l\\le i<j\\le r$，且",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9998"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。\n\n定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\\le x<j$ 且 $a_x\\neq a_{x+1}$。\n\n有 $m$ 次操作：\n\n`1 l r x`：表示将区间 $[l,r]$ 中所有元素都修改为 $x$。\n\n`2 l r x`：表示查询区间 $[l,r]$ 中，对任意 $l\\le i<j\\le r$，且...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments