description

analysis

如果把所有大小关系连成边，小的往大的连，就可以直接上拓扑
暴力连边时间复杂度\(O(n^2)\)，然而连边的过程，考虑用线段树优化
线段树上的所有儿子节点向父亲节点连\(0\)边，
每个操作被分成\(k+1\)个小区间，然后该操作的编号向\(k\)个区间最大值连\(1\)边
对于线段树上表示小区间的\(\log\)个区间，都向该编号连\(0\)边
最后一波拓扑就好了，这类套路要记一下

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<queue>

#define MAXN 100005

#define ll long long

#define reg register ll

#define max(x,y) ((x>y)?(x):(y))

#define min(x,y) ((x<y)?(x):(y))

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

#define rep(i,a) for (reg i=last[a];i;i=next[i])

using namespace std;

ll last[MAXN*50],next[MAXN*50],tov[MAXN*50],len[MAXN*50];

ll a[MAXN*20],d[MAXN*20],pos[MAXN];

ll n,m,q,now,tot;

queue<ll>Q;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

inline void link(ll x,ll y,ll z){next[++tot]=last[x],last[x]=tot,tov[tot]=y,len[tot]=z,++d[y];}

inline void maketree(ll t,ll l,ll r)

{

	now=max(now,t);if (l==r){pos[l]=t;return;}

	ll mid=(l+r)>>1;link(t<<1,t,0),link((t<<1)+1,t,0);

	maketree(t<<1,l,mid),maketree((t<<1)+1,mid+1,r);

}

inline void query(ll t,ll l,ll r,ll x,ll y)

{

	if (l==x && y==r){link(t,now,0);return;}

	ll mid=(l+r)>>1;

	if (x<=mid)query(t<<1,l,mid,x,min(y,mid));

	if (y>mid)query((t<<1)+1,mid+1,r,max(x,mid+1),y);

}

int main()

{

	freopen("web.in","r",stdin);

	//freopen("web.out","w",stdout);

	n=read(),m=read(),q=read();

	maketree(1,1,n);

	fo(i,1,m){ll x=read();a[pos[x]]=read();}

	while (q--)

	{

		ll l=read(),r=read(),k=read(),x=l;++now;

		fo(i,1,k)

		{

			ll y=read();if (x<=y-1)query(1,1,n,x,y-1);

			link(now,pos[y],1),x=y+1;

		}

		if (x<=r)query(1,1,n,x,r);

	}

	fo(i,1,now)if (!d[i]){Q.push(i);if (!a[i])a[i]=1;}

	while (!Q.empty())

	{

		ll x=Q.front();Q.pop();

		rep(i,x)

		{

			a[tov[i]]=max(a[tov[i]],a[x]+len[i]);

			if (!(--d[tov[i]]))Q.push(tov[i]);

		}

	}

	printf("Possible\n");

	fo(i,1,n)printf("%lld ",a[pos[i]]);

	printf("\n");

	return 0;

}

巴特西

【JZOJ6411】上网

description

analysis

code

最新文章

热门文章