BZOJ3772:精神污染 dfs序+可持久化线段树
Jan 25, 2015 11:42:12 PM
以后决定土豪题都粘一下题面吧.
【begin
Description
兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。
Input
第一行两个整数N,M
接下来N-1行，每行两个数a,b，表示A和B之间有一条观光道。
接下来M行，每行两个数x,y，表示一条旅游线路。
Output
所求的概率，以最简分数形式输出。
Sample Input
5 3
1 2
2 3
3 4
2 5
3 5
2 5
1 4
1 2
2 3
3 4
2 5
3 5
2 5
1 4
Sample Output
1/3
样例解释
可以选择的路径对有(1,2),(1,3),(2,3)，只有路径1完全覆盖路径2。
样例解释
可以选择的路径对有(1,2),(1,3),(2,3)，只有路径1完全覆盖路径2。
HINT
100%的数据满足：N,M<=100000
end】
思路:
分类讨论几种完全覆盖的情形,然后用离线+dfs序+可持久化线段树水过.时间复杂度\(O(mlogn)\).
真的想写的话自己看代码.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
namespace Fio{
inline int getc(){
static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return*S++;
}
inline bool digit(int x){return x>='0'&&x<='9';}
template<typename T>inline void Get(T&x){
int c;while(!digit(c=getc()));x=c-'0';while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
}
}
#define N 100010
int n,m;
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
int pa[N][17],dep[N],in[N],out[N],tclock;
void dfs(int x,int fa){
in[x]=++tclock;
for(int j=head[x];j;j=next[j])if(end[j]!=fa){pa[end[j]][0]=x,dep[end[j]]=dep[x]+1,dfs(end[j],x);}
out[x]=tclock;
}
inline int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=16;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
if(x==y)return x;
for(int i=16;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
#define M 100010
int x[M],y[M],Lca[M];
vector<int>v[N];
int root[N<<1];
struct SegmentTree{
struct Node{
int l,r,siz;
}S[3000000];
int cnt;
inline void reset(){cnt=0;}
inline int newnode(){int q=++cnt;S[q].l=S[q].r=S[q].siz=0;return q;}
int Newversion(int Last,int tl,int tr,int ins){
int q=newnode();S[q]=S[Last],++S[q].siz;if(tl==tr)return q;
int mid=(tl+tr)>>1;
if(ins<=mid)S[q].l=Newversion(S[Last].l,tl,mid,ins);else S[q].r=Newversion(S[Last].r,mid+1,tr,ins);
return q;
}
inline int Query(int q,int tl,int tr,int dl,int dr){
if(dl>dr)return 0;
if(dl<=tl&&tr<=dr){return S[q].siz;}
int mid=(tl+tr)>>1;
if(dr<=mid)return Query(S[q].l,tl,mid,dl,dr);
else if(dl>mid)return Query(S[q].r,mid+1,tr,dl,dr);
else return Query(S[q].l,tl,mid,dl,mid)+Query(S[q].r,mid+1,tr,mid+1,dr);
}
}Seg;
struct Path{
int x,y;
Path(){}
Path(int _x,int _y):x(_x),y(_y){}
}sav[M<<1];
inline bool cmp1(const Path&A,const Path&B){return in[A.x]<in[B.x];}
inline bool cmp2(const Path&A,const Path&B){return in[A.y]<in[B.y];}
int seq[M<<1];
long long res;
void calcstep1(){
register int i;int lans,rans,L,R,mid;
for(int Root=1;Root<=n;++Root){
int num=(int)v[Root].size();if(!num)continue;
for(i=1;i<=num;++i){sav[i]=Path(x[v[Root][i-1]],y[v[Root][i-1]]);if(in[sav[i].x]>in[sav[i].y])swap(sav[i].x,sav[i].y);}
sort(sav+1,sav+num+1,cmp1);
Seg.reset();
for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].y]);
for(i=1;i<=num;++i)seq[i]=in[sav[i].x];
for(i=1;i<=num;++i){
if(in[sav[i].x]>seq[num]||out[sav[i].x]<seq[1])continue;
for(L=1,R=num;L<R;){
mid=(L+R)>>1;
if(seq[mid]>=in[sav[i].x])R=mid;else L=mid+1;
}lans=L;
for(L=1,R=num;L<R;){
mid=(L+R+1)>>1;
if(seq[mid]>out[sav[i].x])R=mid-1;else L=mid;
}rans=L;
res+=Seg.Query(root[rans],1,n,in[sav[i].y],out[sav[i].y])-Seg.Query(root[lans-1],1,n,in[sav[i].y],out[sav[i].y])-1;
}
}
}
void calcstep2(){
register int i;int lans,rans,L,R,mid,num=0;
for(i=1;i<=m;++i){
if(x[i]==Lca[i]||y[i]==Lca[i]){sav[++num]=Path(x[i],y[i]);if(in[sav[num].x]>in[sav[num].y])swap(sav[num].x,sav[num].y);}
}
sort(sav+1,sav+num+1,cmp2);
Seg.reset();
for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
for(i=1;i<=num;++i){
if(in[sav[i].y]>seq[num]||out[sav[i].y]<seq[1])continue;
for(L=1,R=num;L<R;){
mid=(L+R)>>1;
if(seq[mid]>=in[sav[i].y])R=mid;else L=mid+1;
}lans=L;
for(L=1,R=num;L<R;){
mid=(L+R+1)>>1;
if(seq[mid]>out[sav[i].y])R=mid-1;else L=mid;
}rans=L;
res+=Seg.Query(root[rans],1,n,1,in[sav[i].x])+Seg.Query(root[rans],1,n,out[sav[i].x]+1,n);
res-=Seg.Query(root[lans-1],1,n,1,in[sav[i].x])+Seg.Query(root[lans-1],1,n,out[sav[i].x]+1,n);
res--;
}
}
void calcstep3(){
register int i;int lans,rans,L,R,mid,num=0;
for(i=1;i<=m;++i)if(x[i]!=Lca[i]&&y[i]!=Lca[i])sav[++num]=Path(Lca[i],x[i]),sav[++num]=Path(Lca[i],y[i]);
sort(sav+1,sav+num+1,cmp2);
Seg.reset();
for(i=1;i<=num;++i)root[i]=Seg.Newversion(root[i-1],1,n,in[sav[i].x]);
for(i=1;i<=num;++i)seq[i]=in[sav[i].y];
for(i=1;i<=m;++i){
if(x[i]!=Lca[i]&&y[i]!=Lca[i])continue;
if(in[x[i]]>in[y[i]])swap(x[i],y[i]);
if(in[y[i]]>seq[num]||out[y[i]]<seq[1])continue;
for(L=1,R=num;L<R;){
mid=(L+R)>>1;
if(seq[mid]>=in[y[i]])R=mid;else L=mid+1;
}lans=L;
for(L=1,R=num;L<R;){
mid=(L+R+1)>>1;
if(seq[mid]>out[y[i]])R=mid-1;else L=mid;
}rans=L;
res+=Seg.Query(root[rans],1,n,1,in[x[i]])+Seg.Query(root[rans],1,n,out[x[i]]+1,n);
res-=Seg.Query(root[lans-1],1,n,1,in[x[i]])+Seg.Query(root[lans-1],1,n,out[x[i]]+1,n);
if(x[i]==y[i])res-=(int)v[x[i]].size();
}
}
long long gcd(long long a,long long b){return(!b)?a:gcd(b,a%b);}
int main(){
Fio::Get(n),Fio::Get(m);register int i,j;int a,b;
for(i=1;i<n;++i){
Fio::Get(a),Fio::Get(b);make(a,b);
}
dep[1]=1,dfs(1,-1);for(j=1;j<=16;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
for(i=1;i<=m;++i){
Fio::Get(x[i]),Fio::Get(y[i]),Lca[i]=lca(x[i],y[i]);
if(Lca[i]!=x[i]&&Lca[i]!=y[i])v[Lca[i]].push_back(i);
}
calcstep1();
calcstep2();
calcstep3();
if(res==0)puts("0/1");
else{
long long total=(long long)m*(m-1)/2;
long long Gcd=gcd(res,total);res/=Gcd,total/=Gcd;
printf("%lld/%lld",res,total);
}
return 0;
}
BZOJ3277:串 后缀自动机+离线处理+树状数组(&&BZOJ3473)
Jan 14, 2015 07:41:41 PM
思路:
水题一道.
首先建立广义后缀树.
然后利用离线+树状数组搞出每一个节点在多少个串中.
然后如果这个节点在不少于\(k\)个串中,我们令这个结点的权值为这个节点父亲边的字符个数,否则为0.
随后我们预处理一下从根到每个节点路径上的权值和.
于是每个字符串的答案等于所有这个字符串的后缀节点的从根到该节点的权值和.
时间复杂度\(O(nlogn)\).
(貌似比一些后缀数组的神方法要好多了QoQ)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int tranc[N<<1][26],len[N<<1],pa[N<<1],cnt,root,last;
inline int newnode(int l){len[++cnt]=l;return cnt;}
struct Graph{
int head[N<<1],next[N<<1],end[N<<1],ind;
inline void addedge(int a,int b){int q=++ind;end[q]=b,next[q]=head[a],head[a]=q;}
}w,g,sav;
char s[N];
int seq[N<<1],in[N<<1],out[N<<1],tclock;
inline void dfs(int x){
in[x]=++tclock,seq[tclock]=x;
for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
out[x]=tclock;
}
struct Ask{
int lab,l,r;
Ask(){}
Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
bool operator<(const Ask&B)const{return r<B.r;}
}S[N<<1];
int ans[N<<1],lastins[N];
int A[N<<1];
inline void mdf(int x,int add){
for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
int v[N<<1];
void dfs2(int x){
v[x]+=v[pa[x]];
for(int j=g.head[x];j;j=g.next[j])dfs2(g.end[j]);
}
void get(int x){
for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");
}
int main(){
int n,lim;scanf("%d%d",&n,&lim);
register int i,j,k;int y;int p,np,q,nq,rep,tmp;
for(root=newnode(0),i=1;i<=n;++i){
scanf("%s",s);int l=strlen(s);
for(last=root,j=l-1;j>=0;--j){
if((p=tranc[last][y=s[j]-'a'])!=0){
if(len[p]==len[last]+1)last=p;
else{
rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
memcpy(tranc[rep],tranc[p],sizeof tranc[p]);
for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
last=rep;
}
}
else{
np=newnode(len[last]+1);
for(p=last;p&&!tranc[p][y];p=pa[p])tranc[p][y]=np;
if(!p)pa[np]=root;
else{
q=tranc[p][y];
if(len[q]==len[p]+1)pa[np]=q;
else{
nq=newnode(len[p]+1),pa[nq]=pa[q],pa[np]=pa[q]=nq;
memcpy(tranc[nq],tranc[q],sizeof tranc[q]);
for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
}
}last=np;
}
w.addedge(last,i);
sav.addedge(i,last);
}
}
for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
dfs(1);
for(i=1;i<=cnt;++i)S[i]=Ask(i,in[i],out[i]);sort(S+1,S+cnt+1);
for(k=i=1;i<=cnt;++i){
for(j=w.head[seq[i]];j;j=w.next[j]){
if(lastins[w.end[j]])mdf(lastins[w.end[j]],-1);mdf(lastins[w.end[j]]=i,1);
}
for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
}
for(i=1;i<=cnt;++i)v[i]=ans[i]>=lim?len[i]-len[pa[i]]:0;
dfs2(1);
long long nowans;
for(i=1;i<=n;++i){
if(i>1)putchar(' ');
for(nowans=0,j=sav.head[i];j;j=sav.next[j])nowans+=v[sav.end[j]];
printf("%lld",nowans);
}
return 0;
}
BZOJ2780:[Spoj]8093 Sevenk Love Oimaster 后缀自动机+离线+dfs序+树状数组
Jan 14, 2015 02:42:05 PM
思路:
首先建立多串后缀自动机(别问我怎么建的)
然后对于每个询问串在自动机上走,记录下走到的节点.那么在几个串中出现等价于逆序后缀树的子树中有几个原串的后缀.
转化为dfs序之后,这等价于每次询问一段区间有几种不同的数.
经典模型,离线+树状数组水.
(我TTMD坑了QoQ)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n,m;
struct Graph{
int head[200010],next[200010],end[200010],ind;
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
}w,g;
int len[200010],deg[200010],pa[200010],cnt,root,last;
map<int,int>tranc[200010];
int newnode(int l){
len[++cnt]=l;return cnt;
}
char s[360010];
int in[200010],out[200010],seq[200010],tclock;
inline void dfs(int x){
in[x]=++tclock;seq[tclock]=x;
for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
out[x]=tclock;
}
int pre[10010];
struct Ask{
int lab,l,r;
Ask(){}
Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
bool operator<(const Ask&B)const{return r<B.r;}
}S[60010];
int A[200010];
inline void mdf(int x,int add){
for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
int lastins[10010];
int ans[60010];
void get(int x){for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");}
int main(){
scanf("%d%d",&n,&m);
register int i,j,k;int l,y,p,np,q,nq,rep,tmp;
for(root=newnode(0),i=1;i<=n;++i){
scanf("%s",s);l=strlen(s);
for(last=root,j=0;j<l;++j){
if((p=tranc[last][y=s[j]])!=0){
if(len[p]==len[last]+1)last=p;
else{
rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
tranc[rep]=tranc[p];
for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
last=rep;
}
}
else{
np=newnode(len[last]+1);
for(p=last;p&&!tranc[p][y];p=pa[p])tranc[p][y]=np;
if(!p)pa[np]=root;
else{
q=tranc[p][y];
if(len[q]==len[p]+1)pa[np]=q;
else{
nq=newnode(len[p]+1),pa[nq]=pa[q],pa[np]=pa[q]=nq;
tranc[nq]=tranc[q];
for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
}
}last=np;
}
w.addedge(last,i);
}
}
for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
dfs(1);
bool find;
for(i=1;i<=m;++i){
scanf("%s",s);l=strlen(s);find=1;
for(p=root,j=0;j<l;++j){
y=s[j];if(!tranc[p][y]){find=0;break;}p=tranc[p][y];
}
if(find)S[i]=Ask(i,in[p],out[p]);else S[i]=Ask(i,-1,-1);
}sort(S+1,S+m+1);
int noww;k=1;while(k<=m&&S[k].l==-1)++k;
for(i=1;i<=cnt;++i){
for(j=w.head[seq[i]];j;j=w.next[j]){
noww=w.end[j];
mdf(i,1);if(lastins[noww])mdf(lastins[noww],-1);lastins[noww]=i;
}
for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
}
for(i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}