1.12

作者: Hiyoiria | 来源:发表于2018-01-12 23:44 被阅读0次

Go 1.12 版本新特性
李云峰吃鼻屎记录表
7.0周检视第十四周（01.12-01.18）
Docker 1.12.0 Swarm
报错 | Tensorflow 安装踩坑记
远程更新
三摩地1.12-1.14
如果 Docker 升级或者重启的话，那容器是不是都会被停掉然后
树莓派docker swarm集群部署 portainer 管理
Docker Swarm 入门一篇文章就够了

从今天开始还是要养回写总结的习惯
转了一圈似乎还是简书又漂亮又能用
~~那些markdown都不能用的怕是要出事咧~~

好的今天是效率超低的一天

总共就写了两题…?如果长跑两种写法的话算三题吧

首先是思路总结
水管局长这种删边题一看就知道要倒序转加边
然后我们考虑它是要求一个图上两点间最大点权最小的路径
那么肯定就转去了最小生成树
那么就类似二分图那题我们用lct来维护这棵生成树(注意题目中保证任意时刻图都联通)
如果加进来这条边会成环就查询一下看到底有没有必要加
注意这里因为是边权lct且需要换根等操作
处理方法是把每条边都变成一个新点(++tot) 然后可以记录一下它所对应的两端节点与它的权值这样每次删边也就转为了断点
还有注意一下就是up的时候mx是要根据w进行判断的也就是应当保存编号而不是值

代码

