{"id":201,"date":"2018-11-20T13:50:19","date_gmt":"2018-11-20T13:50:19","guid":{"rendered":"http:\/\/bytew.net\/?p=201"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"%e3%80%8cbzoj3262%e3%80%8d%e9%99%8c%e4%b8%8a%e8%8a%b1%e5%bc%80","status":"publish","type":"post","link":"https:\/\/bytew.net\/?p=201","title":{"rendered":"\u300cBZOJ3262\u300d\u964c\u4e0a\u82b1\u5f00"},"content":{"rendered":"

\u6709n\u6735\u82b1\uff0c\u6bcf\u6735\u82b1\u6709\u4e09\u4e2a\u5c5e\u6027\uff1a\u82b1\u5f62(s)\u3001\u989c\u8272(c)\u3001\u6c14\u5473(m)\uff0c\u53c8\u4e09\u4e2a\u6574\u6570\u8868\u793a\u3002\u73b0\u8981\u5bf9\u6bcf\u6735\u82b1\u8bc4\u7ea7\uff0c\u4e00\u6735\u82b1\u7684\u7ea7\u522b\u662f\u5b83\u62e5\u6709\u7684\u7f8e\u4e3d\u80fd\u8d85\u8fc7\u7684\u82b1\u7684\u6570\u91cf\u3002\u5b9a\u4e49\u4e00\u6735\u82b1A\u6bd4\u53e6\u4e00\u6735\u82b1B\u8981\u7f8e\u4e3d\uff0c\u5f53\u4e14\u4ec5\u5f53Sa>=Sb,Ca>=Cb,Ma>=Mb\u3002\u663e\u7136\uff0c\u4e24\u6735\u82b1\u53ef\u80fd\u6709\u540c\u6837\u7684\u5c5e\u6027\u3002\u9700\u8981\u7edf\u8ba1\u51fa\u8bc4\u51fa\u6bcf\u4e2a\u7b49\u7ea7\u7684\u82b1\u7684\u6570\u91cf\u3002<\/span><\/h2>\n

<\/p>\n

Input<\/h2>\n
\n
\u7b2c\u4e00\u884c\u4e3aN,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), \u5206\u522b\u8868\u793a\u82b1\u7684\u6570\u91cf\u548c\u6700\u5927\u5c5e\u6027\u503c\u3002<\/div>\n
\u4ee5\u4e0bN\u884c\uff0c\u6bcf\u884c\u4e09\u4e2a\u6574\u6570si, ci, mi (1 <= si, ci, mi <= K)\uff0c\u8868\u793a\u7b2ci\u6735\u82b1\u7684\u5c5e\u6027<\/div>\n<\/div>\n

Output<\/h2>\n
\n
\u5305\u542bN\u884c\uff0c\u5206\u522b\u8868\u793a\u8bc4\u7ea7\u4e3a0\u2026N-1\u7684\u6bcf\u7ea7\u82b1\u7684\u6570\u91cf\u3002<\/div>\n<\/div>\n

Sample Input<\/h2>\n
10 3
\n3 3 3
\n2 3 3
\n2 3 1
\n3 1 1
\n3 1 2
\n1 3 1
\n1 1 2
\n1 2 2
\n1 3 2
\n1 2 1
\n<\/span><\/div>\n

Sample Output<\/h2>\n
3
\n1
\n3
\n0
\n1
\n0
\n1
\n0
\n0
\n1
\n<\/span><\/div>\n

HINT<\/h2>\n
\n

1 <= N <= 100,000, 1 <= K <= 200,000<\/p>\n

\u8fd9\u662f\u4e00\u9053CDQ\u5206\u6cbb\u7ecf\u5178\u9898<\/p>\n

BZOJ1176\uff1a\u8fd8\u662f\u8fd9\u9053\u9898\uff0c\u52a0\u4e00\u52a0\u5bb9\u65a5<\/p>\n<\/div>\n

#include <cstdio>\n#include <vector>\n#include <cstring>\n#include <iostream>\n#include <algorithm>\nusing namespace std;\ntypedef long long ll;\ntemplate<typename T> void read(T &x){\n\tx = 0;char ch = getchar();\n\twhile(!isdigit(ch))ch=getchar();\n\twhile(isdigit(ch)){x = x*10+ch-48;ch=getchar();}\n}\nstruct fl{\n\tint a,b,c,ans = 0;\n} a[100010];\nbool cmp1(fl a,fl b){\n\tif(a.a!=b.a)return a.a<b.a;\n\tif(a.b!=b.b)return a.b<b.b;\n\tif(a.c!=b.c)return a.c<b.c;\n\treturn a.ans < b.ans;\n}\nbool cmp2(fl a,fl b){\n\treturn a.b<b.b;\n}\nint n,k,level[100010],buc[200020],szsz[200020];\nvoid add(int p,int v){while(p<200020){szsz[p]+=v;p+=p&(-p);}}\nint query(int p){int ret = 0;while(p){ret+=szsz[p];p-=p&(-p);}return ret;}\nvoid solve(int st,int sz){\n\tif(sz == 1)return;\n\tint mid = sz\/2;\n\tsolve(st,mid);solve(st+mid,sz-mid);\n\tsort(a+st,a+st+mid,cmp2);sort(a+st+mid,a+st+sz,cmp2);\n\tint p = 0;\n\tfor(int i=st+mid;i<st+sz;i++){\n\t\twhile(p<mid && a[st+p].b<=a[i].b){\n\t\t\tadd(a[st+p].c,1);\n\t\t\t++p;\n\t\t}\n\t\ta[i].ans+=query(a[i].c);\n\t}\n\tfor(int i=0;i<p;i++)add(a[st+i].c,-1);\n}\nint main() {\n\tread(n);read(k);\n\tfor(int i=0;i<n;i++){\n\t\tread(a[i].a);read(a[i].b);read(a[i].c);\n\t}\n\tsort(a,a+n,cmp1);\n\tsolve(0,n);\n\tsort(a,a+n,cmp1);\n\tfor(int i=n-1;i>=0;i--){\n\t\tbuc[a[i].ans]++;\n\t\tif(i&&a[i].a == a[i-1].a && a[i].b == a[i-1].b && a[i].c == a[i-1].c)a[i-1].ans = a[i].ans;\n\t}\n\tfor(int i=0;i<n;i++)cout<<buc[i]<<'\\n';\n\treturn 0;\n}\n<\/pre>\n ","protected":false},"excerpt":{"rendered":"
\u6709n\u6735\u82b1\uff0c\u6bcf\u6735\u82b1\u6709\u4e09\u4e2a\u5c5e\u6027\uff1a\u82b1\u5f62(s)\u3001\u989c\u8272(c)\u3001\u6c14\u5473(m)\uff0c\u53c8\u4e09\u4e2a\u6574\u6570\u8868\u793a\u3002\u73b0\u8981\u5bf9\u6bcf\u6735\u82b1\u8bc4\u7ea7\uff0c\u4e00\u6735\u82b1\u7684\u7ea7\u522b […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/201"}],"collection":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=201"}],"version-history":[{"count":1,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/201\/revisions"}],"predecessor-version":[{"id":758,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/201\/revisions\/758"}],"wp:attachment":[{"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=201"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=201"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}