{"id":362,"date":"2010-08-25T09:49:00","date_gmt":"2010-08-25T01:49:00","guid":{"rendered":"http:\/\/localhost\/?p=362"},"modified":"2010-08-25T09:49:00","modified_gmt":"2010-08-25T01:49:00","slug":"jsoi2008_martian_prefix","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=362","title":{"rendered":"[JSOI2008]\u706b\u661f\u4ebaprefix"},"content":{"rendered":"\n

[JSOI2008]\u706b\u661f\u4ebaprefix <\/p>\n

Time Limit:10000MS  Memory Limit:165536K
Total Submit:127 Accepted:35
Case Time Limit:2000MS<\/p>\n

Description <\/strong><\/p>\n

\u706b\u661f\u4eba\u6700\u8fd1\u7814\u7a76\u4e86\u4e00\u79cd\u64cd\u4f5c\uff1a\u6c42\u4e00\u4e2a\u5b57\u4e32\u4e24\u4e2a\u540e\u7f00\u7684\u516c\u5171\u524d\u7f00\u3002\u6bd4\u65b9\u8bf4\uff0c\u6709\u8fd9\u6837\u4e00\u4e2a\u5b57\u7b26\u4e32\uff1amadamimadam\uff0c\u6211\u4eec\u5c06\u8fd9\u4e2a\u5b57\u7b26\u4e32\u7684\u5404\u4e2a\u5b57\u7b26\u4e88\u4ee5\u6807\u53f7\uff1a
\u5e8f\u53f7\uff1a 1 2 3 4 5 6 7 8 9 10 11
\u5b57\u7b26 m a d a m i m a d a m
\u73b0\u5728\uff0c\u706b\u661f\u4eba\u5b9a\u4e49\u4e86\u4e00\u4e2a\u51fd\u6570LCQ(x, y)\uff0c\u8868\u793a\uff1a\u8be5\u5b57\u7b26\u4e32\u4e2d\u7b2cx\u4e2a\u5b57\u7b26\u5f00\u59cb\u7684\u5b57\u4e32\uff0c\u4e0e\u8be5\u5b57\u7b26\u4e32\u4e2d\u7b2cy\u4e2a\u5b57\u7b26\u5f00\u59cb\u7684\u5b57\u4e32\uff0c\u4e24\u4e2a\u5b57\u4e32\u7684\u516c\u5171\u524d\u7f00\u7684\u957f\u5ea6\u3002\u6bd4\u65b9\u8bf4\uff0cLCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0
\u5728\u7814\u7a76LCQ\u51fd\u6570\u7684\u8fc7\u7a0b\u4e2d\uff0c\u706b\u661f\u4eba\u53d1\u73b0\u4e86\u8fd9\u6837\u7684\u4e00\u4e2a\u5173\u8054\uff1a\u5982\u679c\u628a\u8be5\u5b57\u7b26\u4e32\u7684\u6240\u6709\u540e\u7f00\u6392\u597d\u5e8f\uff0c\u5c31\u53ef\u4ee5\u5f88\u5feb\u5730\u6c42\u51faLCQ\u51fd\u6570\u7684\u503c\uff1b\u540c\u6837\uff0c\u5982\u679c\u6c42\u51fa\u4e86LCQ\u51fd\u6570 \u7684\u503c\uff0c\u4e5f\u53ef\u4ee5\u5f88\u5feb\u5730\u5c06\u8be5\u5b57\u7b26\u4e32\u7684\u540e\u7f00\u6392\u597d\u5e8f\u3002
\u5c3d\u7ba1\u706b\u661f\u4eba\u806a\u660e\u5730\u627e\u5230\u4e86\u6c42\u53d6LCQ\u51fd\u6570\u7684\u5feb\u901f\u7b97\u6cd5\uff0c\u4f46\u4e0d\u7518\u5fc3\u8ba4\u8f93\u7684\u5730\u7403\u4eba\u53c8\u7ed9\u706b\u661f\u4eba\u51fa\u4e86\u4e2a\u96be\u9898\uff1a\u5728\u6c42\u53d6LCQ\u51fd\u6570\u7684\u540c\u65f6\uff0c\u8fd8\u53ef\u4ee5\u6539\u53d8\u5b57\u7b26\u4e32\u672c\u8eab\u3002\u5177\u4f53\u5730 \u8bf4\uff0c\u53ef\u4ee5\u66f4\u6539\u5b57\u7b26\u4e32\u4e2d\u67d0\u4e00\u4e2a\u5b57\u7b26\u7684\u503c\uff0c\u4e5f\u53ef\u4ee5\u5728\u5b57\u7b26\u4e32\u4e2d\u7684\u67d0\u4e00\u4e2a\u4f4d\u7f6e\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\u3002\u5730\u7403\u4eba\u60f3\u8003\u9a8c\u4e00\u4e0b\uff0c\u5728\u5982\u6b64\u590d\u6742\u7684\u95ee\u9898\u4e2d\uff0c\u706b\u661f\u4eba\u662f\u5426\u8fd8\u80fd\u591f\u505a\u5230\u5f88\u5feb\u5730\u6c42 \u53d6LCQ\u51fd\u6570\u7684\u503c\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u7b2c\u4e00\u884c\u7ed9\u51fa\u521d\u59cb\u7684\u5b57\u7b26\u4e32\u3002
\u7b2c\u4e8c\u884c\u662f\u4e00\u4e2a\u975e\u8d1f\u6574\u6570M\uff0c\u8868\u793a\u64cd\u4f5c\u7684\u4e2a\u6570\u3002
\u63a5\u4e0b\u6765\u7684M\u884c\uff0c\u6bcf\u884c\u63cf\u8ff0\u4e00\u4e2a\u64cd\u4f5c\u3002\u64cd\u4f5c\u67093\u79cd\uff0c\u5982\u4e0b\u6240\u793a\uff1a
1\u3001 \u8be2\u95ee\u3002
\u8bed\u6cd5\uff1aQ x y\uff0cx, y\u5747\u4e3a\u6b63\u6574\u6570\u3002
\u529f\u80fd\uff1a\u8ba1\u7b97LCQ(x, y)
\u9650\u5236\uff1a1 <= x, y <= \u5f53\u524d\u5b57\u7b26\u4e32\u957f\u5ea6\u3002
2\u3001 \u4fee\u6539\u3002
\u8bed\u6cd5\uff1aR x d\uff0cx\u662f\u6b63\u6574\u6570\uff0cd\u662f\u5b57\u7b26\u3002
\u529f\u80fd\uff1a\u5c06\u5b57\u7b26\u4e32\u4e2d\u7b2cx\u4e2a\u6570\u4fee\u6539\u4e3a\u5b57\u7b26d\u3002
\u9650\u5236\uff1ax\u4e0d\u8d85\u8fc7\u5f53\u524d\u5b57\u7b26\u4e32\u957f\u5ea6\u3002
3\u3001 \u63d2\u5165\uff1a
\u8bed\u6cd5\uff1aI x d\uff0cx\u662f\u975e\u8d1f\u6574\u6570\uff0cd\u662f\u5b57\u7b26\u3002
\u529f\u80fd\uff1a\u5728\u5b57\u7b26\u4e32\u7b2cx\u4e2a\u5b57\u7b26\u4e4b\u540e\u63d2\u5165\u5b57\u7b26d\uff0c\u5982\u679cx = 0\uff0c\u5219\u5728\u5b57\u7b26\u4e32\u5f00\u5934\u63d2\u5165\u3002
\u9650\u5236\uff1ax\u4e0d\u8d85\u8fc7\u5f53\u524d\u5b57\u7b26\u4e32\u957f\u5ea6\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u5bf9\u4e8e\u8f93\u5165\u6587\u4ef6\u4e2d\u6bcf\u4e00\u4e2a\u8be2\u95ee\u64cd\u4f5c\uff0c\u4f60\u90fd\u5e94\u8be5\u8f93\u51fa\u5bf9\u5e94\u7684\u7b54\u6848\u3002\u4e00\u4e2a\u7b54\u6848\u4e00\u884c\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n

7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11<\/p>\n

Sample Output <\/strong><\/p>\n

5
1
0
2
1<\/p>\n

\u6570\u636e\u89c4\u6a21\uff1a
\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c\u6ee1\u8db3\uff1a
1\u3001 \u6240\u6709\u5b57\u7b26\u4e32\u81ea\u59cb\u81f3\u7ec8\u90fd\u53ea\u6709\u5c0f\u5199\u5b57\u6bcd\u6784\u6210\u3002
2\u3001 M <= 150,000
3\u3001 \u5b57\u7b26\u4e32\u957f\u5ea6L\u81ea\u59cb\u81f3\u7ec8\u90fd\u6ee1\u8db3L <= 100,000
4\u3001 \u8be2\u95ee\u64cd\u4f5c\u7684\u4e2a\u6570\u4e0d\u8d85\u8fc710,000\u4e2a\u3002<\/p>\n

\u5bf9\u4e8e\u7b2c1\uff0c2\u4e2a\u6570\u636e\uff0c\u5b57\u7b26\u4e32\u957f\u5ea6\u81ea\u59cb\u81f3\u7ec8\u90fd\u4e0d\u8d85\u8fc71,000
\u5bf9\u4e8e\u7b2c3\uff0c4\uff0c5\u4e2a\u6570\u636e\uff0c\u6ca1\u6709\u63d2\u5165\u64cd\u4f5c\u3002<\/p>\n

Source <\/strong><\/p>\n

\u8fd9\u9898\u628a\u6211\u641e\u6bdb\u4e86\u5927\u56e7\u3002\u3002\u3002
\u65e0\u7406\u7531WA N\u6b21\u3002\u3002\u6700\u540e\u53d1\u73b0\u662f\u7206Stack\u4e86\u7011\u5e03\u6c57\u3002\u3002\u3002
\u56e0\u4e3a\u6211\u61d2\u5f97\u4e00\u5f00\u59cb\u5efaSplay\uff0c\u6240\u4ee5\u4e00\u5f00\u59cb\u5c31\u662f\u66b4\u529b\u63d2\u5165\u3002\u3002
\u7136\u540eSplay\u4f1a\u53d8\u6210\u4e00\u6761\u94fe\uff0c\u7136\u540e\u5c31\u7206Stack\u4e86\u3002\u3002\u3002
\u6211\u6211\u6211\u3002\u3002\u300210W\u4e2a\u70b9\u5c31\u7206\u6808\u554a\u3002\u3002\u3002
\u4ee5\u540eSplay\u770b\u6765\u4e00\u5b9a\u8981\u5199\u975e\u9012\u5f52\u7684\u56e7\u3002\u3002
\u7b97\u6cd5\u5b9e\u9645\u4e0a\u633a\u7b80\u5355\u7684\u3002\u3002
\u5c31\u662f\u7528\u4e00\u4e2aSplay\u7ef4\u62a4Hash\u503c\uff0c\u7136\u540e\u4e8c\u5206\u5224\u5b9a\u6700\u5927\u957f\u5ea6\u3002\u3002
Code\uff1a
www.ideone.com\/XOZXT<\/a> <\/p>\n","protected":false},"excerpt":{"rendered":"

[JSOI2008]\u706b\u661f\u4ebaprefix Time Limit:10000MS  Memory Limit:165536KTotal Submit:127 Accepted:35 Case Time Limit:2000MS Description \u706b\u661f\u4eba\u6700\u8fd1\u7814\u7a76\u4e86\u4e00\u79cd\u64cd\u4f5c\uff1a\u6c42\u4e00\u4e2a\u5b57\u4e32\u4e24\u4e2a\u540e\u7f00\u7684\u516c\u5171\u524d\u7f00\u3002\u6bd4\u65b9\u8bf4\uff0c\u6709\u8fd9\u6837\u4e00\u4e2a\u5b57\u7b26\u4e32\uff1amadamimadam\uff0c\u6211\u4eec\u5c06\u8fd9\u4e2a\u5b57\u7b26\u4e32\u7684\u5404\u4e2a\u5b57\u7b26\u4e88\u4ee5\u6807\u53f7\uff1a \u5e8f\u53f7\uff1a 1 2 3 4 5 6 7 8 9 10 11 \u5b57\u7b26 m a d a m i m a d a m \u73b0\u5728\uff0c\u706b\u661f\u4eba\u5b9a\u4e49\u4e86\u4e00\u4e2a\u51fd\u6570LCQ(x, y)\uff0c\u8868\u793a\uff1a\u8be5\u5b57\u7b26\u4e32\u4e2d\u7b2cx\u4e2a\u5b57\u7b26\u5f00\u59cb\u7684\u5b57\u4e32\uff0c\u4e0e\u8be5\u5b57\u7b26\u4e32\u4e2d\u7b2cy\u4e2a\u5b57\u7b26\u5f00\u59cb\u7684\u5b57\u4e32\uff0c\u4e24\u4e2a\u5b57\u4e32\u7684\u516c\u5171\u524d\u7f00\u7684\u957f\u5ea6\u3002\u6bd4\u65b9\u8bf4\uff0cLCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 \u5728\u7814\u7a76LCQ\u51fd\u6570\u7684\u8fc7\u7a0b\u4e2d\uff0c\u706b\u661f\u4eba\u53d1\u73b0\u4e86\u8fd9\u6837\u7684\u4e00\u4e2a\u5173\u8054\uff1a\u5982\u679c\u628a\u8be5\u5b57\u7b26\u4e32\u7684\u6240\u6709\u540e\u7f00\u6392\u597d\u5e8f\uff0c\u5c31\u53ef\u4ee5\u5f88\u5feb\u5730\u6c42\u51faLCQ\u51fd\u6570\u7684\u503c\uff1b\u540c\u6837\uff0c\u5982\u679c\u6c42\u51fa\u4e86LCQ\u51fd\u6570 \u7684\u503c\uff0c\u4e5f\u53ef\u4ee5\u5f88\u5feb\u5730\u5c06\u8be5\u5b57\u7b26\u4e32\u7684\u540e\u7f00\u6392\u597d\u5e8f\u3002 \u5c3d\u7ba1\u706b\u661f\u4eba\u806a\u660e\u5730\u627e\u5230\u4e86\u6c42\u53d6LCQ\u51fd\u6570\u7684\u5feb\u901f\u7b97\u6cd5\uff0c\u4f46\u4e0d\u7518\u5fc3\u8ba4\u8f93\u7684\u5730\u7403\u4eba\u53c8\u7ed9\u706b\u661f\u4eba\u51fa\u4e86\u4e2a\u96be\u9898\uff1a\u5728\u6c42\u53d6LCQ\u51fd\u6570\u7684\u540c\u65f6\uff0c\u8fd8\u53ef\u4ee5\u6539\u53d8\u5b57\u7b26\u4e32\u672c\u8eab\u3002\u5177\u4f53\u5730 \u8bf4\uff0c\u53ef\u4ee5\u66f4\u6539\u5b57\u7b26\u4e32\u4e2d\u67d0\u4e00\u4e2a\u5b57\u7b26\u7684\u503c\uff0c\u4e5f\u53ef\u4ee5\u5728\u5b57\u7b26\u4e32\u4e2d\u7684\u67d0\u4e00\u4e2a\u4f4d\u7f6e\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\u3002\u5730\u7403\u4eba\u60f3\u8003\u9a8c\u4e00\u4e0b\uff0c\u5728\u5982\u6b64\u590d\u6742\u7684\u95ee\u9898\u4e2d\uff0c\u706b\u661f\u4eba\u662f\u5426\u8fd8\u80fd\u591f\u505a\u5230\u5f88\u5feb\u5730\u6c42 \u53d6LCQ\u51fd\u6570\u7684\u503c\u3002 Input […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/362"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=362"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/362\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=362"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=362"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=362"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}