BZOJ 4383 Pustynia

发表于 | 更新于

Link

Solution

考虑最最最暴力的做法 每个限制是一个区间[l,r][l,r]集体小于一个点uu的条件，那就把区间的每个点依次向这个点连长度为11的有向边，然后拓扑序。 好吧显然这个做法是闹着玩的 然后考虑一个优化的做法：每个限制建立一个新点pp，点pp到点uu连11，区间[l,r][l,r]集体到点pp连00，然后拓扑序。(为什么让我想到了SAM的构造233) 这个虽然科学了一些，但显然还是啄急。 然后高能： 考虑到每个限制是一个区间连到点的形式，那就用线段树来优化，把区间拆成logL\log L段，

Tips

Code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "lucida"

const int MAXN=100000+11,INF=1e9,MAXM=200000+11,SIZE=(MAXN<<2)+MAXM,
	  SIZE_E=4021928;//m log^2 n+n*4+k?;
void Adde(int,int,int);
int son[SIZE][2],pc,TL,TR,ref[MAXN],a[SIZE],f[SIZE];
void Build(int &pos,int L,int R) {
	pos=++pc;
	f[pos]=1;
	if(L!=R) {
		int Mid=(L+R)>>1;
		Build(son[pos][0],L,Mid);
		Build(son[pos][1],Mid+1,R);
		Adde(son[pos][0],pos,0);
		Adde(son[pos][1],pos,0);
	}
	else ref[L]=pos;
}
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre){}
	void *operator new(size_t);
}*id[SIZE];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((SIZE_E)*sizeof(Edge)),*Me=Pool;
	return Me++;
}
int ind[SIZE];
void Adde(int f,int t,int v) {
	ind[t]++;
	id[f]=new Edge(t,v,id[f]);
}
void Ins(int pos,int L,int R,int l,int r,int to,int v) {
	if(L==l && R==r)
		Adde(pos,to,v);
	else {
		int Mid=(L+R)>>1;
		if(r<=Mid)
			Ins(son[pos][0],L,Mid,l,r,to,v);
		else if(Mid+1<=l)
			Ins(son[pos][1],Mid+1,R,l,r,to,v);
		else {
			Ins(son[pos][0],L,Mid,l,Mid,to,v);
			Ins(son[pos][1],Mid+1,R,Mid+1,r,to,v);
		}
	}
}
void Adde(int l,int r,int t,int v) {
	if(l<=r)
		Ins(1,TL,TR,l,r,t,v);
}
int main() {
//	freopen("input","r",stdin);
	int n,s,m;is>>n>>s>>m;
	int root;Build(root,TL=1,TR=n);
	for(int i=1;i<=s;++i) {
		int p;
		is>>p;
		is>>a[ref[p]];
		f[ref[p]]=a[ref[p]];
	}
	for(int i=1;i<=m;++i) {
		int cur=++pc,l,r,k;
		is>>l>>r>>k;
		while(k--) {
			int p;is>>p;
			Adde(cur,ref[p],1);
			Adde(l,p-1,cur,0);
			l=p+1;
		}
		Adde(l,r,cur,0);
	}
	static int Q[SIZE];
	int he=1,ta=0;
	bool tak=1;
	for(int i=1;i<=pc;++i) 
		if(!ind[i]) 
			Q[++ta]=i;
	while(he<=ta) {
		int cur=Q[he++];
		for(Edge *e=id[cur];e;e=e->pre) {
			int u=e->to;
			if(--ind[u]==0)
				Q[++ta]=u;
			chkmx(f[u],f[cur]+e->v);
			if(f[u]>INF || (a[u] && f[u]>a[u])) {
				tak=0;
				goto out;
			}
		}
	}
out:
	if(ta!=pc) tak=0;
	if(tak) {
		os<<"TAK"<<'\n';
		for(int i=1;i<=n;++i)
			os<<f[ref[i]]<<(i==n?'\n':' ');
	}
	else 
		os<<"NIE"<<'\n';
	return 0;
}