#P17909. The Echoes of Chronos

The Echoes of Chronos

题目描述

给定长度为 nn 的整数序列 aa,所有值属于 [0,m)[0,m)。一次操作选择一个值 x∈[0,m)x\in[0,m),将整个序列中所有当前等于 xx 的元素同时变为以下两者之一:

(x+1) mod m,(x−1) mod m.(x+1)\bmod m,\qquad (x-1)\bmod m.

共有 qq 个询问 (l,r,v)(l,r,v):使位置 ll 到 rr 的全部元素都等于 vv,最少需要多少次操作?区间外的元素可以变为任何值。

所有询问相互独立,每次从原序列开始。操作影响整个序列,而不是只影响询问区间。

输入格式

第一行三个整数 n,q,mn,q,m。第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 qq 行,每行三个整数 l,r,vl,r,v。

输出格式

每个询问输出一行,包含最少操作次数。

数据范围

1≤n,q≤2000001\le n,q\le200000,1≤m≤1091\le m\le10^9,0≤ai,v<m0\le a_i,v<m,1≤l≤r≤n1\le l\le r\le n。本题只有一组数据。

样例输入

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

样例输出

5
4
2
4
4
0

来源

QOJ 14949,The 2025 ICPC Asia Shenyang Regional Contest / The 4th Universal Cup Stage 6。

时间限制:4 秒;空间限制:1024 MiB。中文题面按原数学定义与输入输出要求重新整理,保留英文标题。