http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1503<\/a><\/p>\nBrief description: <\/h3>\n
\u7565\u3002\uff09<\/p>\n
Analysis: <\/h3>\n
\u6d4b\u8bd5\u6a21\u677f\u3002\uff09<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n \r\nnamespace SBT{\r\n const int NN = int(1e5) + 9;\r\n int c[2][NN], sz[NN], ky[NN], tot;\r\n#define lx l[x]\r\n#define rx r[x]\r\n#define l c[d]\r\n#define r c[!d]\r\n#define kx ky[x]\r\n#define sx sz[x]\r\n#define d 0\r\n int new_node(int v = 0){\r\n int x=++tot;lx=rx=0;\r\n sx=1;kx=v;\r\n return x;\r\n }\r\n \r\n void upd(int x){\r\n sx=sz[lx]+1+sz[rx];\r\n }\r\n#undef d\r\n void rot(int &x,int d){\r\n int y=rx;rx=l[y];l[y]=x;\r\n upd(x),upd(y),x=y;\r\n }\r\n \r\n void fix(int &x,int d){\r\n if (sz[l[lx]] > sz[rx]) rot(x,!d);\r\n else{\r\n if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);\r\n else return;\r\n }\r\n d=0,fix(lx,0),fix(rx,1);\r\n fix(x,0),fix(x,1);\r\n }\r\n#define d 0\r\n \r\n int mini(int x){\r\n if (lx) return mini(lx);\r\n return ky[x];\r\n }\r\n \r\n void iod(int x){\r\n if (!x) return;\r\n iod(lx); printf("%d ", ky[x]); iod(rx);\r\n }\r\n \r\n void Ins(int &x,int v){\r\n if(!x) x = new_node(v);\r\n else{\r\n ++sz[x]; Ins(c[v>kx][x],v);\r\n fix(x,v>=kx);\r\n }\r\n }\r\n \r\n int d_key; void Del(int &x,int v){\r\n --sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){\r\n if(!lx||!rx) d_key = kx, x = lx | rx;\r\n else Del(lx,v+1), kx = d_key;\r\n }\r\n else Del(c[v>kx][x],v);\r\n }\r\n \r\n int Rank(int x,int v){\r\n int z=0;while(x){\r\n if(kx<v){\r\n z+=sz[lx]+1;\r\n x=rx;\r\n }\r\n else x=lx;\r\n }\r\n return z;\r\n }\r\n \r\n int Select(int x,int k){\r\n if (sz[lx] == k) return ky[x];\r\n return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);\r\n }\r\n \r\n bool Find(int x,int v){\r\n if (!x) return 0;if (kx==v) return 1;\r\n return Find(c[v>kx][x],v);\r\n }\r\n \r\n void Init(){\r\n tot = 0;\r\n }\r\n \r\n#undef d\r\n#undef l\r\n#undef r\r\n#undef lx\r\n#undef rx\r\n#undef sx\r\n#undef kx\r\n} using namespace SBT;\r\n \r\nint n, b, d, rt, cnt;\r\n \r\nvoid Insert(int v){\r\n if (v < b) return;\r\n v -= d; Ins(rt, v);\r\n}\r\n \r\nint main(){\r\n \r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n while (~scanf("%d %d", &n, &b)){\r\n \r\n Init(); rt = cnt = 0;\r\n \r\n DO(n){\r\n char cmd; RC(cmd); int k; RD(k); switch(cmd){\r\n case 'I':\r\n Insert(k);\r\n break;\r\n case 'A':\r\n d += k;\r\n break;\r\n case 'S':\r\n d -= k;\r\n while (rt && mini(rt) + d < b) Del(rt, mini(rt)),++cnt;\r\n break;\r\n default:\r\n if (k > sz[rt]) puts("-1");\r\n else{\r\n OT(Select(rt,sz[rt]-k)+d);\r\n }\r\n }\r\n }\r\n \r\n OT(cnt);\r\n }\r\n}\r\n<\/pre>\nhttps:\/\/gist.github.com\/lychees\/9fb9e11fba385b4100a9<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[133],"class_list":["post-980","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-offset"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fO","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/980","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=980"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/980\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=980"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=980"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=980"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}