\u6b63\u5982\u6807\u9898\u4e4b\u4e2d\u6240\u5199\u7684\uff0c\u6211\u53ea\u505a\u51fa\u6765 4 \u9053\u9898\uff08\u54ed\uff09\uff0c\u5f53\u65f6\u8fd8\u5dee\u70b9\u5361 D \u4e86\uff0c\u8c03\u5f97\u633a\u5d29\u6e83\u7684\uff0c\u4e5f\u4e0d\u77e5\u9053\u662f\u4e0d\u662f\u8def\u5b50\u4e0d\u591f\u6b63\u3002\u81f3\u4e8e EF \u9898\uff0c\u6211\u5012\u662f\u4e5f\u770b\u4e86\uff0c\u4f46\u662f\u90fd\u6ca1\u6709\u4e00\u4e2a\u5177\u4f53\u7684\u601d\u8def\uff0c\u4ee5\u540e\u770b\u770b dalao \u7684\u9898\u89e3\uff0c\u518d\u8865\u5145\u4e00\u4e0b\u5427\u3002<\/p>\n
\u8f93\u5165\u4e00\u4e2a\u5b57\u7b26$c$\uff0c\u5bf9\u4e8e$c$\u5206\u522b\u4e3a\u5b57\u6bcd B\u3001Y\u3001R \u65f6\uff0c\u5206\u522b\u8f93\u51fa\u5b57\u6bcd Y\u3001R\u3001B\u3002<\/p>\n
\u601d\u8def\u5982\u9898\u3002<\/p>\n
\u6709$N$\u4e2a\u4eba\uff0c\u7b2c$i$\u53f7\u4eba\u4f4d\u4e8e\u5750\u6807$X_i$\u5904\uff0c\u5982\u679c\u4e00\u4e2a\u4eba\u4e0e\u5176\u4ed6\u6240\u6709\u4eba\u7684\u8ddd\u79bb\u6700\u5c0f\u503c\u4e0d\u5c0f\u4e8e$D$\uff0c\u5c31\u79f0\u5176\u4e3a\u201c\u7279\u6b8a\u4eba\u201d\u3002\u8f93\u51fa\u201c\u7279\u6b8a\u4eba\u201d\u7684\u4e2a\u6570\u4ee5\u53ca\u6bcf\u4e2a\u201c\u7279\u6b8a\u4eba\u201d\u7684\u7f16\u53f7\uff08\u7f16\u53f7\u5347\u5e8f\u8f93\u51fa\uff09\u3002$N\\leq 100$\u3002<\/p>\n
\u5bf9\u4e8e\u6bcf\u4e2a\u4eba\u90fd\u627e\u4e00\u4e0b\u5c31\u597d\u4e86\u3002\u65f6\u95f4\u590d\u6742\u5ea6$O(N^2)$\u3002<\/p>\n
\u6709\u4e24\u4e2a\u5b57\u7b26\u4e32$s,\\, t$\uff0c\u8fdb\u884c$Q$\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u7ed9\u51fa$L,\\, R$\uff0c\u5224\u65ad$s$\u4ece\u7b2c$L$\u4f4d\u5230\u7b2c$R$\u4f4d\u7684\u5b50\u4e32\u4e2d\u662f\u5426\u5305\u542b$t$\u4f5c\u4e3a\u5b50\u4e32\u3002$\\lvert s\\rvert \\leq 4\\times 10^5,\\, \\lvert t\\rvert \\leq 10,\\, Q\\leq 2\\times 10^5$\u3002<\/p>\n
\u663e\u7136$O(Q\\lvert s\\vert \\lvert t\\rvert)$\u662f\u4e0d\u884c\u7684\uff0c\u8003\u8651\u524d\u7f00\u548c\u3002\u8bbe$sum_i$\u8868\u793a$s$\u4ece\u5934\u5230\u7b2c$i$\u4f4d\u51fa\u73b0\u7684$t$\u5b50\u4e32\u4e2a\u6570\uff0c\u7531\u4e8e$\\lvert t\\rvert$\u5f88\u5c0f\uff0c\u6240\u4ee5\u8fd9\u91cc\u4e00\u4e2a$O(\\lvert s\\rvert \\lvert t\\rvert)$\u53ef\u4ee5\u63a5\u53d7\u3002<\/p>\n
\u90a3\u4e48\u5bf9\u4e8e\u6bcf\u6b21\u8be2\u95ee\uff0c\u53ea\u9700\u8981\u770b\u770b$[L,\\, R]$\u5185\u51fa\u73b0\u7684$t$\u5b50\u4e32\u4e2a\u6570\u662f\u5426\u5927\u4e8e 0 \u5373\u53ef\u3002\u73b0\u5728\uff0c\u5c31\u8981\u8003\u8651\u5982\u4f55\u7528$sum_i$\u8868\u793a\u51fa$[L,\\, R]$\u5185\u51fa\u73b0\u7684$t$\u5b50\u4e32\u4e2a\u6570\uff0c\u76f4\u63a5$sum_R-sum_{L-1}$\u5417\uff1f\u4f3c\u4e4e\u4e0d\u592a\u5bf9\u554a\u3002\u56e0\u4e3a\u8fd9\u91cc\u5173\u4e8e$sum$\u7684\u542b\u4e49\uff0c\u66f4\u51c6\u786e\u5730\u8bf4\u5e94\u8be5\u662f\uff1a$s$\u4e2d\u51fa\u73b0\u7684\u7ed3\u5c3e\u4f4d<\/strong>\u4e0d\u5927\u4e8e$i$\u7684$t$\u5b50\u4e32\u4e2a\u6570\u3002\u56de\u60f3\u4e00\u4e0b\u521a\u624d\u7684\u5f0f\u5b50\uff0c\u53ef\u80fd\u6709\u521a\u597d\u7ed3\u5c3e\u4f4d<\/strong>\u4e3a$L$\u7684$t$\u5b50\u4e32\u4e5f\u88ab\u7edf\u8ba1\u4e86\uff0c\u4f46\u5b9e\u9645\u4e0a\u90a3\u4e2a$t$\u5b50\u4e32\u5e76\u4e0d\u662f\u5b8c\u5168\u4f4d\u4e8e$[L,\\, R]$\u5185\u3002<\/p>\n \u8fd9\u6837\u4e00\u6765\uff0c\u5c31\u8981\u591a\u8003\u8651\u4e00\u4e2a\u70b9\uff1a$t$\u5b50\u4e32\u7684\u5f00\u5934\u4f4d<\/strong>\u5fc5\u987b\u4e0d\u5c0f\u4e8e$L$\u3002\u5bf9\u4e8e\u5f00\u5934\u4f4d<\/strong>\u6700\u9760\u524d\uff08\u5373\u4e3a$L$\uff09\u7684$t$\u5b50\u4e32\uff0c\u5176\u7ed3\u5c3e\u4f4d\u5e94\u8be5\u4e3a$L+\\lvert t\\rvert -1$\u3002\u90a3\u4e48\uff0c$[L,\\, R]$\u5185\u51fa\u73b0\u7684$t$\u5b50\u4e32\u4e2a\u6570\u7528$sum_i$\u8868\u793a\u51fa\u6765\u5c31\u662f\uff1a$$sum_R-sum_{(L+\\lvert t\\rvert -1)-1}.$$<\/p>\n \u65f6\u95f4\u590d\u6742\u5ea6$O(\\lvert s\\rvert \\lvert t\\rvert +Q)$\u3002<\/p>\n \u6709$N$\u4e2a\u683c\u5b50\u6392\u6210\u4e00\u884c\uff0c\u4e00\u5f00\u59cb\u6240\u6709\u683c\u5b50\u7684\u989c\u8272\u90fd\u4e3a a\uff08\u989c\u8272\u7528\u5c0f\u5199\u5b57\u6bcd\u8868\u793a\uff09\uff0c\u63a5\u7740\u8fdb\u884c$Q$\u6b21\u64cd\u4f5c\uff0c\u6700\u540e\u8f93\u51fa\u6bcf\u4e2a\u683c\u5b50\u7684\u989c\u8272\u3002\u64cd\u4f5c\u7c7b\u578b\u6709\u4e24\u79cd\uff1a\u64cd\u4f5c 1 \u8f93\u5165\u4e00\u4e2a\u6574\u6570$X$\uff0c\u82e5\u7b2c$X$\u53f7\u683c\u5b50\u4e0a\u6709\u74f7\u7816\u8986\u76d6\u5c31\u62ff\u6389\u90a3\u5757\u74f7\u7816\uff0c\u5426\u5219\u5c31\u5728\u4e0a\u9762\u8986\u76d6\u4e00\u5757\u74f7\u7816\uff1b\u64cd\u4f5c 2 \u8f93\u5165\u4e00\u4e2a\u5b57\u7b26$C$\uff0c\u5c06\u6240\u6709\u6ca1\u88ab\u74f7\u7816\u8986\u76d6\u7684\u683c\u5b50\u67d3\u6210\u989c\u8272$C$\u3002$N,\\, Q\\leq 3\\times 10^5$\u3002<\/p>\n \u8003\u8651\u5012\u5e8f<\/strong>\u64cd\u4f5c\u3002\u5148\u987a\u5e8f<\/strong>\u8dd1\u4e00\u904d\uff0c\u8dd1\u51fa\u6700\u7ec8\u6240\u6709\u683c\u5b50\u7684\u74f7\u7816\u8986\u76d6\u72b6\u6001\uff0c\u770b\u770b\u6700\u7ec8\u6ca1\u88ab\u74f7\u7816\u8986\u76d6\u7684\u683c\u5b50\u80fd\u5426\u88ab\u67d3\u4e0a\u8272\uff0c\u5982\u679c\u80fd\u67d3\u5c31\u67d3\uff0c\u518d\u5012\u7740\u8dd1\u5c31\u4f1a\u53d1\u73b0\u6bcf\u6b21\u64cd\u4f5c 1 \u6700\u591a\u6709\u4e00\u4e2a\u683c\u5b50\u7684\u74f7\u7816\u8986\u76d6\u72b6\u6001\u53d1\u751f\u6539\u53d8\uff0c\u5982\u679c\u662f\u74f7\u7816\u88ab\u63ed\uff0c\u5c31\u66f4\u65b0\u4e00\u4e0b\u8fd9\u4e2a\u683c\u5b50\u7684\u989c\u8272\uff08\u524d\u63d0\u662f\u8fd9\u4e2a\u683c\u5b50\u989c\u8272\u8fd8\u662f a\uff09\uff0c\u5173\u4e8e\u66f4\u65b0\u4e3a\u4f55\u79cd\u989c\u8272\uff0c\u5411\u524d\u627e\u64cd\u4f5c 2 \u5373\u53ef\uff08\u5f53\u7136\u592a\u9760\u524d\u7684\u64cd\u4f5c 2 \u4e5f\u4e0d\u884c\uff0c\u6709\u53ef\u80fd\u90a3\u65f6\u8be5\u683c\u5b50\u7684\u74f7\u7816\u8986\u76d6\u72b6\u6001\u53c8\u6539\u53d8\u4e86\u4e00\u6b21\uff0c\u76f8\u5f53\u4e8e\u53c8\u88ab\u8986\u76d6\u4e86\uff0c\u90a3\u5c31\u4e0d\u80fd\u67d3\u4e86\uff09\u3002\u65f6\u95f4\u590d\u6742\u5ea6$O(Q\\log Q)$\uff0c\u8be6\u89c1\u4ee3\u7801\u6ce8\u91ca\uff0c\u53ef\u80fd\u8bfb\u8d77\u6765\u66f4\u597d\u61c2\u4e9b\u3002<\/p>\n \uff08\u8865\u3002\u5b8c\u5168\u60f3\u590d\u6742\u4e86\u3002\uff09<\/p>\n \u7ed9\u51fa\u4e00\u4e2a\u6709$N+1$\u4e2a\u70b9\u7684\u65e0\u5411\u56fe\uff0c\u5bf9\u4e8e\u6bcf\u4e2a$1\\leq i\\leq N$\uff0c\u70b9$i$\u4e0e\u70b9$(i\\mod N)+1$\u4e4b\u95f4\u6709\u4e00\u6761\u957f$A_i$\u7684\u8fb9\uff0c\u70b9$i$\u4e0e\u70b9$N+1$\u4e4b\u95f4\u6709\u4e00\u6761\u957f$B_i$\u7684\u8fb9\u3002\u8fdb\u884c$Q$\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u7ed9\u51fa\u4e24\u4e2a\u70b9$S,\\, T$\uff0c\u8be2\u95ee\u8fd9\u4e24\u70b9\u95f4\u7684\u6700\u77ed\u8ddd\u79bb\u3002$N,\\, Q\\leq 2\\times 10^5,\\, 1\\leq S<T\\leq N+1$\u3002<\/p>\n \u5f88\u663e\u7136\u53ef\u4ee5\u5c06\u8fd9\u4e2a\u56fe\u60f3\u6210\u662f\uff1a\u4e00\u4e2a\u73af<\/strong> + \u4e00\u4e2a\u4e2d\u5fc3\u70b9<\/strong>\u3002\u4ece$S$\u5230$T$\uff0c\u53ef\u4ee5\u9009\u62e9\u53ea\u5728\u73af\u4e0a\u8d70\uff0c\u4e5f\u53ef\u4ee5\u9009\u62e9\u9014\u4e2d\u7ecf\u8fc7\u4e2d\u5fc3\u70b9\u8d70\u3002\u73af\u4e0a\u4e24\u70b9\u95f4\u7684\u8ddd\u79bb\u597d\u6c42\uff0c\u524d\u7f00\u548c\u5373\u53ef\uff1b\u9014\u7ecf\u4e2d\u5fc3\u70b9\u8d70\u5206\u4e3a\u4e24\u90e8\u5206\uff0c\u5148\u4ece$S$\u5230$N+1$\uff0c\u518d\u4ece$N+1$\u5230$T$\uff0c\u8dd1\u4e00\u4e2a\u4ee5$N+1$\u4e3a\u8d77\u70b9\u7684\u5355\u6e90\u6700\u77ed\u8def\u5373\u53ef\u3002\u65f6\u95f4\u590d\u6742\u5ea6$O(N\\log N+Q)$\u3002<\/p>\n \uff08\u8865\u3002\u5b8c\u5168\u6ca1\u60f3\u5230\u600e\u4e48\u505a\uff0c\u4f46\u5b9e\u9645\u4e0a\u505a\u6cd5\u975e\u5e38\u5de7\u5999\u4e14\u7ecf\u5178\u3002\uff09<\/p>\n \u6709\u4e00\u4e2a$N$\u884c$M$\u5217\u7684\u7f51\u683c\uff0c\u7b2c$i$\u884c\u7684\u7b2c$L_i$\u5217\u5230\u7b2c$R_i$\u5217\u4e3a\u9ed1\u8272\uff0c\u5176\u4f59\u4e3a\u767d\u8272\u3002\u8fdb\u884c$Q$\u6b21\u8be2\u95ee\uff0c\u6bcf\u6b21\u8be2\u95ee\u7ed9\u51fa$A,\\, B,\\, C,\\, D$\uff0c\u6c42\u7b2c$A$\u884c\u5230\u7b2c$B$\u884c\u3001\u7b2c$C$\u5217\u5230\u7b2c$D$\u5217\u5f62\u6210\u7684\u77e9\u5f62\u4e2d\u7684\u9ed1\u8272\u683c\u5b50\u4e2a\u6570\u3002$N,\\, M,\\, Q\\leq 2\\times 10^5$\u3002<\/p>\n \u5bb9\u6613\u60f3\u5230\u4e8c\u7ef4\u524d\u7f00\u548c\uff0c\u53ef\u662f$N,\\, M$\u592a\u5927\uff0c\u6839\u672c\u65e0\u6cd5\u5f00\u51fa\u4e00\u4e2a\u5927\u5c0f\u4e3a$NM$\u7684\u6570\u7ec4\u3002\u4e0d\u8fc7\u6211\u4eec\u8fd8\u662f\u53ef\u4ee5\u6839\u636e\u4e8c\u4f4d\u524d\u7f00\u548c\u5199\u51fa\u6765\u4e00\u4e2a\u5f0f\u5b50\uff0c\u8bbe$f(x,\\, y)$\u8868\u793a\u4ee5$(1,\\, 1)$\u4e3a\u5de6\u4e0a\u89d2\u3001$(x,\\, y)$\u4e3a\u53f3\u4e0b\u89d2\u7684\u77e9\u5f62\u4e2d\u7684\u9ed1\u8272\u683c\u5b50\u4e2a\u6570\uff0c\u5219\u6709\uff1a$$ans=f(B,\\, D)-f(A-1,\\, D)-f(B,\\, C-1)+f(A-1,\\, C-1).$$<\/p>\n \u65e2\u7136\u65e0\u6cd5\u4fdd\u5b58$f(x,\\, y)$\uff0c\u90a3\u4e48\u5c31\u76f4\u63a5\u8003\u8651\u600e\u4e48\u628a\u5b83\u6c42\u51fa\u6765\u3002\u6c42$f(x,\\, y)$\u9700\u8981\u77e5\u9053\u7b2c$1$\u884c\u5230\u7b2c$x$\u884c\u4e4b\u95f4\u6bcf\u4e00\u884c\u7684\u8d21\u732e\u3002\u5bf9\u4e8e\u7b2c$i$\u884c\uff0c\u5176\u8d21\u732e\u60c5\u51b5\u6709\u4e09\u79cd\uff0c\u7b80\u5355\u6765\u8bf4\u5c31\u662f\u5b8c\u5168\u4e0d\u8d21\u732e<\/strong>\u3001\u4e0d\u5b8c\u5168\u8d21\u732e<\/strong>\u548c\u5b8c\u5168\u8d21\u732e<\/strong>\u8fd9\u4e09\u79cd\u3002\u5177\u4f53\u6765\u8bf4\u662f\u8fd9\u6837\u7684\uff1a\u82e5$y<L_i$\uff0c\u5219\u8d21\u732e$0$\uff1b\u82e5$L_i\\leq y<R_i$\uff0c\u5219\u8d21\u732e$y-L_i+1$\uff1b\u82e5$y\\geq R_i$\uff0c\u5219\u8d21\u732e$R_i-L_i+1$\u3002<\/p>\n \u5982\u6b64\u4e00\u6765\uff0c\u5219\u6709\uff1a$$f(x,\\, y)=\\sum_{i\\leq x,\\, L_i\\leq y<R_i} (y-L_i+1)+\\sum_{i\\leq x,\\, y\\geq R_i} (R_i-L_i+1).$$<\/p>\n \u8fdb\u800c\u53ef\u4ee5\u5199\u6210\uff1a$$f(x,\\, y)=(y+1)\\cdot \\sum_{i\\leq x,\\, L_i\\leq y<R_i} 1-\\sum_{i\\leq x,\\, L_i\\leq y<R_i} L_i+\\sum_{i\\leq x,\\, y\\geq R_i} (R_i-L_i+1).$$<\/p>\n \u6574\u4e2a\u5f0f\u5b50\u660e\u663e\u5206\u6210\u4e86\u4e09\u90e8\u5206\uff0c\u8003\u8651\u7528\u6811\u72b6\u6570\u7ec4\u7ef4\u62a4\u6bcf\u4e00\u9879\uff0c\u5206\u522b\u662f\u4e0d\u5b8c\u5168\u8d21\u732e\u884c\u6570$cnt$<\/strong>\u3001\u4e0d\u5b8c\u5168\u8d21\u732e\u884c\u7684$L_i$\u4e4b\u548c$sum$<\/strong>\u4ee5\u53ca\u5b8c\u5168\u8d21\u732e\u884c\u7684$R_i-L_i+1$\u4e4b\u548c$csum$<\/strong>\u3002\u6bcf\u4e2a\u72b6\u6001\u6309\u7167$y$\u4ece\u5c0f\u5230\u5927\u8fdb\u884c\u66f4\u65b0\uff1a\u5bf9\u4e8e\u6240\u6709\u6ee1\u8db3$L_i=y$\u7684\u884c$i$\uff0c$cnt$\u52a0\u4e0a$1$\uff0c$sum$\u52a0\u4e0a$L_i$\uff1b\u5bf9\u4e8e\u6240\u6709\u6ee1\u8db3$R_i=y$\u7684\u884c$i$\uff0c$cnt$\u51cf\u53bb$1$\uff0c$sum$\u51cf\u53bb$L_i$\uff0c$csum$\u52a0\u4e0a$R_i-L_i+1$\u3002<\/p>\n \u6700\u540e\u8003\u8651\u67e5\u8be2\u8be5\u600e\u4e48\u5904\u7406\uff0c\u5148\u5c06\u6bcf\u4e2a\u67e5\u8be2\u64cd\u4f5c\u6309\u7167\u4e0a\u6587\u63d0\u5230\u7684\u5173\u4e8e$ans$\u7684\u5f0f\u5b50\u7684\u53f3\u4fa7\u62c6\u6210\u56db\u9879\uff0c\u5206\u522b\u662f$f(B,\\, D)$\u3001$-f(A-1,\\, D)$\u3001$-f(B,\\, C-1)$\u548c$f(A-1,\\, C-1)$\uff0c\u7136\u540e\u518d\u6309\u5217\u5b58\u4e0b\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u5728\u66f4\u65b0\u6811\u72b6\u6570\u7ec4\u65f6\u987a\u4fbf\u6c42\u51fa\u4e00\u4e2a\u4e2a\u67e5\u8be2\u9879\u3002<\/p>\n \u6700\u540e\u53d1\u73b0\u662f\u7ecf\u5178\u7684\u300c\u79bb\u7ebf<\/strong> + \u6811\u72b6\u6570\u7ec4<\/strong>\u300d\u601d\u60f3\u3002\u65f6\u95f4\u590d\u6742\u5ea6$O((N+Q)\\log N)$\u3002<\/p>\n \u5410\u69fd\u81ea\u5df1 \u6b63\u5982\u6807\u9898\u4e4b\u4e2d\u6240\u5199\u7684\uff0c\u6211\u53ea\u505a\u51fa\u6765 4 \u9053\u9898\uff08\u54ed\uff09\uff0c\u5f53\u65f6\u8fd8\u5dee\u70b9\u5361 D \u4e86\uff0c\u8c03\u5f97\u633a\u5d29\u6e83\u7684\uff0c\u4e5f\u4e0d\u77e5\u9053\u662f\u4e0d\u662f\u8def […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-134","post","type-post","status-publish","format-standard","hentry","category-5"],"_links":{"self":[{"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/posts\/134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/comments?post=134"}],"version-history":[{"count":0,"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/posts\/134\/revisions"}],"wp:attachment":[{"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/media?parent=134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/categories?post=134"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/done.baka233.top\/index.php\/wp-json\/wp\/v2\/tags?post=134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}int main(){\n\tcin >> q >> s >> t;\n\tint ls = s.size(), lt = t.size();\n\tfor(int i = 0; i < ls; i++){\n\t\tif(i + 1 < lt) continue; \/\/ \u957f\u5ea6\u8fd8\u4e0d\u5230|t|\n\t\tbool f = 0;\n\t\tfor(int j = 0; j < lt; j++)\n\t\t\tif(t[j] != s[i - lt + 1 + j]){ f = 1; break; }\n\t\tsum[i] = sum[i - 1] + (!f);\n\t}\n\twhile(q--){\n\t\tint l, r;\n\t\tcin >> l >> r; l--, r--; \/\/ \u524d\u9762\u5b57\u7b26\u4e32\u9996\u4f4d\u4ece0\u5f00\u59cb\uff0c\u8fd9\u91cc\u8be2\u95ee\u9ed8\u8ba4\u9996\u4f4d\u4e3a1\uff0c\u6240\u4ee5\u8fdb\u884c-1\u504f\u79fb\n\t\tif(r - l + 1 < lt) cout << "No\\n"; \/\/ \u533a\u95f4\u603b\u957f\u8fd8\u4e0d\u5230|t|\n\t\telse{\n\t\t\tint c = sum[r] - sum[l + lt - 2];\n\t\t\tif(c > 0) cout << "Yes\\n";\n\t\t\telse cout << "No\\n";\n\t\t}\n\t}\n\treturn 0;\n}<\/code><\/pre>\nD – Masking Tape<\/h3>\n
int main(){\n\tcin >> n >> q;\n\tfor(int i = 1; i <= q; i++){\n\t\tcin >> op[i];\n\t\tif(op[i] == 1){\n\t\t\tcin >> x[i];\n\t\t\tt[x[i]].push_back(i); \/\/ t[x]\u91cc\u9762\u5b58\u653e\u7684\u662f\u683c\u5b50x\u7684\u74f7\u7816\u8986\u76d6\u72b6\u6001\u53d1\u751f\u6539\u53d8\u7684\u64cd\u4f5c\u5e8f\u53f7\n\t\t\ta[x[i]] ^= 1; \/\/ a[i]\u4e3a0\u8868\u793a\u6ca1\u88ab\u8986\u76d6\uff0c\u4e3a1\u8868\u793a\u88ab\u8986\u76d6\uff1b\u8fd9\u91cc\u5c31\u662f\u5728\u8fdb\u884c01\u72b6\u6001\u8f6c\u6362\n\t\t}\n\t\telse{\n\t\t\tcin >> c[i];\n\t\t\tp[++tot] = i; \/\/ p\u4e2d\u5b58\u653e\u4e86\u6240\u6709\u64cd\u4f5c2\u7684\u64cd\u4f5c\u5e8f\u53f7\n\t\t}\n\t}\n\tbool f = 0;\n\tfor(int i = q; i >= 1; i--){ \/\/ \u5012\u7740\u8dd1\n\t\tif(op[i] == 2 && !f){ \/\/ \u6700\u65e9\u78b0\u5230\u7684\u64cd\u4f5c2\uff0c\u628a\u76ee\u524d\u8fd8\u6ca1\u88ab\u8986\u76d6\u7684\u683c\u5b50\u67d3\u4e00\u67d3\n\t\t\tf = 1;\n\t\t\tfor(int j = 1; j <= n; j++)\n\t\t\t\tif(!a[j]) ans[j] = c[i];\n\t\t\tcontinue;\n\t\t}\n\t\tif(op[i] == 1){\n\t\t\ta[x[i]] ^= 1;\n\t\t\tif(ans[x[i]]) continue; \/\/ \u5df2\u7ecf\u6709\u4e0d\u4e3aa\u7684\u989c\u8272\u5c31\u8df3\u8fc7\n\t\t\tif(!a[x[i]]){ \/\/ \u53d8\u5b8c\u540e\u53ef\u4ee5\u67d3\u8272\uff0c\u5c31\u5411\u524d\u627e\u64cd\u4f5c2\n\t\t\t\tint ps = upper_bound(p + 1, p + tot + 1, i) - p - 1; \/\/ \u4e8c\u5206\u67e5\u627ei\u4e4b\u524d\u6700\u9760\u540e\u7684\u64cd\u4f5c2\n\t\t\t\tif(!c[p[ps]]) continue; \/\/ \u524d\u9762\u5df2\u7ecf\u6ca1\u6709\u64cd\u4f5c2\u4e86\uff1b\u6ce8\u610fps\u53ea\u80fd\u4f5c\u4e3ap\u7684\u4e0b\u6807\uff0c\u53ea\u6709p[ps]\u624d\u80fd\u4f5c\u4e3ac\u7684\u4e0b\u6807\n\t\t\t\tint l = 0, r = t[x[i]].size() - 1; \/\/ \u4e8c\u5206\u67e5\u627e\u8be5\u64cd\u4f5c\u5e8f\u53f7i\u5728t[x[i]]\u4e2d\u7684\u4f4d\u7f6e\n\t\t\t\twhile(l < r){\n\t\t\t\t\tint mid = (l + r) >> 1;\n\t\t\t\t\tif(t[x[i]][mid] < i) l = mid + 1;\n\t\t\t\t\telse r = mid;\n\t\t\t\t}\n\t\t\t\tif(l == 0) ans[x[i]] = c[p[ps]]; \/\/ \u524d\u9762\u6ca1\u6709\u5173\u4e8e\u8be5\u683c\u5b50\u7684\u64cd\u4f5c1\u4e86\uff0c\u5b89\u5fc3\u67d3\u8272\u5373\u53ef\n\t\t\t\telse if(p[ps] > t[x[i]][l - 1]) ans[x[i]] = c[p[ps]]; \/\/ \u64cd\u4f5c2\u4e0d\u80fd\u592a\u9760\u524d\u4e86\uff0c\u5982\u679c\u8be5\u683c\u5b50\u7684\u74f7\u7816\u8986\u76d6\u72b6\u6001\u53c8\u6539\u53d8\u4e86\u5c31\u4e0d\u80fd\u67d3\u4e86\n\t\t\t}\n\t\t}\n\t}\n\tfor(int i = 1; i <= n; i++){\n\t\tif(ans[i]) cout << ans[i];\n\t\telse cout << 'a';\n\t}\n\tcout << '\\n';\n\treturn 0;\n}<\/code><\/pre>\nE – Wheel Distance<\/h3>\n
signed main(){\n\tinit();\n\tdijkstra(n + 1); \/\/ \u8dd1\u5355\u6e90\u6700\u77ed\u8def\n\twhile(q--){\n\t\tint s, t; cin >> s >> t;\n\t\tif(t == n + 1){ \/\/ \u6b64\u65f6\u4e0d\u80fd\u53ea\u5728\u73af\u4e0a\u8d70\n\t\t\tcout << dis[s] << '\\n';\n\t\t\tcontinue;\n\t\t}\n\t\tint d = sum[t - 1] - sum[s - 1]; \/\/ \u73af\u4e0a\u8d70\u6cd5\u5176\u4e00\uff0c\u53e6\u4e00\u79cd\u89c1\u4e0b\n\t\tint ans = min({d, sum[n] - d, dis[s] + dis[t]});\n\t\tcout << ans << '\\n';\n\t}\n\treturn 0;\n}<\/code><\/pre>\nF – Count Cells in a Window<\/h3>\n
signed main(){\n\tcin >> n >> m >> q;\n\tfor(int i = 1; i <= n; i++){\n\t\tcin >> l[i] >> r[i];\n\t\tel[l[i]].push_back(i); \/\/ \u5b58l[i]\u66f4\u65b0\u9879\n\t\ter[r[i]].push_back(i); \/\/ \u5b58r[i]\u66f4\u65b0\u9879\n\t}\n\tfor(int i = 1; i <= q; i++){\n\t\tint a, b, c, d;\n\t\tcin >> a >> b >> c >> d;\n\t\tqry[d].push_back({b, 1, i}); \/\/ \u6309\u5217\u5b58\uff1a\u884cx\uff0c\u7b26\u53f7sign\uff0c\u64cd\u4f5c\u4e0b\u6807h\n\t\tqry[d].push_back({a - 1, -1, i});\n\t\tqry[c - 1].push_back({b, -1, i});\n\t\tqry[c - 1].push_back({a - 1, 1, i});\n\t}\n\tfor(int j = 1; j <= m; j++){\n\t\tfor(int i : el[j]){ \/\/ \u66f4\u65b0l[i]=y\u7684\n\t\t\tupdate(cnt, i, 1);\n\t\t\tupdate(sum, i, l[i]);\n\t\t}\n\t\tfor(int i : er[j]){ \/\/ \u66f4\u65b0r[i]=y\u7684\n\t\t\tupdate(cnt, i, -1);\n\t\t\tupdate(sum, i, -l[i]);\n\t\t\tupdate(csum, i, r[i] - l[i] + 1);\n\t\t}\n\t\tfor(auto i : qry[j]){ \/\/ \u6c42\u51fa\u4e00\u4e2a\u4e2a\u67e5\u8be2\u9879\n\t\t\tint qcnt = query(cnt, i.x);\n\t\t\tint qsum = query(sum, i.x);\n\t\t\tint qcsum = query(csum, i.x);\n\t\t\tint f = (j + 1) * qcnt - qsum + qcsum; \/\/ \u6c42f(x, y)\u7684\u5f0f\u5b50\n\t\t\tans[i.h] += (f * i.sign); \/\/ \u522b\u5fd8\u4e58\u7b26\u53f7\n\t\t}\n\t}\n\tfor(int i = 1; i <= q; i++){\n\t\tcout << ans[i] << '\\n';\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\u4ee5\u4e0a<\/h3>\n
——— END ———<\/h3>\n","protected":false},"excerpt":{"rendered":"