[Ynoi2001] 冷たい部屋、一人

Luogu
IDLGP9337
Time9000ms
Memory512MB
DifficultyP7
2001O2优化Ynoi
给定 $n,m$,以及序列 $a_1,a_2,\dots,a_n$ 和 $1,2,\dots,n$ 的排列 $y_1,y_2,\dots,y_n$,你需要回答 $m$ 个询问。 对每个询问,给定 $l,r$,查询: $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [a_i=a_j]\cdot\prod_{k=i}^j [l\le y_k\le r]$; 其中 $[\mathrm{cond}]$ 在条件 $\mathrm{cond}$ 为真时值为 $1$,否则值为 $0$。 ## Input 第一行两个数 $n,m$; 第二行 $n$ 个整数 $a_1,\dots,a_n$; 第三行 $n$ 个整数 $y_1,\dots,y_n$; 接下来 $m$ 行,每行两个数 $l,r$ 表示一个询问。 ## Output $m$ 行,每行一个整数,表示相应的答案。 [samples] ## Background  冷たい部屋の隅に 射し込んできた夕陽だったら  冰冷房间的角落 洒满夕阳的光辉  近づいてみても感情は無くて 裏切りも無い  再怎么接近也没有感情 没有变化  今日も明日も一人で きっとそれが普通のことで  就算今后都是一个人 也只是很平常的事  交わす言葉も無く 一日を終える時  交谈也无法改变 这一天的终结  例えば 優しさはどれくらいの  例如 温柔究竟是怎样的  ぬくもりかも知らないで  连获取温暖都不知道  そんなにそんなに簡単じゃない  那么那样不是很简单吗  心の距離  心的距离  冷たい部屋の隅に 小さくなったまま  冰冷房间的角落 就这样变小吧 ![](https://cdn.luogu.com.cn/upload/image_hosting/6uukzjeq.png) ## Note Idea:Ynoi&nzhtl1477,Solution:Ynoi&ccz181078,Code:ccz181078,Data:ccz181078&Terry2022 对于 $100\%$ 的数据,满足 $1\le n,m\le 5\times 10^5$;$1\le a_i\le n$;$1\le y_i\le n$,$y_i$ 互不相同;对每个询问,$1\le l\le r\le n$。 对于 $20\%$ 的数据,满足 $n,m\le 100$。 对于 $40\%$ 的数据,$n,m\le 5000$ 对于 $60\%$ 的数据,$n,m\le 2\times 10^5$
Samples
Input #1
3 4
1 1 3
2 3 1
1 2
1 3
2 3
1 1
Output #1
0
1
1
0
API Response (JSON)
{
  "problem": {
    "name": "[Ynoi2001] 冷たい部屋、一人",
    "description": {
      "content": "给定 $n,m$,以及序列 $a_1,a_2,\\dots,a_n$ 和 $1,2,\\dots,n$ 的排列 $y_1,y_2,\\dots,y_n$,你需要回答 $m$ 个询问。 对每个询问,给定 $l,r$,查询: $\\sum\\limits_{i=1}^n\\sum\\limits_{j=i+1}^n [a_i=a_j]\\cdot\\prod_{k=i}^j [l\\le y_k\\le r]$; 其",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 9000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9337"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n,m$,以及序列 $a_1,a_2,\\dots,a_n$ 和 $1,2,\\dots,n$ 的排列 $y_1,y_2,\\dots,y_n$,你需要回答 $m$ 个询问。\n\n对每个询问,给定 $l,r$,查询:\n\n$\\sum\\limits_{i=1}^n\\sum\\limits_{j=i+1}^n [a_i=a_j]\\cdot\\prod_{k=i}^j [l\\le y_k\\le r]$;\n\n其...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments