首页 > 代码库 > [WC2013][UOJ58]糖果公园 莫队算法
[WC2013][UOJ58]糖果公园 莫队算法
这道题有毒！！！！！！！！！！！！！！！！！！
先贴个题面吧QwQ
#58. 【WC2013】糖果公园
Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园玩。
糖果公园的结构十分奇特，它由 nn 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 11 至 nn。有 n?1n?1 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。
糖果公园所发放的糖果种类非常丰富，总共 mm 种，它们的编号依次为 11 至 mm。每一个糖果发放处都只发放某种特定的糖果，我们用 cici 来表示 ii 号游览点的糖果。
来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。
大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分，我们得到了糖果的美味指数，第 ii 种糖果的美味指数为 vivi。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 ii 次品尝某类糖果的新奇指数 wiwi，如果一位游客第 ii 次品尝第 jj 种糖果，那么他的愉悦指数 HH 将会增加对应的美味指数与新奇指数的乘积，即 vjwivjwi。这位游客游览公园的愉悦指数最终将是这些乘积的和。
当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 mm 种中的一种），这样的目的是能够让游客们总是感受到惊喜。
糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。
输入格式
第一行包含三个正整数 n,m,qn,m,q，分别表示游览点个数、糖果种类数和操作次数。
第二行包含 mm 个正整数 v1,v2,…,vmv1,v2,…,vm。
第三行包含 nn 个正整数 w1,w2,…,wnw1,w2,…,wn。
第四行到第 n+2n+2 行，每行包含两个正整数 ai,biai,bi，表示这两个游览点之间有路径可以直接到达。
第 n+3n+3 行包含 nn 个正整数 c1,c2,…,cnc1,c2,…,cn。
接下来 qq 行，每行包含三个整数 t,x,yt,x,y，表示一次操作：
若 tt 为 00，则 1≤x≤n1≤x≤n，1≤y≤m1≤y≤m，表示编号为 xx 的游览点发放的糖果类型改为 yy；
若 tt 为 11，则 1≤x,y≤n1≤x,y≤n，表示对出发点为 xx，终止点为 yy 的路线询问愉悦指数。
输出格式
按照输入的先后顺序，对于每个 tt 为 11 的操作输出一行，用一个正整数表示答案。
样例一
input
4 3 5 1 9 2 7 6 5 1 2 3 3 1 3 4 1 2 3 2 1 1 2 1 4 2 0 2 1 1 1 2 1 4 2
output
84 131 27 84
限制与约定
对于所有的数据，1≤vi,wi≤1061≤vi,wi≤106，1≤ai,bi≤n1≤ai,bi≤n，1≤ci≤m1≤ci≤m，w1,w2,…,wnw1,w2,…,wn 是非递增序列，即对任意 1<i≤n1<i≤n，满足 wi≤wi?1wi≤wi?1。
| 测试点编号 | nn | mm | 其它限制 | |
|---|---|---|---|---|
| 1 | ≤20≤20 | ≤20≤20 | ≤20≤20 | 无 |
| 2 | ≤2000≤2000 | ≤2000≤2000 | ≤2000≤2000 | |
| 3 | ≤10000≤10000 | ≤10000≤10000 | ≤10000≤10000 | |
| 4 | ≤80000≤80000 | ≤100≤100 | ≤80000≤80000 | 没有修改操作；给出的图构成一条链 |
| 5 | ≤90000≤90000 | ≤100≤100 | ≤90000≤90000 | |
| 6 | ≤80000≤80000 | ≤80000≤80000 | ≤80000≤80000 | 没有修改操作 |
| 7 | ≤90000≤90000 | ≤90000≤90000 | ≤90000≤90000 | |
| 8 | ≤80000≤80000 | ≤80000≤80000 | ≤80000≤80000 | 给出的图构成一条链 |
| 9 | ≤90000≤90000 | ≤90000≤90000 | ≤90000≤90000 | |
| 10 | ≤100000≤100000 | ≤100000≤100000 | ≤100000≤100000 | 无 |
祝大家一遍 AC，求不虐萌萌哒测评机！
时间限制：8s8s
空间限制：512MB
真的有毒。。。
还是先跳过我惨痛的回忆，讲讲这题怎么做吧
首先这题要用到待修改的莫队算法，也是我第一次接触到。
普通的莫队算法建议看下面这个：
http://blog.csdn.net/bossup/article/details/39236275
其实莫队算法就是个优美的暴力，真的很艺术，orz莫队
接下来我们要把序列上的莫队转到树上来，可以参考这个：
http://blog.csdn.net/kuribohG/article/details/41458639
最后是待修改的树上莫队，from vfk大佬：
http://vfleaking.blog.163.com/blog/static/174807634201311011201627/
(看了vfk大佬的<四色的NOI>真的好感动)(雾）
也就是说，待修改的只需要把时间作为第三关键字，同样排序后暴力的转移就好了。然而我不知道为什么块要分成n^(2/3)个。。。(明天去问学长们(*^__^*) 嘻嘻)
贴上我丑陋的代码QwQ：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<ctime> #include<queue> #include<map> #include<set> #include<vector> #define LL long long using namespace std; const int N=100010; struct edge{int to,nxt;}e[N<<1]; struct node{int x,y,z,id;}a[N],b[N]; int n,m,q,c[N],st[N],top,f[N][18],dep[N],head[N],cnt; int dfn[N],bel[N],blonum,blo,q0,q1,pre[N],tot[N]; LL v[N],w[N],Ans[N],ans; bool vis[N]; int read() {int d=0; char c=getchar(); while (c<‘0‘||c>‘9‘) c=getchar(); while (c>=‘0‘&&c<=‘9‘) d=(d<<3)+(d<<1)+c-48,c=getchar(); return d;} void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);} void addedge(int x,int y) { e[++cnt]=(edge){y,head[x]}; head[x]=cnt; e[++cnt]=(edge){x,head[y]}; head[y]=cnt; } void dfs(int u) { dfn[u]=++cnt; int cur=top; for (int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if (v==f[u][0]) continue; f[v][0]=u; dep[v]=dep[u]+1; dfs(v); if (top-cur>=blo) { blonum++; while (top>=cur) bel[st[top--]]=blonum; } } st[++top]=u; } int lca(int x,int y) { if (x==y) return x; if (dep[x]<dep[y]) swap(x,y); for (int i=17;i>=0;i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i]; if (x==y) return x; for (int i=17;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } bool cmp(node a,node b) { if (bel[a.x]==bel[b.x]&&bel[a.y]==bel[b.y]) return a.z<b.z; if (bel[a.x]==bel[b.x]) return bel[a.y]<bel[b.y]; return bel[a.x]<bel[b.x]; } void rever2(int x) { if (vis[x]) ans-=v[c[x]]*w[tot[c[x]]--],vis[x]=0; else ans+=v[c[x]]*w[++tot[c[x]]],vis[x]=1; } void rever1(int x,int y) { if (vis[x]) rever2(x),c[x]=y,rever2(x); else c[x]=y; } void work(int x,int y) { while (x!=y) if (dep[x]<dep[y]) rever2(y),y=f[y][0]; else rever2(x),x=f[x][0]; } void print(LL x){if (!x) return; print(x/10); putchar(‘0‘+x%10);} int main() { //judge(); n=read(); m=read(); q=read(); blo=pow(n,2.0/3)*0.6; for (int i=1;i<=m;i++) v[i]=read(); for (int i=1;i<=n;i++) w[i]=read(); for (int i=1;i<n;i++) addedge(read(),read()); cnt=0; dep[1]=1; dfs(1); while (top) bel[st[top--]]=blonum; for (int j=1;j<=17;j++) for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; for (int i=1;i<=n;i++) c[i]=pre[i]=read(); for (int i=1;i<=q;i++) { int op=read(),x=read(),y=read(); if (!op) b[++q0]=(node){x,y,pre[x],0},pre[x]=y; else { if (dfn[x]>dfn[y]) swap(x,y); a[++q1]=(node){x,y,q0,q1}; } } sort(a+1,a+1+q1,cmp); for (int i=1;i<=a[1].z;i++) rever1(b[i].x,b[i].y); work(a[1].x,a[1].y); int t=lca(a[1].x,a[1].y); rever2(t); Ans[a[1].id]=ans; rever2(t); for (int i=2;i<=q1;i++) { if (a[i].z>a[i-1].z) for (int j=a[i-1].z+1;j<=a[i].z;j++) rever1(b[j].x,b[j].y); if (a[i].z<a[i-1].z) for (int j=a[i-1].z;j>a[i].z;j--) rever1(b[j].x,b[j].z); work(a[i].x,a[i-1].x); work(a[i].y,a[i-1].y); t=lca(a[i].x,a[i].y); rever2(t); Ans[a[i].id]=ans; rever2(t); } for (int i=1;i<=q1;i++) if (Ans[i]==0) puts("0"); else print(Ans[i]),puts(""); return 0; }
应该看得懂吧(雾)，主要是三个子程序，rever1(x,y)是把点x的颜色修改为y，rever2(x)是"走"过点x，work(x,y)是从x"走"到y
接下来请允许我说说我惨痛的回忆
就是一直T啊，我也很无奈啊，一直不知道为什么，改了了压行，删了一些头文件，加了输优，加了inline，第6,7,10个点还是T，绝望。。。
最后看了下UOJ上AC的程序(UOJ就是好，嘻嘻)，发现他们树上分块的打法和我不一样，我原来是这样的：
int dfs(int u) { int size=0; for (int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if (v==f[u][0]) continue; f[v][0]=u; dep[v]=dep[u]+1; size+=dfs(v); if (size>=blo) { blonum++; while (top) bel[st[top--]]=blonum; size=0; } } st[++top]=u; return size+1; }
改了就A了！这是为什么呢，不知道~\(≧▽≦)/~啦啦啦，算了，明天再说。
后天一模(中考)，然而我古诗文什么的都忘光了，赶紧去背一波~
[WC2013][UOJ58]糖果公园 莫队算法