{"problem":{"name":"[USACO24OPEN] Grass Segments G","description":{"content":"Bessie is planting some grass on the positive real line. She has $N$ ($2\\le N\\le 2\\cdot 10^5$) different cultivars of grass,  and will plant the $i$th cultivar on the interval $[\\ell_i, r_i]$ ($0 < \\e","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10281"},"statements":[{"statement_type":"Markdown","content":"Bessie is planting some grass on the positive real line. She has $N$ ($2\\le N\\le 2\\cdot 10^5$) different cultivars of grass,  and will plant the $i$th cultivar on the interval $[\\ell_i, r_i]$ ($0 < \\ell_i < r_i \\leq 10^9$).  \n\nIn addition, cultivar $i$ grows better when there is some cultivar $j$ ($j\\neq i$) such that  cultivar $j$ and cultivar $i$ overlap with length at least $k_i$ ($0 < k_i \\leq r_i - \\ell_i$). Bessie wants to evaluate all of her cultivars.  For each $i$, compute the number of $j\\neq i$ such that $j$ and $i$ overlap with length at least $k_i$.\n\n## Input\n\nThe first line contains $N$.  \n\nThe next $N$ lines each contain three space-separated integers $\\ell_i$, $r_i$, and $k_i$.\n\n## Output\n\nThe answers for all cultivars on separate lines.\n\n[samples]\n\n## Note\n\n##### For Sample 1:\nThe overlaps of the cultivars is $[4,6]$, which has length $2$, which is at least $2$ but not at least $3$.  \n\n#### SCORING:\n- Input 4-5: $N \\leq 5000$.\n- Inputs 6-11: $k$ is the same for all intervals.\n- Inputs 12-20: No additional constraints.  \n\nIn addition, for Inputs 5, 7, ..., 19, $r_i \\leq 2N$ for all $i$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10281","tags":["USACO","2024","cdq 分治"],"sample_group":[["2\n3 6 3\n4 7 2","0\n1"],["4\n3 6 1\n2 5 1\n4 10 1\n1 4 1","3\n3\n2\n2"],["5\n8 10 2\n4 9 2\n3 7 4\n5 7 1\n2 7 1","0\n3\n1\n3\n3"]],"created_at":"2026-03-03 11:09:25"}}