【题目描述】
见 UOJ 好咯。
【题目链接】
UOJ 58 糖果公园 【WC 2013】
BZOJ 3052 糖果公园
【解题思路】
树上带修改莫队,详见 莫队算法 - 学习笔记
【AC代码】
祝大家一遍 A 掉,反正我没能做到,还好我做这题时没啥人...
#include <cstdio> #include <algorithm> #include <cmath> namespace io{ const int INSIZE = 1 << 15, OTSIZE = 1 << 20; char inBuf[INSIZE], otBuf[OTSIZE], *S, *T, ch; int now; inline void init(){ S = T = NULL; now = 0; } inline int getchar(){ if(S == T) S = inBuf, T = inBuf + fread(inBuf, 1, INSIZE, stdin); if(S == T) return EOF; return *S++; } template<typename Int> inline void readint(Int &x){ Int f = 1; for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1; for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); x *= f; } inline void flush(){ if(now) fwrite(otBuf, 1, now, stdout), now = 0; } inline void putchar(char ch){ otBuf[now++] = ch; if(now == OTSIZE) flush(); } template<typename Int> inline void putint(Int x){ if(x < 0) putchar('-'), putint(-x); else{ if(x > 9) putint(x / 10); putchar(x % 10 + '0'); } } inline void br(){ putchar('n'); } inline void close(){ flush(); } } typedef long long int64; const int MAXN = 100000; const int MAXM = 100000; const int MAXL = 2 * MAXN - 1; const int MAXLOGL = 18; const int MAXQ = 100000; struct Node{ struct Edge *edges; Node *fa; int candy; int id, pos, blockId, depth; bool in; } nodes[MAXN]; struct Edge{ Node *to; Edge *next; Edge() {} Edge(Node *fr, Node *to) : to(to), next(fr->edges) {} } epool[2 * (MAXN - 1)], *eptr = epool; inline void link(Node *u, Node *v){ u->edges = new (eptr++) Edge(u, v); v->edges = new (eptr++) Edge(v, u); } int n, m, q; int value[MAXM + 1], curiosity[MAXN + 1]; int64 ans[MAXM]; Node *f[MAXL][MAXLOGL + 1]; int logBase2[MAXL + 1]; int len; Node *S[MAXN]; int top; int blockCnt, blockSize; inline void dfs(Node *v, Node *fa = NULL){ static int dfsClock = 0; v->id = ++dfsClock; f[v->pos = len++][0] = v; int bot = top; for(Edge *e = v->edges; e; e = e->next) if(!e->to->depth){ e->to->depth = v->depth + 1, e->to->fa = v, dfs(e->to); if(top - bot >= blockSize){ while(top > bot) S[--top]->blockId = blockCnt; blockCnt++; } f[len++][0] = v; } S[top++] = v; } inline Node* min(Node *a, Node *b){ return a->depth < b->depth ? a : b; } inline Node* rmq(int l, int r){ int k = logBase2[r - l + 1]; return min(f[l][k], f[r - (1 << k) + 1][k]); } inline Node* queryLCA(Node *a, Node *b){ if(a->pos > b->pos) std::swap(a, b); return rmq(a->pos, b->pos); } void build(){ blockSize = int(std::ceil(std::pow(n, 2.0 / 3.0) + 1e-6)); nodes->depth = 1, nodes->fa = NULL, dfs(nodes); while(top) S[--top]->blockId = blockCnt - 1; logBase2[1] = 0; for(int i = 2; i <= len; i++) logBase2[i] = logBase2[i >> 1] + 1; for(int k = 1; k <= logBase2[len]; k++){ for(int i = 0; i < len; i++){ if(i + (1 << k - 1) < len){ f[i][k] = min(f[i][k - 1], f[i + (1 << k - 1)][k - 1]); } else{ f[i][k] = f[i][k - 1]; } } } } struct Modification{ Node *pos; int candy; } modifications[MAXQ]; struct Query{ Node *u, *v; int id, time; inline friend bool operator<(const Query &a, const Query &b){ if(a.u->blockId != b.u->blockId) return a.u->blockId < b.u->blockId; else if(a.v->blockId != b.v->blockId) return a.v->blockId < b.v->blockId; else return a.time < b.time; } } querys[MAXQ]; int mcnt, qcnt; int buc[MAXN]; int64 currAns; inline int64 contribution(int candy){ return (int64)value[candy] * curiosity[ buc[candy] ]; } inline void flip(Node *v){ v->in ^= 1; if(v->in){ ++buc[v->candy]; currAns += contribution(v->candy); } else{ currAns -= contribution(v->candy); --buc[v->candy]; } } inline void flip(Node *u, Node *v){ Node *lca = queryLCA(u, v); for(Node *p = u; p != lca; p = p->fa) flip(p); for(Node *p = v; p != lca; p = p->fa) flip(p); } inline void flipModification(int time){ Modification *o = modifications + time; bool in = o->pos->in; if(in) flip(o->pos); std::swap(o->candy, o->pos->candy); if(in) flip(o->pos); } inline void solve(){ std::sort(querys, querys + qcnt); Node *u = nodes, *v = nodes, *lca = nodes; flip(nodes); int currTime = 0; for(Query *q = querys; q != querys + qcnt; q++){ while(currTime < q->time) flipModification(currTime++); while(currTime > q->time) flipModification(--currTime); flip(lca); lca = queryLCA(q->u, q->v); flip(lca); flip(u, q->u), u = q->u; flip(v, q->v), v = q->v; ans[q->id] = currAns; } } int main(){ io::init(); io::readint(n), io::readint(m), io::readint(q); for(int i = 1; i <= m; i++) io::readint(value[i]); for(int i = 1; i <= n; i++) io::readint(curiosity[i]); for(int i = 0, u, v; i < n - 1; i++){ io::readint(u), io::readint(v), u--, v--; link(nodes + u, nodes + v); } for(Node *v = nodes; v != nodes + n; v++) io::readint(v->candy); build(); for(int i = 0; i < q; i++){ int t; io::readint(t); if(t == 1){ // Query Query *q = querys + qcnt; int u, v; io::readint(u), io::readint(v), u--, v--; q->u = nodes + u, q->v = nodes + v, q->id = qcnt, q->time = mcnt; if(q->v->id > q->u->id) std::swap(q->u, q->v); qcnt++; } else if(t == 0){ // Modification Modification *o = modifications + mcnt; int pos, candy; io::readint(pos), io::readint(candy), pos--; o->pos = nodes + pos, o->candy = candy; mcnt++; } else{ throw; } } solve(); for(int i = 0; i < qcnt; i++) io::putint(ans[i]), io::br(); io::close(); return 0; }就是这样咯~
近期评论