{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e马里奥是世界著名的水管工。他“魁梧”的身材和惊人的跳跃能力让我们铭记在心。现在可怜的公主再次陷入困境,马里奥需要拯救他的爱人。我们把通往Boss城堡的道路看作一条线段(长度为n),在每个整数点i上都有高度为hi的砖块。现在的问题是,如果马里奥能跳的最大高度是H,那么在[L, R]范围内马里奥能击中多少个砖块。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行是一个整数T,表示测试数据的数量。\u003cbr\u003e对于每组测试数据:\u003cbr\u003e第一行包含两个整数n,m(1 \u003c\u003d n \u003c\u003d 10^5,1 \u003c\u003d m \u003c\u003d 10^5),n表示道路的长度,m表示查询的次数。\u003cbr\u003e接下来一行包含n个整数,表示每个砖块的高度,范围为[0, 1000000000]。\u003cbr\u003e接下来m行,每行包含三个整数L,R,H(0 \u003c\u003d L \u003c\u003d R \u003c n,0 \u003c\u003d H \u003c\u003d 1000000000)。"}},{"title":"输出","value":{"format":"HTML","content":"对每组数据,输出\"Case X: \"(X是从1开始的案例编号),然后是m行,每行包含一个整数。第i个整数表示第i个查询中马里奥能击中的砖块数量。\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n10 10\r\n0 5 2 7 5 4 3 8 7 7 \r\n2 8 6\r\n3 5 0\r\n1 3 1\r\n1 9 4\r\n0 1 0\r\n3 5 5\r\n5 5 1\r\n4 6 3\r\n1 5 7\r\n5 7 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\r\n4\r\n0\r\n0\r\n3\r\n1\r\n2\r\n0\r\n1\r\n5\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}