{"id":525,"date":"2018-12-26T19:09:10","date_gmt":"2018-12-26T11:09:10","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=525"},"modified":"2018-12-26T19:09:10","modified_gmt":"2018-12-26T11:09:10","slug":"lp4117-ynoi2018-%e4%ba%94%e5%bd%a9%e6%96%91%e6%96%93%e7%9a%84%e4%b8%96%e7%95%8c","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/12\/26\/lp4117-ynoi2018-%e4%ba%94%e5%bd%a9%e6%96%91%e6%96%93%e7%9a%84%e4%b8%96%e7%95%8c\/","title":{"rendered":"lp4117 Ynoi2018 \u4e94\u5f69\u6591\u6593\u7684\u4e16\u754c"},"content":{"rendered":"\n

\u867d\u7136\u6211\u6ca1\u6709\u73a9\u8fc7\u8fd9\u4e2aGalgame\uff0c\u4f46\u662f\u5c31\u622a\u56fe\u800c\u8a00\u753b\u98ce\u8fd8\u662f\u633a\u53ef\u7231\u7684\u3002
\n\u62b1\u6b49\u79bb\u9898\u4e86\u3002
\n\u8fd9\u662f\u4e00\u9053\u7531\u4e43\u7701\u7684\u7701\u9009\u9898\u3002
\n\u5927\u5bb6\u90fd\u77e5\u9053\u559c\u6b22\u7531\u4e43\u7684\u67d0\u4eba\u6700\u559c\u6b22\u7684\u5c31\u662f\u6570\u636e\u7ed3\u6784\u4e86\u3002
\n\u4ed4\u7ec6\u89c2\u5bdf\u8fd9\u9053\u9898\u7684\u6570\u636e\u8303\u56f4\uff0c\u6211\u4eec\u53ef\u4ee5\u60f3\u5230\u5206\u5757\u3002
\n\u5bf9\u4e8e\u6bcf\u4e2a\u5757\u91cc\u9762\u6570\u503c\u76f8\u540c\u7684\u6570\u7ef4\u62a4\u4e00\u4e2a\u5e76\u67e5\u96c6\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u5e76\u67e5\u96c6\u7ef4\u62a4\u5b83\u7684\u5927\u5c0f\u3002\u90a3\u4e48\u6211\u4eec\u6bcf\u4e00\u6b21\u4fee\u6539\uff0c\u5982\u679c\u662f\u66b4\u529b\u4fee\u6539\u5c31\u53ea\u9700\u8981\u6539\u53d8\u4e00\u4e2a\u5143\u7d20\u6240\u5728\u7684\u96c6\u5408\uff0c\u5982\u679c\u662f\u6574\u5757\u4fee\u6539\u5c31\u5c06\u5e76\u67e5\u96c6\u5408\u5e76\u3002
\n\u67e5\u8be2\u7684\u65f6\u5019\u5757\u5916\u90e8\u5206\u66b4\u529b\u66f4\u65b0\uff0c\u5feb\u5185\u90e8\u5206\u6309\u5757\u67e5\u8be2\u5373\u53ef\u3002
\n\u4f46\u662f\u8fd9\u4e00\u9898\u7684\u5e38\u6570\u7b80\u76f4\u4e27\u5fc3\u75c5\u72c2\uff0c\u6bd2\u7624lxl\u7b80\u76f4\u662f\u9b54\u9b3c\u3002SIZE\u5927\u4e86T\uff0cSIZE\u5c0f\u4e86MLE\u3002\u6211\u5361\u4e86\u6574\u6574\u5341\u4e5d\u6b21\uff0c\u6700\u7ec8\u7ed3\u5408\u524d\u4eba\u4f18\u79c0\u7ecf\u9a8c\uff0c\u4f7f\u7528unsigned char\u6210\u529f\u5361\u4e86\u8fc7\u53bb\u3002
\n\u5927\u5bb6\u8bb0\u4f4f\u8fd9\u7ec4\u9b54\u6cd5\u7684\u6570\u5b57\uff1a253-410<\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cmath>\n#define MAXNUM 410\nint SIZE,NUM;\nint bl[100005],lb[MAXNUM],rb[MAXNUM];\nint a[100005],tgb[MAXNUM];\nint val[100005],mx[100005],fa[100005];\nunsigned char cnt[MAXNUM][100005],loc[MAXNUM][100005];\nint n,m;\ninline int fthr(int X){\n\twhile(X^fa[X]){\n\t\tX=fa[X]=fa[fa[X]];\n\t}\n\treturn X;\n}\ninline void uni(int X,int A,int B){\n\t\/\/\u5c06X\u5757\u4e2d\u7684A\u5408\u5e76\u5230B\u5904\u3002\u82e5B\u5904\u5b58\u5728\u5219\u76f4\u63a5\u5408\u5e76\uff0c\u5426\u5219\u5c06B\u79fb\u52a8\u5230A\u5e76\u4fee\u6539A\u7684\u503c\u3002 \n\tloc[X][B]?fa[loc[X][A]+lb[X]-1]=loc[X][B]+lb[X]-1:(loc[X][B]=loc[X][A],val[loc[X][A]+lb[X]-1]=B);\n\tcnt[X][B]+=cnt[X][A],cnt[X][A]=loc[X][A]=0;\n}\ninline void del(int S,int X){\n\t\/\/\u5982\u679cX\u6bd4\u6700\u5927\u503c\u7684\u4e00\u534a\u8fd8\u8981\u5c0f\uff0c\u90a3\u4e48\u6211\u4eec\u8003\u8651\u5c06\u6240\u6709\u5c0f\u4e8eX\u7684\u4e0a\u79fb\uff0c\u5e76\u4e14\u4fee\u6539\u6807\u8bb0\uff1b\u5426\u5219\u5c06\u6240\u6709\u5927\u4e8eX\u7684\u4e0b\u79fb\u3002 \n\tif((X<<1)<=mx[S]-tgb[S]){\n\t\tfor(int i=tgb[S]+1;i<=tgb[S]+X;++i){\n\t\t\tif(loc[S][i]){\n\t\t\t\tuni(S,i,i+X);\n\t\t\t}\n\t\t}\n\t\ttgb[S]+=X; \n\t}else{\n\t\tfor(int i=X+tgb[S]+1;i<=mx[S];++i){\n\t\t\tif(loc[S][i]){\n\t\t\t\tuni(S,i,i-X);\n\t\t\t}\n\t\t}\n\t\tmx[S]=std::min(mx[S],tgb[S]+X);\n\t}\n}\ninline void pshd(int X){\n\tfor(int i=lb[X];i<=rb[X];++i){\n\t\ta[i]=val[fthr(i)];\n\t\tloc[X][a[i]]=cnt[X][a[i]]=0;\n\t\t\/\/\u5e94\u5f53\u5148\u6e05\u7a7a\u518d\u4fee\u6539\u6807\u8bb0\u3002 \n\t\ta[i]-=tgb[X];\n\t}\n\tfor(int i=lb[X];i<=rb[X];++i){\n\t\tfa[i]=0;\n\t}\n\ttgb[X]=0;\n}\ninline void updt(int X){\n\tmx[X]=0;\n\tfor(int i=lb[X];i<=rb[X];++i){\n\t\tmx[X]=std::max(mx[X],a[i]);\n\t\tloc[X][a[i]]?(fa[i]=loc[X][a[i]]+lb[X]-1):(fa[i]=i,val[i]=a[i],loc[X][a[i]]=i-lb[X]+1);\n\t\t++cnt[X][a[i]];\n\t}\n}\ninline void chng(int L,int R,int X){\n\tif(bl[L]^bl[R]){\n\t\tpshd(bl[L]),pshd(bl[R]);\n\t\tfor(int i=L;i<=rb[bl[L]];++i){\n\t\t\tif(a[i]>X){\n\t\t\t\ta[i]-=X;\n\t\t\t}\n\t\t}\n\t\tfor(int i=lb[bl[R]];i<=R;++i){\n\t\t\tif(a[i]>X){\n\t\t\t\ta[i]-=X;\n\t\t\t}\n\t\t}\n\t\tupdt(bl[L]),updt(bl[R]);\n\t\tfor(int i=bl[L]+1;i<=bl[R]-1;++i){\n\t\t\tdel(i,X);\n\t\t}\n\t}else{\n\t\tpshd(bl[L]);\n\t\tfor(int i=L;i<=R;++i){\n\t\t\tif(a[i]>X){\n\t\t\t\ta[i]-=X;\n\t\t\t}\n\t\t}\n\t\tupdt(bl[L]);\n\t}\n}\ninline int qry(int L,int R,int X){\n\tif(bl[L]^bl[R]){\n\t\tint rt=0;\n\t\tfor(int i=L;i<=rb[bl[L]];++i){\n\t\t\tif(val[fthr(i)]-tgb[bl[L]]==X){\n\t\t\t\t++rt;\n\t\t\t}\n\t\t}\n\t\tfor(int i=lb[bl[R]];i<=R;++i){\n\t\t\tif(val[fthr(i)]-tgb[bl[R]]==X){\n\t\t\t\t++rt;\n\t\t\t}\n\t\t}\n\t\t\/\/\u6ce8\u610f\u8fd9\u91cc\u51cf\u53bb\u7684\u662f\u5176\u6240\u5728\u5757\u7684lzytg \n\t\tfor(int i=bl[L]+1;i<=bl[R]-1;++i){\n\t\t\trt+=((X+tgb[i]<=100000)?cnt[i][X+tgb[i]]:0);\n\t\t}\n\t\treturn rt;\n\t}else{\n\t\tint rt=0;\n\t\tfor(int i=L;i<=R;++i){\n\t\t\tif(val[fthr(i)]-tgb[bl[L]]==X){\n\t\t\t\t++rt;\n\t\t\t}\n\t\t}\n\t\treturn rt;\n\t}\n}\ninline void DEBUG(){\n\tfor(int i=1;i<=n;++i){\n\t\tprintf(\"%d\/%d \",val[fthr(i)],a[i]);\n\t}\n\tputs(\"\");\n\tfor(int i=1;i<=NUM;++i){\n\t\tprintf(\"[%d %d|%d|%d],\",lb[i],rb[i],tgb[i],mx[i]);\n\t}\n\tputs(\"\");\n\t\/*\n\tfor(int i=1;i<=100;++i){\n\t\tif(loc[2][i]){\n\t\t\tprintf(\"{%d} \",i);\n\t\t}\n\t} \n\t*\/\n}\nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\tSIZE=253;\n\tNUM=std::ceil((double)n\/SIZE);\n\tfor(int i=1;i<=NUM;++i){\n\t\tlb[i]=(i-1)*SIZE+1;\n\t\trb[i]=i*SIZE;\n\t\tfor(int j=lb[i];j<=rb[i];++j){\n\t\t\tbl[j]=i;\n\t\t}\n\t}\n\trb[NUM]=n;\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t}\n\tfor(int i=1;i<=NUM;++i){\n\t\tupdt(i);\n\t}\n\tint op,l,r,x;\n\tfor(int i=1;i<=m;++i){\n\/\/\t\tDEBUG();\n\t\tscanf(\"%d%d%d%d\",&op,&l,&r,&x);\n\t\tif(op==1){\n\t\t\tchng(l,r,x);\n\t\t}else{\n\t\t\tprintf(\"%d\\n\",qry(l,r,x));\n\t\t}\n\t}\n}\n\nint main(){\n\/\/\tfreopen(\"test.out\",\"w\",stdout);\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u867d\u7136\u6211\u6ca1\u6709\u73a9\u8fc7\u8fd9\u4e2aGalgame\uff0c\u4f46\u662f\u5c31\u622a\u56fe\u800c\u8a00\u753b\u98ce\u8fd8\u662f\u633a\u53ef\u7231\u7684\u3002 \u62b1\u6b49\u79bb\u9898\u4e86\u3002 \u8fd9\u662f\u4e00\u9053\u7531\u4e43\u7701\u7684\u7701\u9009\u9898\u3002 \u5927 … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp4117 Ynoi2018 \u4e94\u5f69\u6591\u6593\u7684\u4e16\u754c\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":[74,68,47,45,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/525"}],"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=525"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/525\/revisions"}],"predecessor-version":[{"id":526,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/525\/revisions\/526"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=525"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}