Codechef 13.2 QUERY 可持久化线段树+可持久化数据结构+标记永久化

Nov 20, 2015 04:24:04 PM

 

Tags: 可持久化线段树 可持久化数据结构 标记永久化
Posted in Something | 0 Comments

Codechef 14.3 GERALD07 LCT+可持久化线段树

Nov 20, 2015 04:15:25 PM

 

Tags: LCT 可持久化线段树
Posted in Something | 0 Comments

BZOJ3218:a + b Problem 网络流+线段树

Jan 27, 2015 09:59:33 PM

思路:

首先最小割的建模是显然的.

令\(S\)集合表示选择白色,\(T\)集合表示选择黑色.

则有:

\[S->i~c=w_i\]表示割掉这条边之后,\(i\)在\(T\)集合,颜色为黑色,失去了白色的价值.

同理\[i->T~c=b_i\].

接下来假设有一堆点,若这些点有一个为白色,且\(i\)为黑色,则损失价值\(p_i\).

这个怎么搞?

设一个辅助节点\(x\),让所有对\(i\)有影响的点\(j\)都连\(j->x~c=INF\).然后再连接\(x->i~c=p_i\).

这样的话,如果有某个点\(x\)选了白色(属于\(S\)集),而节点\(i\)为黑色(属于\(T\)集),那么这条\(p_i\)的边就必定需要割掉.

 

可是这样边数爆表.

注意到一堆\(INF\)的边很是浪费,于是我们用线段树优化.

首先不考虑标号的限制,只考虑\(l\leq{a}\leq{r}\)的限制.

离散化后,我们用线段树上的\(O(logn)\)个节点来连向辅助节点.

 

接下来是标号的限制...

我们用一颗可持久化线段树来维护连边即可.

(关于可持久化线段树的姿势可以看代码)

(内附良心样例)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 5010
int a[N],b[N],w[N],l[N],r[N],p[N];
  
int seq[N*3],id;
  
struct MaxflowSolver{
    int head[300010],next[1000010],end[1000010],flow[1000010],ind;
    int d[300010],gap[300010],cur[300010],stk[300010],top;
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){/*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[300010];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int res=0,i,Min,ins,u=S;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find){cur[u]=stk[top++]=ins,u=end[ins];}
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}SteinsGate;
  
struct Node{
    int l,r;
}S[300010];int cnt;
  
int root[5010];
int Newversion(int last,int tl,int tr,int ins){
    int q=++cnt;S[q]=S[last];if(last)SteinsGate.make(last,q,INF);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;
}
  
void Addedge(int q,int tl,int tr,int dl,int dr,int topoint){
    if(dl<=tl&&tr<=dr){if(q)SteinsGate.make(q,topoint,INF);return;}
    int mid=(tl+tr)>>1;
    if(dr<=mid)Addedge(S[q].l,tl,mid,dl,dr,topoint);
    else if(dl>mid)Addedge(S[q].r,mid+1,tr,dl,dr,topoint);
    else Addedge(S[q].l,tl,mid,dl,mid,topoint),Addedge(S[q].r,mid+1,tr,mid+1,dr,topoint);
}
  
int main(){
    int n;scanf("%d",&n);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]);
  
    for(i=1;i<=n;++i)seq[++id]=a[i],seq[++id]=l[i],seq[++id]=r[i];sort(seq+1,seq+id+1);
    map<int,int>M;int num=0;for(seq[0]=-1<<30,i=1;i<=id;++i)if(seq[i]!=seq[i-1])M[seq[i]]=++num;
    for(i=1;i<=n;++i)a[i]=M[a[i]],l[i]=M[l[i]],r[i]=M[r[i]];
  
    SteinsGate.reset();
    for(i=1;i<=n;++i)root[i]=Newversion(root[i-1],1,num,a[i]),SteinsGate.make(250000+i,cnt,INF);
    for(i=1;i<=cnt;++i){
        if(S[i].l)SteinsGate.make(S[i].l,i,INF);
        if(S[i].r)SteinsGate.make(S[i].r,i,INF);
    }
  
    int S=0,T=++cnt,res=0;
    for(i=1;i<=n;++i)res+=b[i]+w[i],SteinsGate.make(S,250000+i,w[i]),SteinsGate.make(250000+i,T,b[i]);
    for(i=1;i<=n;++i)if(i)Addedge(root[i-1],1,num,l[i],r[i],++cnt),SteinsGate.make(cnt,250000+i,p[i]);
  
    printf("%d",res-SteinsGate.Maxflow(S,T,cnt+1+n));
  
#ifndef ONLINE_JUDGE
    system("pause");
#endif
  
    return 0;
}
/*10
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
5 6 7 1 1 2*/

 

Tags: 网络流 可持久化线段树
Posted in BZOJ | 0 Comments

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

Sample Output

1/3
样例解释
可以选择的路径对有(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;
}

Tags: DFS序 可持久化线段树
Posted in BZOJ | 1 Comments