{"id":163,"date":"2026-05-16T11:25:07","date_gmt":"2026-05-16T03:25:07","guid":{"rendered":"https:\/\/huxiaole.cloud\/?p=163"},"modified":"2026-05-20T18:25:34","modified_gmt":"2026-05-20T10:25:34","slug":"at_abc444_e-abc444e-sparse-range","status":"publish","type":"post","link":"https:\/\/huxiaole.cloud\/index.php\/2026\/05\/16\/at_abc444_e-abc444e-sparse-range\/","title":{"rendered":"AT_abc444_e ABC444E Sparse Range"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">AT_abc444_e [ABC444E] Sparse Range<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ed9\u4f60\u4e00\u4e2a\u957f\u5ea6\u4e3a N \u7684\u6574\u6570\u5e8f\u5217 $A_1,\\dots,A_N$ \u548c\u4e00\u4e2a\u6b63\u6574\u6570 D\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6c42\u6ee1\u8db3\u4ee5\u4e0b\u4e24\u4e2a\u6761\u4ef6\u7684\u6574\u6570\u5bf9 (L,R) \u7684\u4e2a\u6570\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$1 \\leq L \\leq R \\leq N$\u3002<\/li>\n\n\n\n<li>$A_L,A_{L+1},\\dots,A_R$ \u4e2d\u4efb\u610f\u4e24\u4e2a\u5143\u7d20\u7684\u5dee\u81f3\u5c11\u4e3a D\u3002\n<ul class=\"wp-block-list\">\n<li>\u5373\u5bf9\u4efb\u610f$ L \\leq i &lt; j \\leq R $\u7684\u6574\u6570\u5bf9 (i,j) \u90fd\u6ee1\u8db3$ |A_i-A_j|\\geq D$\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f93\u5165\u5185\u5bb9\u7531\u6807\u51c6\u8f93\u5165\u6cd5\u63d0\u4f9b\uff0c\u683c\u5f0f\u5982\u4e0b<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">N D<br>$A_1 \\dots A_N$<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f93\u51fa\u7b54\u6848\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #1<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>5 3\n3 1 4 1 5\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>8\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #2<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #2<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>9 1\n1 2 3 4 5 6 7 8 9\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #2<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>45\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #3<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>6 1000000000\n123456789 234567891 987654321 321987654 1000000000 1\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #3<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>6\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8bf4\u660e\/\u63d0\u793a<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\">\u6837\u4f8b\u89e3\u91ca #1<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">(1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) \u516b\u5bf9\u6ee1\u8db3\u6761\u4ef6\u3002<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\u6570\u636e\u8303\u56f4<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$2\\leq N \\leq 4\\times 10^5$<\/li>\n\n\n\n<li>$1 \\leq A_i \\leq 10^9$<\/li>\n\n\n\n<li>$1 \\leq D \\leq 10^9$<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/&nbsp;Sunshine,&nbsp;sunshine,&nbsp;ladybugs&nbsp;awake!  \n\/\/&nbsp;Clap&nbsp;your&nbsp;hooves&nbsp;and&nbsp;do&nbsp;a&nbsp;little&nbsp;shake!  \n#include&nbsp;&lt;bits\/stdc++.h&gt;  \n#define&nbsp;int&nbsp;long&nbsp;long  \n#define&nbsp;endl&nbsp;'\\n'  \nusing&nbsp;namespace&nbsp;std;  \n  \nusing&nbsp;PII=pair&lt;int,int&gt;&nbsp;;  \nconst&nbsp;int&nbsp;MAXN=200010;  \nconst&nbsp;int&nbsp;mod=998244353;  \nconst&nbsp;int&nbsp;INF=0x3f3f3f3f3f3f3f3f;  \n  \nint&nbsp;a&#91;MAXN];  \n  \nvoid&nbsp;solve()&nbsp;{  \n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;q;cin&gt;&gt;q;  \n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mx=-1;  \n&nbsp;&nbsp;&nbsp;&nbsp;while(q--){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;x;cin&gt;&gt;x;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&#91;1]++;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&#91;x+1]--;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mx=max(mx,x+1);  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i=1;i&lt;=mx;i++){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&#91;i]+=a&#91;i-1];  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;pos=1;  \n&nbsp;&nbsp;&nbsp;&nbsp;while(pos&lt;=mx||a&#91;pos]&gt;0){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(a&#91;pos]&gt;=10){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&#91;pos+1]+=a&#91;pos]\/10;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&#91;pos]%=10;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}pos++;  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pos--;  \n&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(pos&nbsp;&gt;&nbsp;1&nbsp;&amp;&amp;&nbsp;a&#91;pos]&nbsp;==&nbsp;0)&nbsp;{  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pos--;  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i=pos;i&gt;=1;i--){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;a&#91;i];  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n}  \n  \nsigned&nbsp;main()&nbsp;{  \n&nbsp;&nbsp;&nbsp;&nbsp;ios_base::sync_with_stdio(false);  \n&nbsp;&nbsp;&nbsp;&nbsp;cin.tie(NULL);  \n&nbsp;&nbsp;&nbsp;&nbsp;\/\/int&nbsp;t;cin&nbsp;&gt;&gt;&nbsp;t;while&nbsp;(t--)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;solve();  \n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;  \n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>AT_abc444_e [ABC444E] Sparse Range \u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u957f\u5ea6\u4e3a N \u7684\u6574\u6570\u5e8f\u5217 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":129,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,10],"tags":[],"class_list":["post-163","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-atc","category-10"],"_links":{"self":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/163","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/comments?post=163"}],"version-history":[{"count":4,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/163\/revisions"}],"predecessor-version":[{"id":199,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/163\/revisions\/199"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media\/129"}],"wp:attachment":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media?parent=163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/categories?post=163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/tags?post=163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}