BZOJ3772精神污染&BZOJ3488&luogu3242接水果

LINK2：[ONTAK2010Highways](http://www.lydsy.com/JudgeOnline/problem.php?id=3488)

LINK3：[接水果](https://www.luogu.com.cn/problem/P3242)

三道题挺相似的也挺重要的所以写一发题解。

精神污染：随机选择两条路径求一条路径被另一条路径包含的概率。
不难发现是污染的路径对数/总路径对数。总路径对数也很显然.
最难得地方是求出左边的东西。考虑枚举一条路径求出有多少条路径被其覆盖了。
树上路径覆盖问题我们需要一个根号的算法或者log的算法。
先考虑链的情况对于当前暴力枚举的路径不妨设为x,y 对于其他路径的两个端点设为ai bi
当前路径覆盖其他路径当且仅当 ai bi都在x-y的路径上我们可以通过求LCA来表示这个东西不过过于繁琐我们还有更快的dfs序.
考虑lx下面分析接水果和刚才未完成的分类讨论。

接水果和刚才不同的是要求包含的第k大的值。

考虑二分然后我们一条一条的加进去再查询。

多组询问那就整体二分。

考虑如何快速判定一个路径到底包含了多少条路径。

可以发现这是一个上述问题的子问题。配合我们上述做法也不过nlog^2的复杂度。

不过常数巨大考虑优化一下这个做法我们维护可持久化主席树这个极其消耗时间单次可以承受但logn次就难以承受了。

一对点被另外一对点所包含设当前这对点dfs序为posx lastx posy lasty

如果x,y(d[x]>d[y])没有祖先关系我们发现另外一对点的dfs序分别出现在上述两个区间之中即可。

如果存在祖先关系那么显然 y=lca(x,y) 另外一对点的其中一个点在posx lastx中设z为y到x路径上的第一个儿子那么令一个点的范围[1,posz-1][lastz,n]
这两个区间之中可以发现我们把这种点对关系转换成区间关系这其实是一个二维数点问题我们可以扫描线+bit/线段树解决。

至于第二道题目显然也是这种类型的特此这钟类型的题目有两种做法其中第二种常用且常数较小。

可以发现我们这样做是一个二维数点问题 K-D tree也是可以查询的不过每次复杂度是$sqrt(n)$。。当然也是可以过的啦。

但是接水果这道题整体二分比较显然还是练练整体二分吧。

多此一举了一个地方导致查半天的错误。。还是思想不够缜密。这里放出代码比较难写qwq.
```
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define db double
#define INF 1000000000
#define ld long double
#define pb push_back
#define put(x) printf("%d\n",x)
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define rep(p,n,i) for(ll i=p;i
#define F first
#define S second
#define mk make_pair
#define EPS 1e-7
#define P 13331ll
#define mod 998244353
using namespace std;
char buf[1'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&chsz[son[x]])son[x]=tn;
}
las[x]=cnt;
}
inline void dp(int x,int father)
{
top[x]=father;
if(!son[x])return;
dp(son[x],father);
for(int i=lin[x];i;i=nex[i])
if(ver[i]!=fa[x]&&ver[i]!=son[x])dp(ver[i],ver[i]);
}
inline int get(int x,int y)
{
while(top[x]!=top[y])
{
if(fa[top[x]]==y)return top[x];
x=fa[top[x]];
}
return son[y];
}
inline void add1(int x,int y)
{
while(xQr)return;
if(L==R)
{
for(int i=Ql;i>1;
int flag=l;
for(int i=Ql;i=s[i].k)sl[++ql]=s[i];
else s[i].k-=w[s[i].id],sr[++qr]=s[i];
}
for(int i=Ql;i=dfn[x])
{
int zz=get(x,y);
t[++ss]=(wy){1,dfn[x],las[x]+1,z,1};
t[++ss]=(wy){dfn[zz],dfn[x],las[x]+1,z,-1};
t[++ss]=(wy){las[zz]+1,dfn[x],las[x]+1,z,1};
}
else
{
t[++ss]=(wy){dfn[y],dfn[x],las[x]+1,z,1};
t[++ss]=(wy){las[y]+1,dfn[x],las[x]+1,z,-1};
}
}
for(int i=1;isz[son[x]])son[x]=tn;
}
las[x]=cnt;
}
inline void dp(int x,int father)
{
top[x]=father;
if(!son[x])return;
dp(son[x],father);
for(int i=lin[x];i;i=nex[i])
if(ver[i]!=fa[x]&&ver[i]!=son[x])dp(ver[i],ver[i]);
}
inline int get(int x,int y)
{
while(top[x]!=top[y])
{
if(fa[top[x]]==y)return top[x];
x=fa[top[x]];
}
return son[y];
}
inline void add1(int x,int y)
{
while(x=dfn[x])
{
int z=get(x,y);
q[++s]=(wy){1,las[x],n};
q[++s]=(wy){-1,las[x],las[z]};
q[++s]=(wy){1,las[x],dfn[z]-1};
q[++s]=(wy){-1,dfn[x]-1,n};
q[++s]=(wy){1,dfn[x]-1,las[z]};
q[++s]=(wy){-1,dfn[x]-1,dfn[z]-1};
}
else
{
q[++s]=(wy){1,las[x],las[y]};
q[++s]=(wy){-1,dfn[x]-1,las[y]};
q[++s]=(wy){-1,las[x],dfn[y]-1};
q[++s]=(wy){1,dfn[x]-1,dfn[y]-1};
}
}
sort(t+1,t+1+2*m);sort(q+1,q+1+s);
int flag=1;
for(int i=1;isz[son[x]])son[x]=tn;
}
las[x]=cnt;
}
inline void dp(int x,int father)
{
top[x]=father;
if(!son[x])return;
dp(son[x],father);
for(int i=lin[x];i;i=nex[i])
if(ver[i]!=fa[x]&&ver[i]!=son[x])dp(ver[i],ver[i]);
}
inline int get(int x,int y)
{
while(top[x]!=top[y])
{
if(fa[top[x]]==y)return top[x];
x=fa[top[x]];
}
return son[y];
}
inline void add1(int x,int y)
{
while(x=dfn[x])
{
int z=get(x,y);
q[++s]=(wy){1,las[x],n,i};
q[++s]=(wy){-1,las[x],las[z],i};
q[++s]=(wy){1,las[x],dfn[z]-1,i};
q[++s]=(wy){-1,dfn[x]-1,n,i};
q[++s]=(wy){1,dfn[x]-1,las[z],i};
q[++s]=(wy){-1,dfn[x]-1,dfn[z]-1,i};
}
else
{
q[++s]=(wy){1,las[x],las[y],i};
q[++s]=(wy){-1,dfn[x]-1,las[y],i};
q[++s]=(wy){-1,las[x],dfn[y]-1,i};
q[++s]=(wy){1,dfn[x]-1,dfn[y]-1,i};
}
}
sort(t+1,t+1+2*m);sort(q+1,q+1+s);
int flag=1;
for(int i=1;i

巴特西

BZOJ3772精神污染&BZOJ3488&luogu3242接水果

最新文章

热门文章