{"problem":{"name":"[JRKSJ R7] 月下缭乱","description":{"content":"你有一个长度为 $n$，初值全为 $0$ 的序列 $a$。 你有长为 $m$ 的操作序列，其中第 $i$ 次有三个参数 $l_i,r_i,x_i$，表示令 $\\forall j\\in[l_i,r_i] ,a_j\\gets\\max(a_j,x_i)$。 令 $\\text{sol}(l,r)$ 表示依次操作第 $l$ 至第 $r$ 个操作后的 $a$ 序列。 你需要回答有多少对 $(l,r)$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8936"},"statements":[{"statement_type":"Markdown","content":"你有一个长度为 $n$，初值全为 $0$ 的序列 $a$。\n\n你有长为 $m$ 的操作序列，其中第 $i$ 次有三个参数 $l_i,r_i,x_i$，表示令 $\\forall j\\in[l_i,r_i] ,a_j\\gets\\max(a_j,x_i)$。\n\n令 $\\text{sol}(l,r)$ 表示依次操作第 $l$ 至第 $r$ 个操作后的 $a$ 序列。\n\n你需要回答有多少对 $(l,r)$ 满足 $1\\le l\\le r\\le m$ 且 $\\text{sol}(l,r)=\\text{sol}(1,m)$。\n\n记 $f_i$ 为有多少 $i\\le k\\le m$ 满足 $\\text{sol}(i,k)=\\text{sol}(1,m)$，你还需要输出 $\\displaystyle\\bigoplus_{i=1}^m f_i\\times i$ 与 $\\displaystyle\\sum_{i=1}^m f_i\\times i$ 的值。\n\n所有答案都需要对 $2^{32}$ 取模后输出。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$，表示第 $i$ 个操作。\n\n## Output\n\n一行三个整数表示答案，对 $2^{32}$ 取模。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/xkd5zhgk.png?x-oss-process=image)\n\n轻快的音乐声坚定了你做一道简单题的决心。\n\n（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）\n\n## Note\n\nIdea：cyffff，Solution：Ntokisq / abruce，Code：cyffff，Data：cyffff\n\n**月下缭乱 - 月見静華 vs. LUNARiUM (Insane14.8)**\n\n**本题输入输出文件较大，请使用恰当的输入输出方式。**\n\n### 样例解释\n\n对于样例 $2$，最终 $a$ 序列的值为 $\\{2,2,3\\}$。不难发现，进行 $[1,4],[1,5],[2,5],[3,5],[4,5]$ 内的操作都可以使得 $a$ 与进行所有操作后 $a$ 序列的值相同。答案为 $5$。$f$ 序列的值为 $\\{2,1,1,1,0\\}$。\n\n### 数据规模\n本题采用捆绑测试。\n\n::cute-table\n| $\\text{Subtask}$ | $n,m\\le$ | 特殊限制 | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $100$ | 无 | $10$ |\n| $2$ | $10^4$ | ^ | $20$ |\n| $3$ | $3\\times10^5$ | 保证 $l_i=r_i$ | $10$ |\n| $4$ | ^ | 保证 $x_i=1$ | $10$ |\n| $5$ | ^ | 无 | $20$ |\n| $6$ | $10^6$ | ^ | $30$ |\n\n对于 $100\\%$ 的数据，$1\\le n,m\\le10^6$，$1\\le l_i\\le r_i\\le n$，$1\\le x_i\\le m$。\n### 特殊评分方式\n本题开启子任务依赖，具体如下：\n- 对于子任务 $i\\in\\{1,3,4\\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。\n- 对于子任务 $i\\in\\{2,5,6\\}$，您需要答对所有 $j\\in[1,i]$ 的子任务 $j$ 才能获得子任务 $i$ 的分数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8936","tags":["线段树","并查集","2023","颜色段均摊（珂朵莉树 ODT）","洛谷原创","O2优化"],"sample_group":[["5 5\n1 3 1\n2 4 1\n2 3 1\n1 3 1\n1 4 1\n","9 2 20"],["3 5\n1 3 2\n1 1 1\n2 2 2\n3 3 3\n1 3 2\n","5 7 11"]],"created_at":"2026-03-03 11:09:25"}}