[THUPC 2024 决赛] 贸易

Luogu
IDLGP10550
Time1000ms
Memory512MB
DifficultyP5
2024THUPC
小 Z 生活的学校就像是一条链,直径很长,宽度很窄。 具体来说,这里有一个长度为 $n$ 的序列,每个位置有一个属性 $a_i\in \{0/1\}$ 和一个类型 $c_i$,在这里有一些贸易事件会发生。 小 Z 从左往右通过这个序列,若当前遇到一个 $0$ 属性的节点,则小 Z 可以购入至多一个 $c_i$ 类型的物品,若当前遇到一个 $1$ 属性的节点,则小 Z 可以卖出至多一个 $c_i$ 类型的物品,显然,在小 Z 没有这种类型的物品时是不能卖出的。 一次合法的交易定义为从某个节点买入,并在某个节点卖出,注意,你需要保证在最后小 Z 手里不存在任何东西。 给出 $q$ 次询问,每次小 Z 从 $l_i$ 顺序走到 $r_i$,问:最大合法交易次数是多少。 ## Input 第一行两个正整数 $n,q$。 接下来一行 $n$ 个数,第 $i$ 个表示 $a_i$。 接下来一行 $n$ 个数,第 $i$ 个表示 $c_i$。 接下来 $q$ 行,每行两个数表示 $l_i,r_i$。 ## Output 输出共 $q$ 行,每行一个数表示当前这个询问中的最大合法交易次数。 [samples] ## Note 对于所有数据,满足 $1\le n,q\le5\times 10^5,1\le c_i\le n,1\le l_i\le r_i\le n,a_i\in\{0,1\}$。 请注意输入输出效率。 **来源与致谢** 来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>
Samples
Input #1
10 5
1 1 0 0 0 0 0 1 1 1 
1 1 1 1 1 1 1 1 1 1 
4 6
2 4
2 6
7 10
4 7
Output #1
0
0
0
1
0
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2024 决赛] 贸易",
    "description": {
      "content": "小 Z 生活的学校就像是一条链,直径很长,宽度很窄。 具体来说,这里有一个长度为 $n$ 的序列,每个位置有一个属性 $a_i\\in \\{0/1\\}$ 和一个类型 $c_i$,在这里有一些贸易事件会发生。 小 Z 从左往右通过这个序列,若当前遇到一个 $0$ 属性的节点,则小 Z 可以购入至多一个 $c_i$ 类型的物品,若当前遇到一个 $1$ 属性的节点,则小 Z 可以卖出至多一个 $c_i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10550"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Z 生活的学校就像是一条链,直径很长,宽度很窄。\n\n具体来说,这里有一个长度为 $n$ 的序列,每个位置有一个属性 $a_i\\in \\{0/1\\}$ 和一个类型 $c_i$,在这里有一些贸易事件会发生。\n\n小 Z 从左往右通过这个序列,若当前遇到一个 $0$ 属性的节点,则小 Z 可以购入至多一个 $c_i$ 类型的物品,若当前遇到一个 $1$ 属性的节点,则小 Z 可以卖出至多一个 $c_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments