{"id":388,"date":"2018-11-09T20:14:57","date_gmt":"2018-11-09T12:14:57","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=388"},"modified":"2018-11-09T20:15:33","modified_gmt":"2018-11-09T12:15:33","slug":"lp1486-noi2004-%e9%83%81%e9%97%b7%e7%9a%84%e5%87%ba%e7%ba%b3%e5%91%98","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/11\/09\/lp1486-noi2004-%e9%83%81%e9%97%b7%e7%9a%84%e5%87%ba%e7%ba%b3%e5%91%98\/","title":{"rendered":"lp1486 NOI2004 \u90c1\u95f7\u7684\u51fa\u7eb3\u5458"},"content":{"rendered":"

\uff08\u4f3c\u4e4e\u5f88\u5c11\u770b\u89c1\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u505a\u6cd5\u7684\u6837\u5b50\u3002\u4f46\u662f\u6743\u503c\u7ebf\u6bb5\u6811\u5982\u679c\u52a8\u6001\u5f00\u70b9\u3001\u5927\u80c6\u5361\u5e38\u7684\u8bdd\uff0c\u662f\u53ef\u4ee5\u8dd1\u5f97\u98de\u5feb\u7684\u3002\uff09
\n\u9996\u5148\u770b\u4e00\u4e0b\u9898\u9762\uff0c\u53d1\u73b0\u503c\u57df\u5f88\u5c0f\uff0c\u5f88\u5bb9\u6613\u5c31\u53ef\u4ee5\u60f3\u5230\u7528\u6743\u503c\u7ebf\u6bb5\u6811\u7ef4\u62a4\u3002
\n\u652f\u6301\uff1a\u5355\u70b9\u52a0\uff0c\u533a\u95f4\u6e05\u96f6\uff0c\u67e5\u8be2\u7b2ck\u5927\u7684\u6743\u503c\u7ebf\u6bb5\u6811\u3002
\n\u5f53\u7136\u8fd9\u9898\u6709\u4e00\u4e9b\u7ec6\u8282\u3002
\n\u4e00\uff1a\u5982\u679c\u521d\u59cb\u5de5\u8d44\u4f4e\u4e8e\u5de5\u8d44\u4e0b\u9650\uff0c\u90a3\u4e48\u8fd9\u4e2a\u4eba\u5c31\u4e0d\u5b58\u5728\u3002
\n\u4e8c\uff1a\u7ef4\u62a4\u7684\u662f\u7b2c\\(k\\)\u5927\u7684\u800c\u975e\u7b2c\\(k\\)\u5c0f\u7684\u3002
\n\u4e09\uff1a\u7531\u4e8e\u662f\u4e25\u683c\u5c0f\u4e8e\u5de5\u8d44\u4e0b\u9650\uff0c\u8981\u6ce8\u610f\u8fb9\u754c\u7684\u5f00\u95ed\u6027\u3002\u6700\u597d\u5c06\u516c\u5f0f\u5199\u51fa\u6765\u3002 <\/p>\n

#include<iostream>\r\n#include<cstdio>\r\nusing namespace std;\r\n#define LS (X<<1)\r\n#define RS (X<<1|1)\r\n#define LEN (R-L+1)\r\n#define MID ((L+R)>>1)\r\n#define LLEN (MID-L+1)\r\n#define RLEN (R-MID) \r\n\/\/\u652f\u6301\uff1a\u5355\u70b9\u52a0\uff0c\u533a\u95f4\u6e05\u96f6\uff0c\u67e5\u8be2\u7b2ck\u5927\u7684\u6743\u503c\u7ebf\u6bb5\u6811\u3002\r\nint tr[2000005],cnt=0; \r\ninline void updt(int X){\r\n\ttr[X]=tr[LS]+tr[RS];\r\n}\r\ninline void pshd(int X,int L,int R){\r\n\tif(!tr[X]){\r\n\t\ttr[LS]=tr[RS]=0;\r\n\t}\r\n}\r\ninline void add(int X,int L,int R,int A){\r\n\tif(L==R){\r\n\t\t++tr[X];\r\n\t\treturn;\r\n\t}\r\n\tpshd(X,L,R);\r\n\tif(A<=MID){\r\n\t\tadd(LS,L,MID,A);\r\n\t}else{\r\n\t\tadd(RS,MID+1,R,A);\r\n\t}\r\n\tupdt(X);\r\n}\r\ninline void clr(int X,int L,int R,int A,int B){\r\n\tif(A<=L&&R<=B){\r\n\t\tcnt+=tr[X];\r\n\t\ttr[X]=0;\r\n\t\treturn;\r\n\t}\r\n\tpshd(X,L,R);\r\n\tif(A<=MID){\r\n\t\tclr(LS,L,MID,A,B);\r\n\t}\r\n\tif(B>MID){\r\n\t\tclr(RS,MID+1,R,A,B);\r\n\t}\r\n\tupdt(X);\r\n}\r\ninline int srch(int X,int L,int R,int K){\r\n\tif(L==R){\r\n\t\treturn L;\r\n\t}\r\n\tpshd(X,L,R);\r\n\tif(tr[RS]<K){\r\n\t\treturn srch(LS,L,MID,K-tr[RS]);\r\n\t}else{\r\n\t\treturn srch(RS,MID+1,R,K);\r\n\t}\r\n}\r\ninline int qry(int X,int L,int R,int A,int B){\r\n\tif(A<=L&&R<=B){\r\n\t\treturn tr[X];\r\n\t}\r\n\tpshd(X,L,R);\r\n\tint rt=0;\r\n\tif(A<=MID){\r\n\t\trt+=qry(LS,L,MID,A,B);\r\n\t}\r\n\tif(B>MID){\r\n\t\trt+=qry(RS,MID+1,R,A,B);\r\n\t}\r\n\tupdt(X);\r\n\treturn rt;\r\n}\r\n\/\/1 k \u63d2\u5165\u5927\u5c0f\u4e3ak\u7684\u70b9\r\n\/\/2 k \u5168\u90e8\u6570\u52a0\u4e0ak\r\n\/\/3 k \u5168\u90e8\u6570\u51cf\u53bbk\r\n\/\/4 k \u67e5\u8be2\u7b2ck\u5927\u7684\u503c \r\nint n,m,tg=0,k;\r\nchar op[4];\r\nvoid init(){\r\n\tscanf(\"%d%d\",&n,&m);\r\n\t--m;\r\n\tfor(int i=1;i<=n;++i){\r\n\t\tcin>>op;\r\n\t\tscanf(\"%d\",&k);\r\n\t\tif(op[0]=='I'){\r\n\t\t\t\/\/\u6ce8\u610f\u5927\u4e8e\u4e0e\u5927\u7b49\u4e8e\u3002 \r\n\t\t\tif(k>m){\r\n\t\t\t\tadd(1,1,300001,k+100001+tg);\r\n\t\t\t}\r\n\t\t}else if(op[0]=='A'){\r\n\t\t\ttg-=k; \r\n\t\t}else if(op[0]=='S'){\r\n\t\t\ttg+=k;\r\n\t\t\tclr(1,1,300001,1,m+100001+tg);\r\n\t\t}else if(op[0]=='F'){\r\n\t\t\tif(qry(1,1,300001,1,300001)<k){\r\n\t\t\t\tputs(\"-1\");\r\n\t\t\t}else{\r\n\t\t\t\tprintf(\"%d\\n\",srch(1,1,300001,k)-100001-tg);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tprintf(\"%d\",cnt);\r\n}\r\nint main(){\r\n\tinit();\r\n\treturn 0;\r\n}<\/code><\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\uff08\u4f3c\u4e4e\u5f88\u5c11\u770b\u89c1\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u505a\u6cd5\u7684\u6837\u5b50\u3002\u4f46\u662f\u6743\u503c\u7ebf\u6bb5\u6811\u5982\u679c\u52a8\u6001\u5f00\u70b9\u3001\u5927\u80c6\u5361\u5e38\u7684\u8bdd\uff0c\u662f\u53ef\u4ee5\u8dd1\u5f97\u98de\u5feb\u7684\u3002\uff09 \u9996\u5148\u770b\u4e00 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp1486 NOI2004 \u90c1\u95f7\u7684\u51fa\u7eb3\u5458\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[50,43,49,8,6,48,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/388"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=388"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/388\/revisions"}],"predecessor-version":[{"id":389,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/388\/revisions\/389"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=388"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=388"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=388"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}