BZOJ 1006 神奇的国度

发表于 | 更新于

Link

Solution

弦图的最小染色，很多结论都不会证明，所以题解待填

最精华的部分大概是线性维护最大值了。

一种最值问题的解法

%%jcvb%%

Problem

一个长度为nn的序列，mm次操作，每次可以选择删除一个数字，或者把一个数字的值增大11，要求实时维护最大数字的下标

Solution

显然可以用平衡树或者堆来做，但是相当大材小用，没有发挥问题的特性，复杂度也带着log\log

思路是：设数字的值域为[1,n][1,n]，那就开nn个桶，每个桶上ii挂着一个链表，表示值为ii的数字的下标。

修改aia_i时直接把下标ii插入bucket[ai+1]bucket[a_i+1]，记录一个值ff表示当前已知的最大值并更新。

删除通过bool[]实现。

查询需要从bucket[f]bucket[f]开始，删掉所有被删除了的数字，如果bucket[f]bucket[f]被删空了，就 ，直到找到一个没有被删除的数字即是答案。

复杂度：

每次操作至多增加一个链表节点，所以链表中共插入O(n+m)O(n+m)个节点，同样删除次数也是O(n+m)O(n+m)。

每次插入，ff要么+1+1，要么不变，所以ff的增加、减少次数都是O(m)O(m)。

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}

const int MAXN=10000+11,MAXM=1000000+11;
struct Edge
{
	int to,pre;
}e[MAXM<<1];int id[MAXN],ec;
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
namespace _List_
{
	const int SIZE=MAXN+MAXM;
	struct Node
	{
		Node *pre;
		int val;
		Node(Node *pre,int val):pre(pre),val(val){}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	typedef Node List_Node;
	struct List
	{
		typedef List_Node Node;
		Node *head;
		void push_front(int val){head=new(ME++) Node(head,val);}
		void pop_front(){head=head->pre;}
	}buck[MAXN];
}using namespace _List_;
int main()
{
	freopen("input","r",stdin);
	static int seq[MAXN],ud[MAXN],color[MAXN],pot[MAXN];
	int n,m;get(n),get(m);
	for(int i=1;i<=m;++i)
	{
		int f,t;get(f),get(t);
		Adde(f,t);
	}
	int mx=0;
	for(int i=1;i<=n;++i)
		buck[pot[i]=0].push_front(i);
	ud[0]=1;
	for(int i=n;i>=1;--i)
	{
		int cur=-1;
		do
		{
			if(cur==-1) cur=0;
			else mx--;
			while(buck[mx].head && ud[cur=buck[mx].head->val])
				buck[mx].pop_front();
		}while(ud[cur]);
		ud[cur]=1;
		seq[i]=cur;
		for(int j=id[cur];j;j=e[j].pre)
		{
			int u=e[j].to;
			if(!ud[u])
				buck[++pot[u]].push_front(u);
			chkmx(mx,pot[u]);
		}
	}
	memset(ud,0,sizeof(ud));
	int Ans=0;
	for(int i=n;i>=1;--i)
	{
		int pos=seq[i];
		for(int j=id[pos];j;j=e[j].pre)
			ud[color[e[j].to]]=i;//e[j].to
		for(color[pos]=1;ud[color[pos]]==i;++color[pos]);
		chkmx(Ans,color[pos]);
	}
	put(Ans),putchar('\n');
	return 0;
}