2021.8.7 队测题解

显然题目是不公开的，所以只会写出每个题的解法，不会贴链接和题面。

昔我往矣

草没听过的 Trick 自闭了。

显然答案是两两之间的路径求并，但这样太麻烦了。

首先我们将 dfs 序最大的和最小的点之间的路径作为主链，然后对于剩下的点，求出他与被加入的点的 LCA 中深度最大的那一个，那么这就是该点不断往上跳到主链的入点，直接计入答案即可。

只要会写 LCA 就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4;
int n;
int head[N+10],nxt[N*2+10],son[N*2+10],dis[N*2+10],tot;
void add(int x,int y,int v) {
    son[++tot]=y,dis[tot]=v;
    nxt[tot]=head[x],head[x]=tot;
}
int dfn[N+10],dep[N+10],ju[N+10][20],cnt,Dis[N+10],Fa[N+2];
void dfs(int x,int fa) {
    ju[x][0]=fa;dep[x]=dep[fa]+1;
    dfn[x]=++cnt;
    for(int i=head[x];i;i=nxt[i])
        if(son[i]!=fa) {
            Dis[son[i]]=Dis[x]+dis[i];
            dfs(son[i],x);
        }
}
int q;
int a[6];
bool cmp(int x,int y) {
    return dfn[x]<dfn[y];
}
int LCA(int x,int y) {
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=18;i>=0;i--)
        if(dep[ju[x][i]]>=dep[y])
            x=ju[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--)
        if(ju[x][i]!=ju[y][i])
            x=ju[x][i],y=ju[y][i];
    return ju[x][0];
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int x,y,v;
        scanf("%d %d %d",&x,&y,&v);
        x++,y++;
        add(x,y,v),add(y,x,v);
    }
    dfs(1,0);
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++)
            ju[i][j]=ju[ju[i][j-1]][j-1];
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        for(int j=1;j<=5;j++) scanf("%d",&a[j]),a[j]++;
        sort(a+1,a+6,cmp);
        int lca1=LCA(a[1],a[5]);
        int out=Dis[a[1]]+Dis[a[5]]-2*Dis[lca1];
        for(int j=2;j<=4;j++) {
            int ma=0,id=0;
            for(int k=1;k<j;k++) {
                int lca=LCA(a[j],a[k]);
                if(dep[lca]>ma) ma=dep[lca],id=lca;
            }
            int lca=LCA(a[j],a[5]);
            if(dep[lca]>ma) ma=dep[lca],id=lca;
            out+=Dis[a[j]]-Dis[id];
        }
        printf("%d\n",out);
    }
}

杨柳依依

暴力题，没做出来是我菜了。

从每个人的起始点终止点开始 BFS，求出每一条路径的长度和数量，暴力做就行了。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=5010;
int n,m,k;
vector<int> G[N+2];
double E[N+2];
int dis[2][N+2],sum[2][N+2];
int dl[N+2],l,r;
void bfs(int s,int *dis,int *sum) {
    memset(dis,-1,sizeof dl);
    memset(sum,0,sizeof dl);
    dis[dl[l=r=1]=s]=0;
    sum[s]=1;
    while(l<=r) {
        int x=dl[l++];
        for(auto y:G[x])
            if(dis[y]==-1) {
                dis[dl[++r]=y]=dis[x]+1;
                sum[y]+=sum[x];
            }
            else if(dis[y]==dis[x]+1) sum[y]+=sum[x];
    }
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1,x,y;i<=m;i++) {
        scanf("%d %d",&x,&y);
        x++,y++;
        G[x].pb(y),G[y].pb(x);
    }
    scanf("%d",&k);
    while(k--) {
        int a,b;
        scanf("%d %d",&a,&b);
        a++,b++;
        bfs(a,dis[0],sum[0]);
        bfs(b,dis[1],sum[1]);
        int Dis=dis[0][b],Sum=sum[0][b];
        for(int i=1;i<=n;i++)
            if(dis[0][i]+dis[1][i]==Dis)
                E[i]+=1.0*(sum[0][i]*sum[1][i])/Sum;
    }
    double ma=0;
    int id=-1;
    for(int i=1;i<=n;i++)
        if(E[i]>ma) ma=E[i],id=i;
    //cout<<ma<<endl;
    printf("%d\n",id-1);
}

今我来思

按 $x$ 排序每个询问，那么每一个位置的下限显然可以区间覆盖求出，如果这个下限都不能满足条件，显然无解。

接下来按顺序考虑每一个数 $i$ ，考虑他填在哪里，对有关 $i$ 的询问区间求交，那么位置一定在交里，同时还可以选择下限 $\le i$ 的位置，对上面两个的集合取交，随便填一个就可以了。

