「VUSC」Card Tricks

Luogu

IDLGP8955

Time3000ms

Memory100MB

DifficultyP5

线段树二分整体二分

牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\le i\le N)$ 有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\forall l_i\le j \le r_i,a_j\gets a_j \lor v_i$。其中 $\lor$ 表示按位或操作，即 C++ 中的 `|`。对于 $i=1,2,\dots,N$，求出在哪一次操作后，$a_i$ **首次严格大于** $P$，其中 $P$ 为一给定常数。数据保证在初始情况下，$P\ge\max\{a_i\}$。 ## Input 第一行三个整数 $N,Q,P$。第二行 $N$ 个整数，第 $i$ 个数为 $a_i$ 的初始值。接下来 $Q$ 行，每行三个整数，$l_i,r_i,v_i$。 ## Output 输出 $N$ 个数 $id_1,id_2,\dots,id_N$，第 $i$ 个数表示在第 $id_i$ 次操作后，$a_i$ 首次严格大于 $P$。 **如果 $a_i$ 始终小于等于 $P$，请在这一位输出 $-1$。** [samples] ## Background **upd 2023.1.17 数据已加强。** **upd 2023.10.18 空间限制调整为 100 MiB。** Bessie 正在玩一场卡牌游戏！这个游戏有一些~~神秘的~~规则。Bessie 需要用一些编程技巧，加快计算。 ## Note #### 样例 #1 解释第一次操作后的数列为 $1,2,3,4,5$。第二次操作后的数列为 $11,2,3,4,5$。第三次操作后的数列为 $11,6,7,4,5$。 …… 最终的数列为 $11,14,15,4,23$。 --- #### 数据范围全部数据满足：$1\le N,Q \le 10^6$，$1\le l_i\le r_i \le N$，$1\le a_i,v_i,P\le 10^9$。测试点 $1\sim2$ 另满足 $1\le N,Q\le 10^3$。测试点 $3$ 另满足 $l_i=r_i$。测试点 $4$ 另满足 $l_i=1,r_i=N$。测试点 $5\sim10$ 无额外限制。 **本题数据规模较大，请注意常数优化。**

Samples

Input #1

Output #1

2 4 4 -1 7

Input #2

10 10 86
26 27 33 1 21 31 9 22 17 14
6 10 76
5 8 85
4 5 89
3 9 87
2 9 100
7 10 83
1 6 75
1 4 66
3 10 68
3 4 72

Output #2

7 5 4 3 3 1 2 1 1 6

API Response (JSON)

{
  "problem": {
    "name": "「VUSC」Card Tricks",
    "description": {
      "content": "牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\\le i\\le N)$ 有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\\forall l_i\\le j \\le r_i,a_j\\gets a_j \\lor v_i$。 其中 $\\lor$ 表示按位或操作，即 C++ 中的 `|`。 对于 $i=1,2,\\dots,N$，求出在哪一次操作后",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 102400
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8955"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "牌堆可以看成一个长度为 $N$ 的数列，下标为 $i$ 的位置值为 $a_i$。$(1\\le i\\le N)$\n\n有 $Q$ 次操作，每次操作给定 $l_i,r_i,v_i$，$\\forall l_i\\le j \\le r_i,a_j\\gets a_j \\lor v_i$。\n\n其中 $\\lor$ 表示按位或操作，即 C++ 中的 `|`。\n\n对于 $i=1,2,\\dots,N$，求出在哪一次操作后...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments