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

//list
const int maxnode=10003;
template<typename T>
struct LIST
{
	int pre[maxnode],nxt[maxnode];
	T ary[maxnode];
	int f;
	int endd;
	LIST()
	{
		f=0;
		endd=maxnode-1;
		nxt[0]=endd;
	}
	void clear()
	{
		f=0;
		endd=maxnode-1;
		nxt[0]=endd;
	}
	void insert(int k,const T& w)//insert in front of k
	{
		ary[++f]=w;
		int pree=pre[k],nxtt=k;
		pre[nxtt]=nxt[pree]=f;
		nxt[f]=nxtt;
		pre[f]=pree;
	}
	void del(int k)
	{
		int pree=pre[k],nxtt=nxt[k];
		pre[nxtt]=pree;
		nxt[pree]=nxtt;
	}
	int begin()
	{
		return nxt[0];
	}
	int end()
	{
		return endd;
	}
};

 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

template<typename T,int size>
struct QUE
{
	T ary[size];
	int f,t,cnt;
	QUE(){f=t=cnt=0;}
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w)
	{
		ary[t++]=w;
		if(t==size)t=0;
		++cnt;
	}
	T top(){return ary[f];}
	void pop()
	{
		++f,--cnt;
		if(f==size)f=0;
	}
};
template<typename T,int size>
struct memLIST
{
	 T ary[size+1];
	 int pre[size+1],nxt[size+1];
	 int f;
	 QUE<int,size> mem;
	 int endd;
	 memLIST()
	 {
	 	memset(pre,0,sizeof(pre));
	 	memset(nxt,0,sizeof(nxt));
	 	f=0;
	 	mem.clear();
	 	nxt[0]=endd;
	 	endd=size;
	 }
	 void clear()
	 {
	 	memset(pre,0,sizeof(pre));
	 	memset(nxt,0,sizeof(nxt));
	 	f=0;
	 	mem.clear();
	 	nxt[0]=endd;
	 	endd=size;
	 }
	 T operator[](int k)
	 {
	 	return ary[k];
	 }
	 void del(int k)
	 {
	 	int pree=pre[k],nxtt=nxt[k];
	 	nxt[pree]=nxtt;
	 	pre[nxtt]=pree;
	 	pre[k]=nxt[k]=0;
	 	mem.push(k);
	 }
	 void insert(const T& w,int k)//insert in front of k
	 {
	 	int id;
	 	if(!mem.empty())
		 	id=mem.top(),mem.pop();
	 	else id=++f;
	 	int pree=pre[k],nxtt=k;
	 	pre[id]=pree;
	 	nxt[id]=nxtt;
	 	nxt[pree]=pre[nxtt]=id;
	 	ary[id]=w;
	 }
	 int begin()
	 {
	 	return nxt[0];
	 }
	 int end()
	 {
	 	return endd;
	 }
};