实际实现的时候需要一个 set 辅助。

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int n,q;
int L[N+10],R[N+10],X[N+10];
namespace luangao {
	struct node {
		int ma[N*4+10],cov[N*4+10];
		void pushdown(int p) {
			if(cov[p]) {
				ma[p*2+1]=ma[p*2]=cov[p];
				cov[p*2+1]=cov[p*2]=cov[p];
				cov[p]=0;
			}
		}
		void pushup(int p) {
			ma[p]=max(ma[p*2],ma[p*2+1]);
		}
		void update(int p,int l,int r,int x,int y,int v) {
			if(x<=l&&r<=y) {
				ma[p]=v,cov[p]=v;
				return;
			}
			pushdown(p);
			int mid=(l+r)/2;
			if(x<=mid) update(p*2,l,mid,x,y,v);
			if(y>mid) update(p*2+1,mid+1,r,x,y,v);
			pushup(p);
		}
		int query(int p,int l,int r,int x) {
			if(l==r) return ma[p];
			pushdown(p);
			int mid=(l+r)/2;
			if(x<=mid) return query(p*2,l,mid,x);
			else return query(p*2+1,mid+1,r,x);
		}
	} tr;
	int sx[N+10],col[N+10],ans[N+10];
	vector<int> pos[N+10];
	set<int> dx;
	bool cmp(int x,int y) {
	    return X[x]<X[y];
	}
struct ST {
    int Logn[200005], f[200002][22];
    void pre() {
        Logn[1] = 0;
        Logn[2] = 1;

        for (int i = 3; i < 200000; i++) {
            Logn[i] = Logn[i / 2] + 1;
        }
    }
    void init() {
        for (int j = 1; j <= 21; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    int query(int x, int y) {
        int s = Logn[y - x + 1];
        return min(f[x][s], f[y - (1 << s) + 1][s]);
    }
} st;
	void solve() {
		for(int i=1; i<=q; i++) sx[i]=i;
		sort(sx+1,sx+q+1,cmp);
		for(int cnyz_newbie=1; cnyz_newbie<=q; cnyz_newbie++) {
			int i=sx[cnyz_newbie];
			tr.update(1,1,n,L[i],R[i],X[i]);
		}
		int zz=1;
		for(int i=1; i<=n; i++) col[i]=tr.query(1,1,n,i),pos[col[i]].push_back(i);
	    //remember to make no solution;
	    st.pre();
	    for(int i=1;i<=n;i++) st.f[i][0]=col[i];
	    st.init();
	    for(int i=1;i<=q;i++) {
	        if(st.query(L[i],R[i])!=X[i]) {
	            for(int i=1;i<=n;i++) printf("-1 ");
	            return;
	        }
	    }
		for(int i=0;i<n;i++) {
		    for(auto j:pos[i]) dx.insert(j);
		    if(X[sx[zz]]!=i) {
		        if(dx.size()==0) {
		            for(int i=1;i<=n;i++) printf("-1 ");
		            return;
		        }
		        int p=(*dx.begin());
		        ans[p]=i;
		        dx.erase(p);
		        continue;
		    }
		    int l=L[sx[zz]],r=R[sx[zz]];
		    zz++;
		    while(zz<=q&&X[sx[zz]]==i)
		        l=max(l,L[sx[zz]]),r=min(r,R[sx[zz]]),zz++;
		    if(l>r) {
		        for(int i=1;i<=n;i++) printf("-1 ");
		        return;
		    }
		    int p=(*dx.lower_bound(l));
		    ans[p]=i;
		    dx.erase(p);
		}
		for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	}
}
int main() {
	//freopen("nostalgia.in","r",stdin);
	//freopen("nostalgia.out","w",stdout);
	scanf("%d %d",&n,&q);
	for(int i=1; i<=q; i++) scanf("%d %d %d",&L[i],&R[i],&X[i]),L[i]++,R[i]++;
	luangao::solve();
}

雨雪霏霏

将原图看成网格图，边权为两点海拔的最大值，建立 Kruskal 重构树。

那么，此时对于一个点的询问，就是子树内的询问，运用 dfs 序拍平到序列上，变成区间数颜色，单点修改，带修莫队解决。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int h,w,Q1,n;
int L[N+10],C[N+10];
int bh(int x,int y) {
    return (x-1)*w+y;
}
namespace Mo {
    int a[N+10],cnt[N+10],Ans[N+10],qtot,ctot,ans,pre[N+10],BL,l,r,t;
    struct node {
        int x,y,t;
    } Q[N+10],C[N+10];
    void init(int type,int x,int y,int z) {
        if(type==1) Q[++qtot]=(node){x,y,z};
        else C[++ctot]=(node){x,y,z};
    }
    bool cmp(node _,node __) {
       int k1=(_.x-1)/BL+1,k2=(__.x-1)/BL+1;
		if(k1!=k2)return k1<k2;
		k1=(_.y-1)/BL+1,k2=(__.y-1)/BL+1;
		if(k1!=k2)return k1<k2;
		return k1&1?_.t<__.t:_.t>__.t;
    }
    void add(int x,int val) {
        if(!cnt[x]) ans++;
        cnt[x]+=val;
        if(!cnt[x]) ans--;
    }
    void add_ch(int t) {
        int x=C[t].x,v=C[t].y;
        if(l<=x&&x<=r) {
            cnt[a[x]]--;
            if(!cnt[a[x]]) ans--;
        }
        pre[t]=a[x];
        a[x]=v;
        if(l<=x&&x<=r) {
            if(!cnt[a[x]]) ans++;
            cnt[a[x]]++;
        }
    }
    void del_ch(int t) {
        int x=C[t].x;
        if(l<=x&&x<=r) {
            cnt[a[x]]--;
            if(!cnt[a[x]]) ans--;
        }
        a[x]=pre[t];
        if(l<=x&&x<=r) {
            if(!cnt[a[x]]) ans++;
            cnt[a[x]]++;
        }
    }
    void work() {
        BL=pow(w*h,2.0/3);
        sort(Q+1,Q+qtot+1,cmp);
        l=1,r=0,t=0;
        for(int i=1;i<=qtot;i++) {
            while(r<Q[i].y) add(a[++r],1);
            while(l>Q[i].x) add(a[--l],1);
            while(r>Q[i].y) add(a[r--],-1);
            while(l<Q[i].x) add(a[l++],-1);
            while(t<ctot&&C[t+1].t<Q[i].t) add_ch(++t);
            while(t>0&&C[t].t>Q[i].t) del_ch(t--);
            Ans[Q[i].t]=ans;
        }
        for(int i=1;i<=Q1;i++)
            if(Ans[i])
                if(Ans[i]==-1) puts("0");
                else printf("%d\n",Ans[i]);
    }
}
namespace Kruskal {
    vector<int> T[N+2];
    struct UFS {
        int fa[N+2];
        void init(int x) {
            for(int i=1;i<=x;i++) fa[i]=i;
        }
        int get(int x) {return fa[x]=(x==fa[x]?fa[x]:get(fa[x]));}
        void debug(int x) {
            for(int i=1;i<=x;i++) printf("%d\n",fa[i]);
        }
    } UFS;
    struct edge {
        int x,y,v;
    } E[N+2];
    bool cmp(edge _,edge __) {
        return _.v<__.v;
    }
    int l[N+2],r[N+2],ju[N+2][20],dfncnt;
    void dfs(int x) {
        l[x]=1e9;
        for(int i=1;i<20;i++) ju[x][i]=ju[ju[x][i-1]][i-1];
        for(int i:T[x]) {
            ju[i][0]=x;
            dfs(i);
            l[x]=min(l[x],l[i]);
            r[x]=max(r[x],r[i]);
        }
        if(l[x]>r[x]) l[x]=r[x]=++dfncnt;
        //printf("Point %d equals to [%d,%d]\n",x,l[x],r[x]);
    }
    int jump(int x,int v) {
        for(int i=19;i>=0;i--)
            if(ju[x][i]&&L[ju[x][i]]<=v)
                x=ju[x][i];
        return x;
    }
    void work() {
        int m=0;
        UFS.init(2*n);
        for(int i=1;i<=h;i++)
            for(int j=1;j<=w;j++) {
                if(i>1) E[++m]=(edge){bh(i-1,j),bh(i,j),max(L[bh(i-1,j)],L[bh(i,j)])};
                if(j>1) E[++m]=(edge){bh(i,j-1),bh(i,j),max(L[bh(i,j-1)],L[bh(i,j)])};
            }
        sort(E+1,E+m+1,cmp);
        for(int i=1;i<=m;i++) {
            int fx=UFS.get(E[i].x),fy=UFS.get(E[i].y);
            //printf("visit edge %d,%d %d,%d\n",E[i].x,E[i].y,fx,fy);
            if(fx!=fy) {
                L[UFS.fa[fx]=UFS.fa[fy]=++n]=E[i].v;
                T[n].push_back(fx);
                T[n].push_back(fy);
                //printf("add edge between %d,%d %d,%d\n",n,fx,n,fy);
            }
        }
        dfs(n);
        for(int i=1;i<=h*w;i++) Mo::a[l[i]]=C[i];
        for(int i=1;i<=Q1;i++) {
            int opt,x,y,v;
            scanf("%d %d %d %d",&opt,&y,&x,&v);
            if(opt==1) Mo::init(2,l[bh(x,y)],v,i);
            else {
                if(v<L[bh(x,y)]) {Mo::Ans[i]=-1;continue;}
                int p=jump(bh(x,y),v);
                Mo::init(1,l[p],r[p],i);
                //printf("init query : %d,%d,%d,%d\n",p,l[p],r[p],i);
            }
        }
    }
}
int main() {
    scanf("%d %d %d",&h,&w,&Q1);
    n=h*w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            scanf("%d",&L[bh(i,j)]);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            scanf("%d",&C[bh(i,j)]);
    Kruskal::work();
    Mo::work();
}

cnyz's Blog

2021.8.7 队测题解

昔我往矣

杨柳依依

今我来思

雨雪霏霏

下一篇：2021.8.2 队测题解