注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

WC 2013 bzoj 3052 糖果公园  

2014-01-04 22:07:11|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
艾神的题
争取在这学期结束前尽可能的把WC的题补一些吧

其实WC没有想象中的那么难了
比起去年我的手足无措
也许我的确进步了?
可惜大家进步的更多
于是最后只有使我更悲伤

这不是兢兢业业的写题解……这只是在扯淡
题解请看http://vfleaking.blog.163.com/blog/static/174807634201311011201627/

本来一两个小时不到就写完了的
过了样例就应该要过了
我的原本做法是这样的:
建立一个长度为2n的DFS序,用来分块,然后莫队
待修改莫队处理方法:
把本来的按(l,r)二元组排序变成按(l,r,t)三元组排序,l所在块为一关键字,r所在块为而关键字,t为三关键字,分成n^(1/3)块,每块n^(2/3)个
树上莫队处理方法:
(这个处理方法是vfk的题解里讲的)现在每两个点的距离已经不大了了,所以可以用暴力LCA的形式来暴力转移。但一个问题出现了……实际写代码的时候会发现LCA非常的讨厌
看了vfk的题解……不管LCA,我们维护(a,b)路径上除了LCA的答案,要求答案的时候再log n的找到lca把他算进去就行了
于是莫名其妙地解决了那个问题

不过就结束了吗?
很happy的搞掉了,感慨自己状态不错之后WC 2013 bzoj 3052 糖果公园 - ydc - ydc的博客
 坐等明天被封号
“请大家不要恶意卡评测机”

除了第一份程序
后面都是在卡常数

最后放弃了,打算换个分块方法
于是又跑去看vfk的题解和程序

然后就没有然后了
A掉王室联邦……然后用那个方法去做
就A掉了

其实那个方法比DFS序分块优显然的
因为DFS序是2*n的那种
至于那个方法得到编号相邻块相邻……也是显然的

不管怎样还是很开心了……虽然做完之后有种怅然若失的感觉
曾经不敢触及的题目,如今到了能解决的地步,却没有任何成就感

学问无穷好比云挂山头行至山前云更远
知识难尽恰似月落水底拨开水面月尤深

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cctype>
#define each(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
#define maxn 200010
using namespace std;
typedef long long LL;
template<class T>
void Read(T &digit)
{
digit=0;
char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);digit=digit*10+c-'0',c=getchar());
}
int pos[maxn];
struct Operation
{
int a,b;
}op[maxn];
struct Query
{
int a,b,id;
LL ans;
friend bool operator < (const Query &a,const Query &b)
{
if(pos[a.a]!=pos[b.a])
return pos[a.a]<pos[b.a];
if(pos[a.b]!=pos[b.b])
return pos[a.b]<pos[b.b];
return a.id<b.id;
}
}q[maxn];
bool cmp(const Query &a,const Query &b)
{
return a.id<b.id;
}
LL ans;
bool vis[maxn];
int father[maxn],F[maxn][20];
int n,nBlock,lim,nq,cnt[maxn],dep[maxn];
int Log[maxn];
int wait[maxn],nwait;
LL val1[maxn],val2[maxn];
vector<int> adj[maxn];
vector<int>::iterator now[maxn];
int DFS(int p)
{
int sum=0;
each(i,adj[p])
if(dep[*i]==0)
{
father[*i]=p;
dep[*i]=dep[p]+1;
F[*i][0]=p;
for(int j=1;j<=18;++j)
F[*i][j]=F[F[*i][j-1]][j-1];
sum+=DFS(*i);
if(sum>=lim)
{
++nBlock;
while(sum--)
pos[wait[nwait--]]=nBlock;
sum=0;
}
}
wait[++nwait]=p;
return ++sum;
}
void read()
{
static vector<int> candy[maxn];
int c,m,nBlock;
Read(n),Read(m),Read(c);
for(int i=1;i<=m;++i)
Read(val1[i]);
for(int i=1;i<=n;++i)
Read(val2[i]);
for(int i=2,a,b;i<=n;++i)
{
Read(a),Read(b);
adj[a].push_back(b);
adj[b].push_back(a);
}
lim=(int)pow(n,2.0/3);
for(int i=1,p;i<=n;++i)
{
Read(p);
candy[i].push_back(p);
}
for(int i=1,type;i<=c;++i)
{
Read(type);
if(type==0)
{
Read(op[i].a),Read(op[i].b);
candy[op[i].a].push_back(op[i].b);
}
else
{
++nq;
Read(q[nq].a),Read(q[nq].b);
q[nq].id=i;
}
}
for(int i=1;i<=n;++i)
now[i]=candy[i].begin();
dep[1]=1;
DFS(1);
while(nwait)
pos[wait[nwait--]]=nBlock;
for(int i=2;i<=n;++i)
Log[i]=Log[i-1]+(i==(i&-i));
for(int i=1;i<=nq;++i)
if(pos[q[i].a]>pos[q[i].b])
swap(q[i].a,q[i].b);
sort(q+1,q+nq+1);
}
int LCA(int a,int b)
{
if(dep[a]<dep[b])
swap(a,b);
for(int i=Log[dep[a]];i>=0;--i)
if(dep[F[a][i]]>=dep[b])
a=F[a][i];
if(a==b)
return a;
for(int i=Log[dep[a]];i>=0;--i)
if(F[a][i]!=F[b][i])
a=F[a][i],b=F[b][i];
return father[a];
}
inline void XorPoint(int p)
{
if(vis[p])
{
int c=*now[p];
ans=ans-val1[c]*val2[cnt[c]];
--cnt[c];
vis[p]=false;
}
else
{
int c=*now[p];
++cnt[c];
ans=ans+val1[c]*val2[cnt[c]];
vis[p]=true;
}
}
void XorPath(int a,int b)
{
if(dep[a]<dep[b])
swap(a,b);
while(dep[a]!=dep[b])
XorPoint(a),a=father[a];
while(a!=b)
XorPoint(a),XorPoint(b),a=father[a],b=father[b];
}
LL solve(int a,int b)
{
int lca=LCA(a,b);
XorPoint(lca);
LL tot=ans;
XorPoint(lca);
return tot;
}
void Mo_Algorithm()
{
for(int i=1,nowa=1,nowb=1,nowt=0;i<=nq;++i)
{
while(nowt<q[i].id)
{
int p=op[++nowt].a;
if(p==0)
continue;
bool mark=vis[p];
if(mark)
XorPoint(p);
++now[p];
if(mark)
XorPoint(p);
}
while(nowt>q[i].id)
{
int p=op[nowt--].a;
if(p==0)
continue;
bool mark=vis[p];
if(mark)
XorPoint(p);
--now[p];
if(mark)
XorPoint(p);
}
XorPath(nowa,q[i].a),nowa=q[i].a;
XorPath(nowb,q[i].b),nowb=q[i].b;
q[i].ans=solve(nowa,nowb);
}
}
void print()
{
sort(q+1,q+nq+1,cmp);
for(int i=1;i<=nq;++i)
printf("%lld\n",q[i].ans);
}
int main()
{
read();
Mo_Algorithm();
print();
return 0;
}


  评论这张
 
阅读(1042)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017