2018年12月21日 – Smokey_Days

一道匈牙利算法的模板题。
对于一张二分图$G$（也就是没有奇环的图），我们定义它的「匹配」为一个图$G'(V’,E’)$，使得：
$$\forall V” \in V’,V”_{u}\in E’,V”_{v}\in E’,|E’|=2|V’|$$
我们称一个匹配是最大匹配，当且仅当它是一个边数最多的匹配。

匈牙利算法是用于求解最大匹配的一类问题。
匈牙利算法使用了一种被称为「增广」的操作。
我们首先定义一条增广路径指的是一张二分图上的路径，使得这条路径的起点和终点都是尚未匹配的点，并且它的路径上经过的所有点都是已经匹配过的点。
那么很容易可以发现，一条增广路径上的边必然是「一条已匹配一条未匹配」的。
于是，我们对增广路径上的所有边的匹配状态取反，就可以增加匹配数量的大小。
增广操作是指，对于一个点，尝试访问它的每一个相邻点，然后从这个相邻点找下去，直到能找到一条增广路径为止。然后将这条增广路径上所有边匹配状态取反。
故而，每一次新加入一个点，我们尝试一次增广。这样就能够找到最大匹配了。

#include<iostream>
#include<cstdio>

int mp[1005][1005];
bool vis[1005];
int n,m,q,usd[1005];
inline bool dfs(int X){
	for(int i=1;i<=m;++i){
		if(!mp[X][i]){
			continue;
		}
		if(!vis[i]){
			vis[i]=1;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	
	return 0;
}
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=mp[j][i]=0;
			usd[i]=usd[j]=0;
		}
	}
	int u,v;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&u,&v);
		if(u>n||v>m){
			continue;
		}
		++mp[u][v];
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		ans+=dfs(i);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

Splay裸题。
具体来说，维护两个延迟标记，翻转标记和改变标记。然后对于每一个标记考虑下传。
对于两种询问各自更新区间和与区间最大子段和。
一个区间的最大子段和有可能有三种情况：左子区间的最大子段和，右子区间的最大子段和，以及跨过两个区间的子段和。
故而我们对每个区间关于子段和维护三个信息，左起最大子段和、右起最大子段和以及总最大子段和。
而对于左起最大子段和的更新，则考虑两种情况：左子区间的最大子段和，以及整个左子区间加上根节点再加上右子区间的左起最大子段和。
右起同理。

注意：

1.updt时应当先updt(tr[X].sn[D^1])再updt(X)
2.添加节点和各种修改之后应当科学地rnw
3.添加节点时应当注意是从posi~posi+1之间的区间。
4.一个节点被删除以后，rnw它的父亲是没有意义的，应当从根开始rnw
5.内存回收机制中，添加入栈应当是++tp,出栈应当是tp–
6.考虑updt和pshd的方式：对于每一次pshd，我们应该统一修改它的子节点的标记，并对它的子节点计算贡献，然后取消它本身的标记；打标记的时候对它本身计算好贡献。
换句话说，不要在统计一个节点的贡献之前，updt它的父亲。
7.加入节点应当加入成一棵二叉树，而不是一条链。根据我根本不懂的势能分析法，加入一棵二叉树带来的势能改变是常数乘大小级的，而一条链则是对数乘大小级的。
8.对于MAX-SUM操作，必须要至少选中一个节点，所以应当额外维护一个最大值。

#include<iostream>
#include<cstdio>
#define R register
#define MAGIC 19260817
#define MID ((L+R_R)>>1)
/*

*/
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Chck(int X){
    return X>0?X:0;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
//表示特殊状态 
class Splay{
    private:
        class Node{
            public:
    			int fa;
    			int sn[2];
    			int sz;
    			int sm;
    			int lmxsm;
    			int rmxsm;
    			int mxsm;
    			int mx;
    			int v;
    			int lzy_flp;
    			int lzy_chng;
    			inline void set(int FA,int V){
    			    fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);
    			    sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;
                }
                inline void init(){
                    fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;
                    mxsm=mx=-MAGIC;
                    lzy_chng=MAGIC;
                }
        };
        Node tr[500005];
        int st[500005],tp,cnt,rt;
        inline int fndD(int X){
            return tr[tr[X].fa].sn[0]==X?0:1;
        }
        inline void chng(int X){
            tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);
            tr[X].v=tr[X].mx=tr[X].lzy_chng;
        }
        inline void flp(int X){
            Swap(tr[X].sn[0],tr[X].sn[1]);
            Swap(tr[X].lmxsm,tr[X].rmxsm);
        }
        inline void pshd(int X){
            if(!X){
                return;
            }
            if(tr[X].lzy_chng!=MAGIC){
            	tr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;
                chng(tr[X].sn[0]),chng(tr[X].sn[1]);
                tr[X].lzy_chng=MAGIC;
            }
            if(tr[X].lzy_flp){
            	tr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;
                flp(tr[X].sn[0]),flp(tr[X].sn[1]);
                tr[X].lzy_flp=0;
            }
        }
        inline void updt(int X){
            if(!X){
                return;
            }
            tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;
            tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);
            tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
            tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);
            tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);
            tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);
        }
        inline void splayOne(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
            tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
            tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;
            updt(tr[X].sn[D^1]),updt(X);
        }
        inline void splayTwo(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
        }
        inline void splayRnw(int X){
            if(!X){
                return;
            }
            //printf("%d->",X);
            while(tr[X].fa){
                splayTwo(X);
                //printf("[%d,%d,%d[%d,%d](%d)] ",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));
            }
            //puts("");
            rt=X;
        }
        //注意，权值splay中的fnd函数实质上求的是排名为K的节点。 
        inline int fnd(int K){
            R int P=rt,FP=0;
            while(P){
                pshd(P);
                FP=P;
                if(tr[tr[P].sn[0]].sz+1<K){
                    K-=(tr[tr[P].sn[0]].sz+1);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<K){
                    return P;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return FP;
        }
        inline int nwlc(int FA,int D,int V){
            if(!cnt){
                rt=1;
            }
            int P=tp?st[tp--]:++cnt;
            tr[FA].sn[D]=P;
            tr[P].set(FA,V);
            return P;
        }
        inline int preSplay(int L,int LEN){
            int __L__=fnd(L),__R__=fnd(L+LEN+1);
            splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);
            splayRnw(__L__);
            splayRnw(__R__);
            //printf("%d,%d,%d\n",rt,tr[rt].sn[0],tr[rt].sn[1]);
            if(tr[__L__].fa!=__R__&&__L__!=__R__){
                splayOne(__L__);
            }
            pshd(tr[tr[rt].sn[0]].sn[1]);
            return tr[rt].sn[0];
        }
        inline void rmv(int X){
            if(!X){
                return;
            }
            rmv(tr[X].sn[0]);
            rmv(tr[X].sn[1]);
            tr[tr[X].fa].sn[fndD(X)]=0;
            tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;
            st[++tp]=X;
        }
        inline void prnt(int X, int dep=0){
            if(!X){
                return;
            }
            //pshd(X);
            prnt(tr[X].sn[0], dep+1);
            //printf("{%d}[%d](%d,%d)[%d][%d,%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);
            for(int i = 1; i <= dep; ++i) printf("口");
        	//printf("ID:%d    VAL:%d    SM:%d   CHANGE_TAG:%d \n",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);
        	printf("%d %d\n",tr[X].v,tr[X].mxsm);
            prnt(tr[X].sn[1], dep+1);
        }
        inline void build(int L,int R_R,int *IN,int D,int FA){
        	if(L>R_R){
        		return;
			}
        	int P=nwlc(FA,D,IN[MID]);
        	build(L,MID-1,IN,0,P);
        	build(MID+1,R_R,IN,1,P);
        	updt(P);
		}
    public:
        inline void INSERT(int L,int TOT,int *IN){
            int X=preSplay(L+1,0);
            build(1,TOT,IN,1,X);
            updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);
       }
        inline void DELETE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            rmv(X);
            updt(tr[rt].sn[0]),updt(rt);
        }
        inline void MAKE_SAME(int L,int LEN,int V){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_chng=V;
            chng(X);
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void REVERSE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_flp^=1;
            if(tr[X].lzy_flp){
            	flp(X);
            }
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void GET_SUM(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            printf("%d\n",tr[X].sm);
        }
        inline void MAX_SUM(){
            printf("%d\n",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);
        }
        inline void INIT(int N,int *IN){
            tr[0].init();
            rt=tp=cnt=0;
            int X=0;
            for(int i=1;i<=N;++i){
                X=nwlc(X,1,IN[i]);
            }
            nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);
            splayRnw(N+1),splayRnw(N+2);
        }
        inline void PRINT(){
            printf("%d ->\n",rt);
            prnt(rt);
            puts("");
        }
};
int n,m;
int a[4000005];
Splay T;
void init(){
    scanf("%d%d",&n,&m);
    int posi,tot,c;
    char op[10];
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    T.INIT(n,a);
    for(int i=1;i<=m;++i){
        std::cin>>op;
        switch(op[2]){
            case 'S':{
                scanf("%d%d",&posi,&tot);
                for(int j=1;j<=tot;++j){
                    scanf("%d",a+j);
                }
                T.INSERT(posi,tot,a);
                break;
            }
            case 'L':{
                scanf("%d%d",&posi,&tot);
                T.DELETE(posi,tot);
                break;
            }
            case 'K':{
                scanf("%d%d%d",&posi,&tot,&c);
                T.MAKE_SAME(posi,tot,c);
                break;
            }
            case 'V':{
                scanf("%d%d",&posi,&tot);
                T.REVERSE(posi,tot);
                break;
            }
            case 'T':{
                scanf("%d%d",&posi,&tot);
                T.GET_SUM(posi,tot);
                break;
            }
            case 'X':{
                T.MAX_SUM();
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}

一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

每日归档： 2018年12月21日

lp3386 二分图最大匹配

lp2042 NOI2005 维护数列