#include<bits/stdc++.h>
#define N 3000000
#define rg register
using namespace std;
inline int gi(){
    int w=0,q=0; char c=getchar();
    while((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if(c=='-') q=1,c=getchar();
    while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}
map < int,int > vis[N],mp[N];
int n,m,Q,tot,tp;
int l[N],r[N],rev[N],ch[N][2],fa[N],fat[N],st[N],w[N],mx[N],ans[N];
struct data { int x,y,z; }q[N],lk[N];
inline bool cmp(data a,data b) { return a.z<b.z; }
inline bool ir(int x) { return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; }
inline void up(int x) {
    if (!x) return ; mx[x]=x;
    int L=ch[x][0],R=ch[x][1],&v=mx[x];
    if (L&&w[mx[L]]>w[v]) v=mx[L];
    if (R&&w[mx[R]]>w[v]) v=mx[R];
}
inline void pd(int x) {
    if (x*rev[x]==0) return ;
    swap(ch[x][0],ch[x][1]),rev[x]=0;
    if (ch[x][0]) rev[ch[x][0]]^=1;
    if (ch[x][1]) rev[ch[x][1]]^=1;
} 
inline void rot(int x){
    int p=fa[x],q=fa[p],l=ch[p][1]==x,r=l^1;
    if (!ir(p)) ch[q][ch[q][1]==p]=x;
    fa[x]=q,fa[p]=x;
    fa[ch[x][r]]=p,ch[p][l]=ch[x][r],ch[x][r]=p;
    up(p),up(x);
}
inline void splay(int x){
    st[tp=1]=x;
    for (int i=x;!ir(i);i=fa[i]) st[++tp]=fa[i];
    while (tp) pd(st[tp--]);
    while (!ir(x)){
        int p=fa[x],q=fa[p];
        if (!ir(p)){
            if ((ch[p][0]==x)^(ch[q][0]==p)) rot(x);
            else rot(p);
        } rot(x);
    }
}
inline void access(int x) { for (int la=0;x;x=fa[x]) splay(x),ch[x][1]=la,up(x),la=x; }
inline void mtr(int x) { access(x),splay(x),rev[x]^=1; }
inline void link(int x,int y) { mtr(x),fa[x]=y,splay(y); }
inline void cut(int x,int y) { mtr(x),access(y),splay(y),ch[y][0]=fa[x]=0; }
inline int find(int x) { return fat[x]==x?fat[x]:fat[x]=find(fat[x]); }
inline int query(int x,int y) { mtr(x),access(y),splay(y); return mx[y]; }
inline void add(int x,int y,int z){
    int f1=find(x),f2=find(y);
    if (f1==f2){
        int t=query(x,y);
        if (z>=w[t]) return ;
        cut(l[t],t),cut(t,r[t]);
    }
    fat[f1]=f2,w[++tot]=z;
    l[tot]=x,r[tot]=y,link(x,tot),link(tot,y);  
}
int main(){
    freopen ("tube_strong.in","r",stdin);
    freopen ("tube_strong.out","w",stdout);
    n=gi(),m=gi(),Q=gi();
    memset(w,0,sizeof(w));
    for (int i=1;i<=n;++i) fat[i]=i;
    int x,y,z; tot=n;
    for (int i=1;i<=m;++i) x=gi(),y=gi(),z=gi(),lk[i]=(data){x,y,z},mp[x][y]=mp[y][x]=z;
    for (int i=1;i<=Q;++i){
        x=gi(),y=gi(),z=gi(),q[i]=(data){x,y,z};
        if (x==2) vis[y][z]=vis[z][y]=1;//!!
    }
    sort(lk+1,lk+m+1,cmp);
    for (int i=1;i<=m;++i) if (!vis[lk[i].x][lk[i].y]) add(lk[i].x,lk[i].y,lk[i].z);
    for (int i=Q;i;--i){
        if (q[i].x==1) ans[i]=w[query(q[i].y,q[i].z)];
        else add(q[i].y,q[i].z,mp[q[i].y][q[i].z]);
    }
    for (int i=1;i<=Q;++i) if (q[i].x==1) printf ("%d\n",ans[i]);
    return 0;
}

然后就滚去补长跑了
~~辣鸡边双让我痛苦~~

可以注意到经过一个点时他所在边双是不走白不走的
而且对于一个无向图把边双都缩起来之后就会形成一个森林注意一定是森林
于是就lct了啊
这题比较恶心的地方在于缩点之后还有各种查询让人有点分不清什么fat什么联通之类的问题(有一个并查集用于判定属于哪一个边双另一个则维护图的连通性)
细节挺多的首先是我有点疑惑的在于
为什么修改点权之前一定要先spaly?
(不这样做会WA)

然后是access的时候要把fa和find(fa)并起来
以及各种查询都要注意是哪个fa
还有缩点操作其实是通过提取路径然后转成一棵splay 往下bfs
将点权转移的同时进行清空与压缩

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 200000
#define rg register
using namespace std;
inline int gi(){
    int w=0,q=0; char c=getchar();
    while((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if(c=='-') q=1,c=getchar();
    while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}
int n,m,h,t,tp;
int fa[N],fat[N],bl[N],c[N],w[N],val[N],ch[N][2],rev[N],q[N],st[N];
int find(int x) { return bl[x]==x?x:bl[x]=find(bl[x]); }
int lfind(int x) { return fat[x]==x?x:fat[x]=lfind(fat[x]); }
bool ir(int x) { return (ch[fa[x]][0]!=x)&&(ch[fa[x]][1]!=x); }
void up(int x) { if (x) w[x]=w[ch[x][0]]+w[ch[x][1]]+val[x]; }
void pd(int x){
    if (x*rev[x]==0) return ;
    swap(ch[x][0],ch[x][1]),rev[x]=0;
    if (ch[x][0]) rev[ch[x][0]]^=1;
    if (ch[x][1]) rev[ch[x][1]]^=1;
}
void rot(int x){
    int p=fa[x],q=fa[p],l=ch[p][1]==x,r=l^1;
    if (!ir(p)) ch[q][ch[q][1]==p]=x;
    fa[x]=q,fa[p]=x;
    fa[ch[x][r]]=p,ch[p][l]=ch[x][r],ch[x][r]=p;
    up(p),up(x);
}
void splay(int x){
    st[tp=1]=x;
    for (int i=x;!ir(i);i=fa[i]) st[++tp]=fa[i];
    while (tp) pd(st[tp--]);
    while (!ir(x)){
        int p=fa[x],q=fa[p];
        if (!ir(p)){
            if ((ch[p][0]==x)^(ch[q][0]==p)) rot(x);
            else rot(p);
        } rot(x);
    }
}
void access(int x) { for (int la=0;x;x=fa[x]=find(fa[x])) splay(x),ch[x][1]=la,up(x),la=x; }//!!
void mtr(int x) { access(x),splay(x),rev[x]^=1; }
void link(int x,int y) { mtr(x),fa[x]=y,splay(y); }
void cut(int x,int y) { mtr(x),access(y),splay(y),ch[y][0]=fa[x]=0; }
int query(int x,int y) { mtr(x),access(y),splay(y); return w[y]; }
void bfs(int s){
    q[t=1]=s,h=0;
    while (h<t){
        int x=q[++h],v,f;
        for (int i=0;i<2;++i){
            v=ch[x][i]; if (!v) continue;
            f=find(v),val[s]+=val[f],bl[f]=s;
            fa[v]=ch[x][i]=0,q[++t]=v;
        }
    }
}
void add(int x,int y){
    if (x==y) return ;
    int f1=lfind(x),f2=lfind(y);
    if (f1!=f2) link(x,y),fat[f1]=f2;
    else mtr(x),access(y),splay(y),bfs(y);  
}
int main(){
//  freopen ("2959.in","r",stdin);
//  freopen ("2959.out","w",stdout);
    n=gi(),m=gi();
    for (int i=1;i<=n;++i) c[i]=val[i]=gi(),bl[i]=fat[i]=i;//bl shuangliantong fat lctliantong
    int nino,x,y;
    while (m--){
        scanf ("%d%d%d",&nino,&x,&y);
        int f1=find(x),f2=find(y);
        if (nino==1) add(f1,f2);
        if (nino==2) access(f1),splay(f1),val[f1]-=c[x],c[x]=y,val[f1]+=c[x],up(f1);
        if (nino==3) printf ("%d\n",lfind(f1)==lfind(f2)?query(f1,f2):-1);
    }   
    return 0;
}

然后是写了我特别久的
据说这个可以A…? 清橙上还是只有70可能我写丑了(明明链剖常数小啊可能是线段树的锅吧)
这个的思路与lct有些类似但是离线做法
先把树建造出来丢好链剖那一套理论的东西
然后就是加边啦还是判连通性很恶心各种冰茶机搅在一起
然后犯了个很致命的错误
就是我每次求top都find了
然后…那个deep比较就会挂而且就一直都跳不到一个top上去
所以一定要想清哪里要用边双标号哪里不用
链的合并是暴力跳的时间证明也不难自己想想就好

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 200000
#define rg register
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
inline int gi(){
    int w=0,q=0; char c=getchar();
    while((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if(c=='-') q=1,c=getchar();
    while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    return q?-w:w;
}
int n,m,tot,df;
int bl[N],fat[N],c[N];
int head[N],nxt[(N<<1)],to[(N<<1)];
int tr[(N<<2)],tag[(N<<2)],dfn[N],sz[N],son[N],fa[N],d[N],rev[N],tp[N];
struct data { int nino,x,y; }q[N*5];
void init() { for (int i=1;i<=n;++i) fat[i]=i; }
int fnd(int x) { return bl[x]==x?x:bl[x]=fnd(bl[x]); }
int link(int x) { return fat[x]==x?x:fat[x]=link(fat[x]); }
void up(int x) { tr[x]=tr[ls]+tr[rs]; }
void add(int x,int y) { nxt[tot]=head[x],to[tot]=y,head[x]=tot++; }
void down(int x){
    if (!tag[x]) return ;tag[x]=0;
    tr[ls]=tr[rs]=0,tag[rs]=tag[ls]=1;  
}
void dfs(int x){
    sz[x]=1;
    for (int i=head[x];i!=-1;i=nxt[i]){
        int v=to[i];
        if (v==fa[x]) continue;
        d[v]=d[x]+1,fa[v]=x;
        dfs(v),sz[x]+=sz[v];
        if (sz[v]>sz[son[x]]) son[x]=v;
    }
}
void dfs1(int x,int top){
    tp[x]=top,dfn[x]=++df,rev[df]=x;
    if (son[x]) dfs1(son[x],top);
    for (int i=head[x];i!=-1;i=nxt[i]){
        int v=to[i];
        if (v==fa[x]||v==son[x]) continue;
        dfs1(v,v);
    }
}
void build(int x,int l,int r){
    if (l==r) { tr[x]=c[rev[l]]; return ; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    up(x);
}
void update(int x,int l,int r,int v,int vw){
    if (l!=r) down(x);
    if (l==r) { tr[x]+=vw; return ; }
    int mid=(l+r)>>1;
    if (v<=mid) update(ls,l,mid,v,vw);
    if (v>mid) update(rs,mid+1,r,v,vw);
    up(x);                  
}
void cov(int x,int l,int r,int ll,int rr){
    if (l!=r) down(x);
    if (ll<=l&&r<=rr) { tag[x]=1,tr[x]=0; return ; }
    int mid=(l+r)>>1;
    if (ll<=mid) cov(ls,l,mid,ll,rr);
    if (rr>mid) cov(rs,mid+1,r,ll,rr);
    up(x);
}
int query(int x,int l,int r,int ll,int rr){
    if (l!=r) down(x);
    if (ll<=l&&r<=rr) return tr[x];
    int mid=(l+r)>>1,res=0;
    if (ll<=mid) res+=query(ls,l,mid,ll,rr);
    if (rr>mid) res+=query(rs,mid+1,r,ll,rr);
    return res;
}
int find(int x,int y,int f){
    int xx=x,yy=y,ans=0;
    int f1=tp[x],f2=tp[y];
    while (f1!=f2){
        if (d[f1]<d[f2]) swap(x,y),swap(f1,f2);
        ans+=query(1,1,n,dfn[f1],dfn[x]);
        if (f) cov(1,1,n,dfn[f1],dfn[x]);
        x=fa[f1]=fnd(fa[f1]),f1=tp[x];
    }
    if (d[x]>d[y]) swap(x,y);
    ans+=query(1,1,n,dfn[x],dfn[y]);
    if (!f) return ans; cov(1,1,n,dfn[x],dfn[y]);
    x=fnd(x),update(1,1,n,dfn[x],ans);
    while (xx!=yy&&xx&&yy){
        if (d[xx]<d[yy]) swap(xx,yy);
        bl[xx]=x,xx=fa[xx]=fnd(fa[xx]);
    }                 
}
int main(){
//  freopen ("2959.in","r",stdin);
//  freopen ("2959.out","w",stdout);
    memset(head,-1,sizeof(head));
    n=gi(),m=gi();
    for (int i=1;i<=n;++i) c[i]=gi(),bl[i]=i;
    for (int i=1;i<=m;++i) q[i]=(data){gi(),gi(),gi()};
    init();
    for (int i=1;i<=m;++i){
        if (q[i].nino!=1) continue;
        int f1=link(q[i].x),f2=link(q[i].y);
        if (f1==f2) continue;
        add(q[i].x,q[i].y),add(q[i].y,q[i].x),fat[f1]=f2;       
    }
    for (int i=1;i<=n;++i) if (!dfn[i]) dfs(i),dfs1(i,i);
    build(1,1,n),init();
    for (int i=1;i<=m;++i){
        int nino=q[i].nino,x=q[i].x,y=q[i].y,f1=fnd(x),f2=fnd(y);
        if (nino==1){
            if (link(x)!=link(y)) fat[link(x)]=link(y); 
            else if (f1!=f2) find(f1,f2,1);
        }
        if (nino==2) update(1,1,n,dfn[f1],y-c[x]),c[x]=y;
        if (nino==3) printf ("%d\n",link(x)==link(y)?find(f1,f2,0):-1);
    }
    return 0;
}

Go 1.12 版本新特性
Go 1.12 昨天，Go 官方发布 1.12 版本。本文介绍下 Go 1.12 版本变更的内容。 Go 1.12...
李云峰吃鼻屎记录表
1.12 10:18 吃了1次 1.12 12:59 2
7.0周检视第十四周（01.12-01.18）
本周计划1.12–1.18 日历事项 1.12 易效能7.0 晨会 1.12LD上门取样盒材质 1.13大宝舞蹈汇...
Docker 1.12.0 Swarm
docker1.12 Swarm 模式简介 Docker Engine 1.12 集成了Swarm集群工具. 主要...
报错 | Tensorflow 安装踩坑记
之前装好了 1.12，可以正常使用。然后，我安装 tensorboard == 1.12，导致 tensorflo...
远程更新
版本【1.12】
三摩地1.12-1.14
1.12 止息必须通过修行和不执着来达成。 1.12 Both practice and non-reaction...
如果 Docker 升级或者重启的话，那容器是不是都会被停掉然后
在 1.12 以前的版本确实如此，但是从 1.12 开始，Docker 引擎加入了 --live-restore ...
树莓派docker swarm集群部署 portainer 管理
介绍 Swarm 在 Docker 1.12 版本之前属于一个独立的项目，在 Docker 1.12 版本发布之后...
Docker Swarm 入门一篇文章就够了
Swarm 在 Docker 1.12 版本之前属于一个独立的项目，在 Docker 1.12 版本发布之后，该项...