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<=ry为该路径的dfs序 af<=bf为其他路径的dfs序那么显然有 lx<=af<=bf<=rx即可。对于更一般的情况显然有一条路径被另外一条路径覆盖当且仅当该路径的两个端点都在另外一条路径上。自证不难。对于树呢？我们还考虑高处来dfs序然后只需要利用dfs序来表示出上述结论。这需要仔细的进行分类讨论。。很复杂这里我先介绍一种比较简单的数点方式: 我们发现对于一个端点x存在一个y的端点那么首先第一个要求就是x被包含于我们要查询链 xx,lca,yy xx~lca 或者 yy~lca之间这个可以利用dfs序来做考虑y 也应该在这两个之间这类似于二维偏序。不过我们可以利用对dfs序列的可持久化降维然后线段树中再装一个序列这样我们的复杂度就做到logn了。

下面分析接水果和刚才未完成的分类讨论。

接水果和刚才不同的是要求包含的第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 ",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<=n;++i) #define pii pair #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<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=40010; int n,m,Q,maxx,cnt,ss,len; int dfn[MAXN],las[MAXN],d[MAXN],son[MAXN],sz[MAXN],c[MAXN],w[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],top[MAXN],fa[MAXN],ans[MAXN]; struct wy { int x,l,r; int v,op; int friend operator <(wy a,wy b){return a.xsz[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<=n) { c[x]+=y; x+=x&(-x); } } inline int ask(int x) { int cnt=0; while(x) { cnt+=c[x]; x-=x&(-x); } return cnt; } inline void solve(int Ql,int Qr,int l,int r,int L,int R) { if(Ql>Qr)return; if(L==R) { for(int i=Ql;i<=Qr;++i)ans[s[i].id]=L; return; } int ql=0,qr=0,ll=0,rr=0; int mid=(L+R)>>1; int flag=l; for(int i=Ql;i<=Qr;++i) { while(flag<=r&&t[flag].x<=s[i].x) { if(t[flag].v<=mid) { tl[++ll]=t[flag]; add1(t[flag].l,t[flag].op); add1(t[flag].r,-t[flag].op); } else tr[++rr]=t[flag]; ++flag; } w[s[i].id]+=ask(s[i].y); } for(int i=Ql;i<=Qr;++i) { if(w[s[i].id]>=s[i].k)sl[++ql]=s[i]; else s[i].k-=w[s[i].id],sr[++qr]=s[i]; } for(int i=Ql;i<=Qr;++i)w[s[i].id]=0; for(int i=1;i<=ll;++i) { add1(tl[i].l,-tl[i].op); add1(tl[i].r,tl[i].op); } for(int i=flag+1;i<=r;++i) if(t[i].v<=mid)tl[++ll]=t[i]; else tr[++rr]=t[i]; for(int i=1;i<=ql;++i)s[Ql+i-1]=sl[i]; for(int i=1;i<=qr;++i)s[Ql+ql-1+i]=sr[i]; for(int i=1;i<=ll;++i)t[l+i-1]=tl[i]; for(int i=1;i<=rr;++i)t[l+ll-1+i]=tr[i]; solve(Ql,Ql+ql-1,l,l+ll-1,L,mid); solve(Ql+ql,Qr,l+ll,r,mid+1,R); } int main() { freopen("1.in","r",stdin); n=read();m=read();Q=read(); for(int i=1;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;i<=Q;++i) { int x,y,z; x=read();y=read();z=read(); s[i]=(jl){dfn[x],dfn[y],i,z}; s[i+Q]=(jl){dfn[y],dfn[x],i,z}; } sort(s+1,s+1+Q*2,cmp);sort(t+1,t+1+ss); solve(1,Q*2,1,ss,1,maxx); for(int i=1;i<=Q;++i)printf("%d ",ans[i]); return 0; } ``` update:这个代码中的get写错了都A了...神奇数据...应该return top[x]而并非x写错了。。精神污染代码： ``` const int MAXN=100010; int n,m,len,cnt,s;ll ans; int dfn[MAXN],las[MAXN],d[MAXN],son[MAXN],sz[MAXN],c[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],top[MAXN],fa[MAXN]; struct wy { int op;//属性 int x,y;//横坐标纵坐标. int friend operator <(wy a,wy b){return a.xsz[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<=n) { c[x]+=y; x+=x&(-x); } } inline int ask(int x) { int cnt=0; while(x) { cnt+=c[x]; x-=x&(-x); } return cnt; } inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} int main() { freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i=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;i<=s;++i) { while(flag<=2*m&&t[flag].x<=q[i].x)add1(t[flag].y,1),++flag; ans=ans+q[i].op*ask(q[i].y); } ans-=m; if(!ans){printf("%lld/%lld ",ans,(ll)m*(m-1)/2);return 0;} ll d=gcd(ans,(ll)m*(m-1)/2); printf("%lld/%lld ",ans/d,(ll)m*(m-1)/2/d); return 0; } ``` Hignways代码注意数组的大小因为这个T了几次.. ``` const int MAXN=100010,maxn=500010; int n,m,len,cnt,s,Q; int dfn[MAXN],las[MAXN],d[MAXN],son[MAXN],sz[MAXN],c[MAXN]; int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],top[MAXN],fa[MAXN],ans[maxn]; struct wy { int op;//属性 int x,y;//横坐标纵坐标. int id; int friend operator <(wy a,wy b){return a.xsz[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<=n) { c[x]+=y; x+=x&(-x); } } inline int ask(int x) { int cnt=0; while(x) { cnt+=c[x]; x-=x&(-x); } return cnt; } int main() { freopen("1.in","r",stdin); n=read(); for(int i=1;i=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<=s;++i) { while(flag<=2*m&&t[flag].x<=q[i].x)add1(t[flag].y,1),++flag; ans[q[i].id]+=q[i].op*ask(q[i].y); } for(int i=1;i<=Q;++i)printf("%d ",ans[i]+1); return 0; } ```