「蓬莱人形」

Luogu

IDLGP9212

Time1500ms

Memory512MB

DifficultyP6

O2优化分块根号分治传智杯

为了证明人类的可能性，你需要解决一个问题。给定序列 $a=[a_1,a_2,\cdots,a_n]$。现在有 $q$ 次询问： - 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\in [l,r]$ 满足 $(a_i+x)\bmod m<(a_i+y)\bmod m$。 ## Input 第一行有两个正整数 $n, q$，表示序列长度及询问次数。第二行有 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，描述序列 $a$。接下来 $q$ 行，每行有五个整数 $l_i,r_i,x_i,y_i,m_i$，描述一组询问。 ## Output 输出共 $q$ 行。第 $i$ 行输出第 $i$ 次询问的结果。 [samples] ## Background 不老不死的妹红，还能称之为「人类」吗？超脱了生死的人类，本来就是不可思议的啊。 ## Note ### 样例解释 - 对于第一组询问，符合条件的元素的下标为 $1, 2, 7, 8$； - 对于第二组询问，没有符合条件的元素； - 对于第三组询问，符合条件的元素的下标为 $2, 3, 4, 5, 6, 7$； - 对于第四组询问，符合条件的元素的下标为 $5, 6, 9$； - 对于第五组询问，符合条件的元素的下标为 $1, 2$。 ### 数据范围及约定对于全部数据，$1\le n\le 10^5$，$1\le q\le 5\times 10^5$，$1\le a_i,x_i,y_i,m_i\le 10^5$，$1\le l_i\le r_i\le n$。

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「蓬莱人形」",
    "description": {
      "content": "为了证明人类的可能性，你需要解决一个问题。 给定序列 $a=[a_1,a_2,\\cdots,a_n]$。现在有 $q$ 次询问： - 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\\in [l,r]$ 满足 $(a_i+x)\\bmod m<(a_i+y)\\bmod m$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9212"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "为了证明人类的可能性，你需要解决一个问题。\n\n给定序列 $a=[a_1,a_2,\\cdots,a_n]$。现在有 $q$ 次询问：\n\n- 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\\in [l,r]$ 满足 $(a_i+x)\\bmod m<(a_i+y)\\bmod m$。\n\n## Input\n\n第一行有两个正整数 $n, q$，表示序列长度及询问次...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments