{"problem":{"name":"[SDCPC 2023] Colorful Segments","description":{"content":"Consider $n$ segments on the number axis, where the left endpoint of the $i$-th segment is $l_i$ and the right endpoint is $r_i$. Each segment has a color where the color of the $i$-th segment is $c_i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9561"},"statements":[{"statement_type":"Markdown","content":"Consider $n$ segments on the number axis, where the left endpoint of the $i$-th segment is $l_i$ and the right endpoint is $r_i$. Each segment has a color where the color of the $i$-th segment is $c_i$ ($0 \\le c_i \\le 1$). There are two types of colors, where $c_i = 0$ indicates a red segment and $c_i = 1$ indicates a blue segment.\n\nYou need to choose some segments (you can also choose no segments at all). If any two chosen segments overlap, then they must have the same color.\n\nCalculate the number of ways to choose segments.\n\nWe say segment $i$ overlaps with segment $j$, if there exists a real number $x$ satisfying both $l_i \\le x \\le r_i$ and $l_j \\le x \\le r_j$.\n\nWe say two ways of choosing segments are different, if there exists an integer $1 \\le k \\le n$ such that the $k$-th segment is chosen in one of the ways and is not chosen in the other.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\le n \\le 10^5$) indicating the number of segments.\n\nFor the following $n$ lines, the $i$-th line contains three integers $l_i$, $r_i$ and $c_i$ ($1 \\le l_i \\le r_i \\le 10^9$, $0 \\le c_i \\le 1$) indicating the left and right endpoints and the color of the $i$-th segment.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $5 \\times 10^5$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the number of ways to choose segments. As the answer may be large, please output the answer modulo $998244353$.\n\n[samples]\n\n## Note\n\nFor the first sample test case, you cannot choose the $1$-st and the $2$-nd segment, or the $2$-nd and the $3$-rd segment at the same time, because they overlap with each other and have different colors.\n\nFor the second sample test case, as the $2$-nd segment does not overlap with the $1$-st and the $3$-rd segment, you can choose them arbitrary.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9561","tags":["动态规划 DP","线段树","2023","山东","O2优化","省赛/邀请赛"],"sample_group":[["2\n3\n1 5 0\n3 6 1\n4 7 0\n3\n1 5 0\n7 9 1\n3 6 0","5\n8"]],"created_at":"2026-03-03 11:09:25"}}