{"id":917,"date":"2014-06-15T09:09:11","date_gmt":"2014-06-15T01:09:11","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=917"},"modified":"2014-09-07T22:54:50","modified_gmt":"2014-09-07T14:54:50","slug":"srm-624","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-624\/","title":{"rendered":"SRM 624"},"content":{"rendered":"

250. BuildingHeights<\/h2>\n

Brief description:<\/h3>\n

\u7ed9\u5b9a n \u4e2a\u5efa\u7b51\u7684\u9ad8\u5ea6\uff0c\u4f60\u6240\u80fd\u6267\u884c\u7684\u552f\u4e00\u64cd\u4f5c\u662f\u5c06\u4e00\u4e2a\u5efa\u7b51\u7684\u9ad8\u5ea6 +1<\/code>.\u3002\u3002
\n\u3002\u3002\u3002\u3002 f(k)<\/code> \u8868\u793a\u5f97\u5230\u81f3\u5c11 k<\/code> \u4e2a\u76f8\u540c\u9ad8\u5ea6\u7684\u5efa\u7b51\uff0c\u81f3\u5c11\u9700\u8981\u8fdb\u884c\u591a\u5c11\u6b21\u64cd\u4f5c\u3002
\n\u6c42 Xor_{i=1}^n<\/code>\u3002<\/p>\n

<\/p>\n

Analysis:<\/h3>\n

\u3002\u3002\u6392\u5e8f\u3001\u3002\u4e4b\u540e\u679a\u4e3e\u76ee\u6807\u5efa\u7b51\u7684\u9ad8\u5ea6\u3002\u3002 $$O(n^2)$$ \u66b4\u529b\u5373\u53ef\u3002\u3002
\n\u3002\u56e0\u4e3a\u9700\u8981\u4f7f\u7528\u90e8\u5206\u548c\u3002\u3002\u3002\u679c\u65ad\u4ece 1 \u6807\u53f7\u5427\uff01<\/p>\n

450. DrivingPlans<\/h2>\n

Brief description:<\/h3>\n

\u7ed9\u5b9a\u4e00\u4e2a n<\/code> \u4e2a\u7ed3\u70b9\u7684\u8fb9\u6743\u975e\u8d1f\u7684\u65e0\u5411\u56fe\uff0c\u95ee 1->n<\/code> \u6700\u77ed\u8def\u5f84\u7684\u65b9\u6848\u6570\uff0c
\n\u65e0\u7a77\u65f6\u8f93\u51fa -1<\/code>\u3002<\/p>\n

Analysis:<\/h3>\n

\u6ca1\u6709\u8d1f\u73af\uff0c\u6709\u65e0\u7a77\u591a\u7ec4\u65b9\u6848\u6570\u5f53\u4e14\u4ec5\u5f53\u6700\u77ed\u8def\u5f84\u4e0a\u5b58\u5728\u6743\u503c\u548c\u4e3a 0<\/code> \u7684\u56de\u8def\uff0c\u56e0\u4e3a\u8fb9\u6743\u975e\u8d1f\u8fd9\u79cd\u60c5\u51b5\u4e5f\u5c31\u53ea\u9700\u8981\u5224\u65ad\u5355\u6761\u8fb9\u3002
\n\u76f4\u63a5 Dijkstra \u5c31\u53ef\u4ee5\u4e86\uff0c\u57fa\u672c\u4e2d\u7684\u57fa\u672c\u3002\u3002<\/p>\n

\r\nconst int N = 2009;\r\n\r\nVII adj[N];\r\nint d1[N], dn[N], dp[N] , n;\r\n\r\npriority_queue<PII, VII, greater<PII> > Q;\r\n\r\nvoid relax(int d[], int u, int v, int w){\r\n    if (d[v] > d[u] + w){\r\n        d[v] = d[u] + w;\r\n        Q.push(MP(d[v], v));\r\n    }\r\n}\r\n\r\n#define v it->fi\r\n#define w it->se\r\n\r\nint gao(){\r\n    VII I; REP_1(i, n) I.PB(MP(d1[i], i)); SRT(I);\r\n    fill(dp+1, dp+n+1, 0); dp[1] = 1;\r\n\r\n    ECH(it, I){\r\n        int u = it->se; ECH(it, adj[u]) if (d1[u] + w == d1[v]){\r\n            INC(dp[v], dp[u]);\r\n        }\r\n    }\r\n\r\n    return dp[n];\r\n}\r\n\r\n\r\nvoid Dijkstra(int s, int d[]){\r\n    while (!Q.empty()) Q.pop(); fill(d+1, d+n+1, INF); d[s] = 0; Q.push(MP(0, s));\r\n\r\n    while (!Q.empty()){\r\n        int du = Q.top().fi, u = Q.top().se; Q.pop();\r\n        if (du != d[u]) continue; ECH(it, adj[u]){\r\n            relax(d, u, v, w);\r\n        }\r\n    }\r\n}\r\n\r\nclass DrivingPlans {\r\n    public:\r\n    int count(int n, vector <int> A, vector <int> B, vector <int> C) {\r\n\r\n    \t::n = n; REP_1(i, n) adj[i].clear(); REP(i, A.size()){\r\n    \t\tadj[A[i]].PB(MP(B[i] , C[i]));\r\n    \t\tadj[B[i]].PB(MP(A[i] , C[i]));\r\n    \t}\r\n\r\n    \tDijkstra(1, d1); Dijkstra(n, dn);\r\n\r\n    \tREP(i, A.size()) if (!C[i]){\r\n            if (d1[A[i]] + dn[B[i]] == d1[n]) {\r\n                return -1;\r\n            }\r\n    \t}\r\n\r\n    \treturn gao();\r\n    }\r\n\r\n};\r\n<\/pre>\n
1000. TreeColoring<\/h2>\n
Brief description:<\/h3>\n
\u52a8\u6001\u7ef4\u62a4\u4e00\u4e2a\u6811\uff0c\u652f\u6301\uff0c\u5c06\u4e00\u4e2a\u70b9\u67d3\u6210\u84dd\u8272\u3002\u8be2\u95ee u \u70b9\u5230\u6240\u6709\u84dd\u8272\u7ed3\u70b9\u7684\u8ddd\u79bb\u548c\u3002
\n\u3002\u67d3\u8272\u53ea\u6709\u767d\u8272->\u84dd\u8272\u3002\u3002\u3002\u521d\u59cb\u90fd\u662f\u767d\u8272\u3001\u3001<\/p>\n
Analysis:<\/h3>\n
\u5982\u679c\u662f\u5b50\u6811\u548c\u7684\u8bdd\u3002\u3002\u5c31\u53ef\u4ee5\u76f4\u63a5\u79bb\u7ebf\u6811\u72b6\u6570\u7ec4\u641e\u3002\u3002\u4f46\u662f\u8fd9\u4e2a\u9898\u662f\u6240\u6709\u56db\u5468\u7684\u548c\u3002\u3002\u3002\u3002
\n\u3002\u3002\u3002\u3002\u4f3c\u4e4e\u53ef\u4ee5\u70b9\u5206\u6cbb\u4e0d\u8fc7\u52a8\u6001\u6811\u7684\u505a\u6cd5\u66f4\u52a0\u76f4\u89c9\u3002\u3002<\/p>\n
\u3002\u3002\u3002\u3002\u7ec8\u4e8e\u8c03\u8fc7\u4e86\u3002\u3002\u3002\u51e0\u4e2a\u6708\u6ca1\u5f04\u3002\u3002\u3002\u52a8\u6001\u6811\u7adf\u53d8\u5f97\u5982\u6b64\u751f\u758f\u3002\u3002
\n\u3002\u3002\u3002\u672c\u5730\u6d4b\u8bd5\u7684\u65f6\u5019\u9700\u8981\u6c47\u7f16\u8c03\u6808\u3002\u3002\u3002\uff08\u4f46\u662f\u8fd9\u6bb5\u4ee3\u7801\u4f3c\u4e4e\u5fc5\u987b\u653e\u5728 main() \u51fd\u6570\u4e2d\u3002\u3002\u5426\u5219\u76f4\u63a5 RE \uff1f\uff1f\uff1f\uff09
\n\u3002\u3002\u3002\u800c TC \u662f\u6ca1\u6709 main() \u51fd\u6570\u7684\u3002\u3002\u4e0d\u8fc7\u4ea4\u4e0a\u53bb\u4f3c\u4e4e\u6ca1\u9519\u3002\u3002\u770b\u6765 TC \u6808\u8db3\u591f\u7684\u6df1\u3002<\/p>\n
\u3002\uff08\u3002\u3002\u6bd4\u8d5b\u65f6\u82e5\u80fd\u7528 LCT \u5168\u573a A \u6389\u8fd9\u9898\u3002\u3002\u90a3\u5c06\u591a\u4e48\u534e\u4e3d\uff01\uff01\u3002\u3002\u3002\uff09<\/p>\n
\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/p>\n
\u5176\u5b9e\u5c31\u8fd9\u4e09\u884c\u3002\u3002\u5509\u3002\u3002<\/p>\n
\r\n     inline void upd(){\r\n        sz = l->sz+c0+r->sz+_sz, dd = l->dd+d0+r->dd;\r\n        ls = l->ls+_ls+r->ls+(l->dd+d0)*(sz-l->sz);\r\n        rs = l->rs+_ls+r->rs+r->dd*(sz-r->sz)+(LL)d0*l->sz;\r\n    }\r\n<\/pre>\n
…<\/p>\n
\u505a\u6cd5\u5c31\u662f\u4e09\u53c9\u52a8\u6001\u6811\u3002\u3002\u3002\u3002<\/p>\n
\r\n    static node *NIL; node *c[2], *p; int _sz; LL _ls;\r\n    int c0, d0, sz; LL dd, ls, rs;\r\n<\/pre>\n
c0: \u662f\u5426\u67d3\u8272\u3002
\nd0: \u5230\u7236\u4eb2\u7684\u8fb9\u6743\u3002
\nsz: \u5b50\u6811\u4e2d\u5305\u542b\u67d3\u8272\u7ed3\u70b9\u7684\u4e2a\u6570\u3002
\ndd: \u91cd\u94fe\u7684\u957f\u5ea6\u3002<\/p>\n
ls: \u5de6\u7aef\u70b9\u51fa\u53d1\u7684\u8ddd\u79bb\u548c\u3002
\nrs: \u53f3\u7aef\u70b9\u51fa\u53d1\u7684\u8ddd\u79bb\u548c\u3002<\/p>\n
_sz: \u865a\u5b69\u5b50\u7684 sz \u548c\u3002\u3002\u3002
\n_ls: \u865a\u5b69\u5b50\u7684 ls \u548c\u3002\u3002<\/p>\n
    \u5982\u679c\u6bd4\u8d5b\u65f6\u5927\u8111\u5b9e\u5728\u8fdb\u6c34\u3002\u3002\u3002\u4e0d\u59a8\u5148\u8003\u8651\u4e00\u6761\u94fe\u7248\u672c\u7684\u95ee\u9898\u3002\u3002\u3002
\n\uff08\u7ed9\u5b9a\u4e00\u6761\u94fe\uff0c\u6bcf\u6b21 toggle()<\/code> \u4e00\u4e2a\u70b9\uff0c\u8be2\u95ee\u6240\u6709\u67d3\u8272\u70b9\u5230\u67d0\u4e2a\u70b9\u7684\u8ddd\u79bb\u548c \uff09
\n\uff08\u663e\u7136\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528 splay \u53bb\u7ef4\u62a4\u8fd9\u4e2a\u95ee\u9898\u3002\u3002\u7565\u52a0\u601d\u7d22\u3002\u3002\u3002\u3002upd()<\/code> \u7684\u96cf\u5f62\u5c31\u6709\u4e86\u3002\u3002)
\n\uff08\u3002\u4e4b\u540e\u628a _sz<\/code> \u548c _ls<\/code> \u4e00\u5e76\u8003\u8651\u8fdb\u6765\u5c31\u53ef\u4ee5\u4e86\u3002\u3002\u865a\u5b69\u5b50\u7684\u4f5c\u7528\u548c\u53f3\u5b69\u5b50\u662f\u4e00\u81f4\u7684\u3002\u3002\uff09<\/p>\n
\u8be2\u95ee\u7684\u65f6\u5019\u6211\u4eec access()<\/code> \u8fd9\u4e2a\u70b9\u3002\u3002\u90a3\u4e48\u5b83\u73b0\u5728\u5c31\u6210\u4e3a\u4e00\u6761\u91cd\u94fe\u7684\u672b\u5c3e\uff08\u53f3\u7aef\u70b9\uff09\u3002\u3002
\n\u3002\u3002\u56e0\u6b64\u6b64\u65f6 rs<\/code> \u5c31\u662f\u7b54\u6848\u3002\u3002\u3002<\/p>\n
\r\n\r\nconst int N = int(1e5) + 9, M = 2 * N;\r\n\r\nnamespace LCT{\r\n\r\nstruct node{\r\n\r\n    static node *NIL; node *c[2], *p; int _sz; LL _ls;\r\n    int c0, d0, sz; LL dd, ls, rs; \/\/bool r0;\r\n\r\n#define NIL node::NIL\r\n#define l c[0]\r\n#define r c[1]\r\n#define lx x->l\r\n#define rx x->r\r\n#define px x->p\r\n#define ly y->l\r\n#define ry y->r\r\n#define py y->p\r\n\r\n    void reset(){\r\n        l = r = p = NIL; _sz = _ls = 0;\r\n        c0 = d0 = sz = dd = 0; ls = rs = 0; \/\/r0 = 0;\r\n    }\r\n\r\n    inline node(){\r\n        reset();\r\n    }\r\n\r\n    inline void rev(){\r\n        \/\/r0 ^= 1; swap(l, r); swap(ls, rs);\r\n    }\r\n\r\n    inline void upd(){\r\n        sz = l->sz+c0+r->sz+_sz, dd = l->dd+d0+r->dd;\r\n        ls = l->ls+_ls+r->ls+(l->dd+d0)*(sz-l->sz);\r\n        rs = l->rs+_ls+r->rs+r->dd*(sz-r->sz)+(LL)d0*l->sz;\r\n    }\r\n\r\n    inline void rls(){\r\n        \/*if (r0){\r\n            l->rev(), r->rev();\r\n            r0 = 0;\r\n        }*\/\r\n    }\r\n\r\n    inline int sgn(){return p->l==this?0:p->r==this?1:-1;}\r\n    inline void setc(int d,node*x){c[d]=x,px=this;}\r\n\r\n    inline void rot(int d){\r\n        node*y=p,*z=py;if(~y->sgn())z->setc(y->sgn(),this);else p=z;\r\n        y->setc(d,c[!d]),setc(!d,y),y->upd();\r\n    }\r\n    inline void rot(){rot(sgn());}\r\n\r\n    inline void fix(){if (~sgn()) p->fix(); rls();}\r\n\/*\r\n    inline node* splay(){\r\n        fix();while (~sgn()) rot(); upd();\r\n        return this;\r\n    }\r\n*\/\r\n\r\n    inline node*splay(){\r\n        fix();int a,b;while(~(a=sgn())){\r\n            if(~(b=(p->sgn())))(a^b?this:p)->rot(a),rot(b);\r\n            else rot(a);\r\n        }\r\n        upd();\r\n        return this;\r\n    }\r\n\r\n    inline node* acs(){\r\n        node *x = this, *y = NIL; do{\r\n            x->splay();\r\n            if (y != NIL) x->_sz -= y->sz, x->_ls -= y->ls;\r\n            if (rx != NIL) x->_sz += rx->sz, x->_ls += rx->ls;\r\n            rx = y, x->upd();\r\n            y = x, x = px;\r\n        } while (x != NIL);\r\n        return splay();\r\n    }\r\n\r\n    inline node* rt(){node* x; for (x = acs(); x->rls(), lx != NIL; x = lx); return x->splay();}\r\n    inline node* ert(){acs()->rev(); return this;}\r\n\r\n    void cut(){\r\n        acs(); l->p = l = NIL;\r\n    }\r\n\r\n    void tog(){\r\n        acs(); c0 = 1;\r\n    }\r\n\r\n    LL query(){\r\n        acs(); return rs;\r\n    }\r\n\r\n} *NIL, *T[N];\r\n\r\n\r\n\r\nint hd[N], suc[M], to[M], ww[N], n;\r\n#define aa to[i^1]\r\n#define bb to[i]\r\n#define w ww[i\/2]\r\n#define v bb\r\n\r\ninline void dfs(int u){\r\n    REP_G(i, u) if (T[v]->p == NIL){\r\n        T[v]->p = T[u], T[v]->d0 = w, dfs(v);\r\n    }\r\n    T[u]->upd();\r\n}\r\n\r\n} using namespace LCT;\r\n\r\nvoid init(){\r\n    NIL = new node(); REP(i, N) T[i] = new node();\r\n}\r\n\r\nint curValue; int genNextRandom() {\r\n    curValue = ((LL)curValue * 1999 + 17) % 1000003;\r\n    return curValue;\r\n}\r\n\r\nint distancee[N], parent[N], queryType[N], queryNode[N];\r\n\r\nclass TreeColoring {\r\npublic:\r\n\tlong long color(int n, int Q, int startSeed, int threshold, int maxDist) {\r\n\r\n        curValue = startSeed;\r\n\r\n        for (int i = 0; i < n-1; i++) {\r\n            distancee[i] = genNextRandom() % maxDist;\r\n            parent[i] = genNextRandom();\r\n            if (parent[i] < threshold) {\r\n                parent[i] = i;\r\n            } else {\r\n                parent[i] = parent[i] % (i + 1);\r\n            }\r\n        }\r\n\r\n        for (int i = 0; i < Q; i++) {\r\n            queryType[i] = genNextRandom() % 2 + 1;\r\n            queryNode[i] = genNextRandom() % n + 1;\r\n        }\r\n\r\n        \/\/ gen input..\r\n\r\n        if (!NIL) init(); else fill(hd+1, hd+n+1, 0);\r\n        REP_1(i, n) T[i]->reset();\r\n\r\n        int i = 2; FOR_1(ii, 2, n){\r\n            aa = ii, bb = parent[ii-2]+1, w = distancee[ii-2];\r\n            suc[i] = hd[aa], hd[aa] = i++;\r\n            suc[i] = hd[aa], hd[aa] = i++;\r\n        }\r\n\r\n        T[1]->p = T[0]; dfs(1); T[1]->p = NIL;\r\n\r\n        LL res = 0; REP(i, Q){\r\n            switch(queryType[i]){\r\n                case 2:\r\n                    res ^= T[queryNode[i]]->query();\r\n                break;\r\n                default:\r\n                    T[queryNode[i]]->tog();\r\n            }\r\n        }\r\n\r\n\t\treturn res;\r\n\t}\r\n};\r\n<\/pre>\n
— UPD —<\/p>\n
External link:<\/h2>\n
https:\/\/gist.github.com\/lychees\/27fd8661bd8489244d93<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
250. BuildingHeights Brief description: \u7ed9\u5b9a n \u4e2a\u5efa\u7b51\u7684\u9ad8\u5ea6\uff0c\u4f60\u6240\u80fd\u6267\u884c\u7684\u552f\u4e00\u64cd\u4f5c\u662f\u5c06\u4e00\u4e2a\u5efa\u7b51\u7684\u9ad8\u5ea6 +1.\u3002\u3002 \u3002\u3002\u3002\u3002 f(k) \u8868\u793a\u5f97\u5230\u81f3\u5c11 k \u4e2a\u76f8\u540c\u9ad8\u5ea6\u7684\u5efa\u7b51\uff0c\u81f3\u5c11\u9700\u8981\u8fdb\u884c\u591a\u5c11\u6b21\u64cd\u4f5c\u3002 \u6c42 Xor_{i=1}^n\u3002<\/p>\n","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":[17],"tags":[126,129,127],"class_list":["post-917","post","type-post","status-publish","format-standard","hentry","category-topcoder","tag-126","tag-129","tag-127"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-eN","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/917","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=917"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/917\/revisions"}],"predecessor-version":[{"id":918,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/917\/revisions\/918"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=917"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=917"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=917"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}