【Nowcoder71E】组一组（差分约束，最短路）

题面

Nowcoder

题解

看到二进制显然就直接拆位，那么区间的按位或和按位与转成前缀和之后，可以写成两个前缀和的值的差的大小关系，那么直接差分约束就好了。

注意几个细节，首先相等是要两侧都要连边，不要直连了一侧；然后这题卡常，所以对于区间内全是一的情况，处理出哪些位置确定是一，然后求个前缀和，直接从\(0\)连过去，这样子可以优化大量时间。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,A[MAX],dis[MAX],d[MAX];

int L[MAX],R[MAX],X[MAX],O[MAX];

struct Line{int v,next,w;}e[MAX*5];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

bool vis[MAX];

void SPFA()

{

	queue<int> Q;for(int i=0;i<=n;++i)dis[i]=-1e9;

	Q.push(0);dis[0]=0;vis[0]=true;

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

			if(dis[e[i].v]<dis[u]+e[i].w)

			{

				dis[e[i].v]=dis[u]+e[i].w;

				if(!vis[e[i].v])vis[e[i].v]=true,Q.push(e[i].v);

			}

		vis[u]=false;

	}

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;++i)O[i]=read(),L[i]=read(),R[i]=read(),X[i]=read();

	for(int i=0;i<20;++i)

	{

		for(int j=0;j<=n;++j)h[j]=d[j]=0;cnt=1;

		for(int j=1;j<=m;++j)

			if(O[j]==1)

			{

				if(X[j]&(1<<i))Add(L[j]-1,R[j],1);

				else Add(L[j]-1,R[j],0),Add(R[j],L[j]-1,0);

			}

			else

			{

				if(X[j]&(1<<i))Add(L[j]-1,R[j],R[j]-L[j]+1),Add(R[j],L[j]-1,-R[j]+L[j]-1),++d[L[j]],--d[R[j]+1];

				else Add(R[j],L[j]-1,L[j]-R[j]);

			}

		for(int j=1;j<=n;++j)Add(j-1,j,0);

		for(int j=1;j<=n;++j)Add(j,j-1,-1);

		for(int j=1;j<=n;++j)d[j]+=d[j-1];

		for(int j=1;j<=n;++j)if(d[j])d[j]=1;

		for(int j=1;j<=n;++j)d[j]+=d[j-1];

		for(int j=1;j<=n;++j)Add(0,j,d[j]);

		SPFA();

		for(int j=1;j<=n;++j)A[j]|=(dis[j]-dis[j-1])*(1<<i);

	}

	for(int i=1;i<=n;++i)printf("%d ",A[i]);puts("");

	return 0;

}