UVa12657移動(dòng)盒子

當(dāng)插入刪除搬家移動(dòng)位置比較多的時(shí)候，普通數(shù)組必定超時(shí)，此時(shí)在數(shù)據(jù)結(jié)構(gòu)上考慮優(yōu)化，用鏈表。

要知道盒子的前驅(qū)和后繼，采用雙向鏈表。

結(jié)點(diǎn)類三個(gè)成員，左指針、右指針、數(shù)據(jù)值。指針是數(shù)組下標(biāo)。

因?yàn)樵擃}目是根據(jù)數(shù)據(jù)值來(lái)移動(dòng)，而不是數(shù)據(jù)值的位置，所以最好是把數(shù)據(jù)值就當(dāng)作數(shù)組下標(biāo)，直接將元素對(duì)應(yīng)到房間下標(biāo)。因此結(jié)點(diǎn)類就不需要3個(gè)成員，只需要2個(gè)。

此外，仍然用0號(hào)代表頭結(jié)點(diǎn)，初始化first指針指向0號(hào)，頭結(jié)點(diǎn)的右指針指向第一個(gè)實(shí)際元素，頭結(jié)點(diǎn)的左指針指向最后一個(gè)元素。維護(hù)last指針指向最后一個(gè)元素，最后一個(gè)元素的左指針指向前驅(qū)，右指針指向頭結(jié)點(diǎn)。

操作3——交換位置

畫個(gè)圖就知道如何寫了，而且還要確定好執(zhí)行順序。

void SWAP(int a, int b) { // 交換位置 
	rlink[llink[a]] = b;
	llink[rlink[a]] = b;
	
	rlink[llink[b]] = a; 
	llink[rlink[b]] = a;
	
	int t = rlink[b];
	rlink[b] = rlink[a];
	rlink[a] = t;
	 
	t = llink[b];
	llink[b] = llink[a];
	llink[a] = t;	
	return;
}

這種寫法對(duì)于一般的情況是可以的，但是對(duì)于相鄰的情況來(lái)說就會(huì)出現(xiàn)問題，就會(huì)出現(xiàn)自己的左右指針指向自己的情況。因此數(shù)據(jù)結(jié)構(gòu)上的操作要考慮完整。以上代碼交上去得了一個(gè)超時(shí)，幸好有一組測(cè)試數(shù)據(jù)對(duì)應(yīng)到了超時(shí)的這種情況。

4 1
3 3 4

這組數(shù)據(jù)遲遲不能出結(jié)果。陷入了死循環(huán)，交換寫得有問題。特殊情況的考慮要貫穿所有操作。

這兩種寫法不能合并。3種情況合成2種就是讓鏈上位于左邊的數(shù)在前面，視情況交換a和b。

if (llink[a] == b) { 
    int t = a;
    a = b;
    b = t;
}

!> 值突然改變要么就是越界要么就是==寫成=。

不相鄰情況：
a->llink->rlink=b
a->rlink->llink=b
b->rlink->llink=a
b->llink->rlink=a
// 三變量交換，這里是直觀寫法
a->rlink=b->rlink
b->rlink=a->rlink
// 三變量交換，這里是直觀寫法
a->llink=b->llink
b->llink=a->llink

相鄰情況：
a->llink->rlink=b
b->rlink->rllink=a
a->rlink=b->rlink
b->llink=a->llink
b->rlink=a
a->llink=b

操作4——反轉(zhuǎn)整條鏈

反轉(zhuǎn)整條鏈，將last指針和頭結(jié)點(diǎn)指針對(duì)調(diào)。但是這樣還不夠，2、3操作涉及把盒子移動(dòng)到左邊右邊，如果反轉(zhuǎn)了，左邊右邊關(guān)系就改變了，如果對(duì)每個(gè)結(jié)點(diǎn)對(duì)調(diào)左右指針會(huì)比較麻煩和費(fèi)時(shí)。因此引入一個(gè)標(biāo)記，一旦引入這個(gè)標(biāo)記，其他操作都要考慮這個(gè)標(biāo)記。線段樹的懶標(biāo)記也是引入標(biāo)記。

提示6-6非常核心：

如果數(shù)據(jù)結(jié)構(gòu)上的某一個(gè)操作很耗時(shí)，有時(shí)可以用加標(biāo)記的方式處理，而不需要真的執(zhí)行那個(gè)操作。但同時(shí)，該數(shù)據(jù)結(jié)構(gòu)的所有其他操作都要考慮這個(gè)標(biāo)記。

如果a在b左邊，反轉(zhuǎn)整條鏈，a就在b的右邊。如果a要放到b的左邊，反轉(zhuǎn)整條鏈就是把a(bǔ)放到b的右邊。

例子：1 a b

• 沒有反轉(zhuǎn) 執(zhí)行前 a <-> c <-> d <-> b 執(zhí)行后 c <-> d <-> a <-> b
• 有反轉(zhuǎn) 執(zhí)行前 b <-> d <-> c <-> a 執(zhí)行后 a <-> b <-> d <-> c

? 再把這個(gè)執(zhí)行結(jié)果反轉(zhuǎn)回去就是c <-> d <-> b <-> a，相當(dāng)于沒有反轉(zhuǎn) 2 a b

? 因此如果有反轉(zhuǎn)，輸出的時(shí)候也要反轉(zhuǎn)。

求奇數(shù)位置的盒子編號(hào)就挨著走鏈，直到指回頭結(jié)點(diǎn)。

如果是盒子總數(shù)是奇數(shù)，反轉(zhuǎn)就不影響結(jié)果，如果盒子總數(shù)是偶數(shù)，反轉(zhuǎn)就是取補(bǔ)。注意最大50億超了int。注意修改數(shù)據(jù)類型則所有地方，包括輸入輸出都要改。涉及l(fā)ong long就要隨時(shí)注意類型轉(zhuǎn)換，還有防止溢出的問題。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100010;

int llink[MAXN];
int rlink[MAXN];
int first, last;
int inv; // 反轉(zhuǎn)標(biāo)記 
int n, m;
void Init(int n) {
	inv = 0;
	first = 0;
	last = n;
	for(int i = 1; i < MAXN - 1; i++) { // 從1開始沒有給0弄到 
		llink[i] = i - 1;
		rlink[i] = i + 1;
	}
	rlink[0] = 1; 
	rlink[n] = 0;
	return;
}

void SWAP(int a, int b) { // 交換位置
	if (llink[a] == b || rlink[a] == b) {
		//3種寫法變成2種寫法就是使得位于左邊的數(shù)在前面,交換a和b。
		if (llink[a] == b) { 
			int t = a;
			a = b;
			b = t;
		}
		rlink[llink[a]] = b;
		llink[rlink[b]] = a; 
		rlink[a] = rlink[b];
		llink[b] = llink[a];
		
		rlink[b] = a;
		llink[a] = b;	
	} else {
		rlink[llink[a]] = b;
		llink[rlink[a]] = b;
		
		rlink[llink[b]] = a; 
		llink[rlink[b]] = a;
		
		int t = rlink[b];
		rlink[b] = rlink[a];
		rlink[a] = t;
		 
		t = llink[b];
		llink[b] = llink[a];
		llink[a] = t;			
	}

	return;
}

void InsertToLeft(int a, int b) { // 將a移動(dòng)到b左邊 
	rlink[llink[a]] = rlink[a];
	llink[rlink[a]] = llink[a];
	
	rlink[llink[b]] = a;
	
	llink[a] = llink[b];
	rlink[a] = b;
	llink[b] = a;
	
	return;
}

void InsertToRight(int a, int b) { // 將a移動(dòng)到b右邊
	rlink[llink[a]] = rlink[a];
	llink[rlink[a]] = llink[a];
	
	llink[rlink[b]] = a;
	
	rlink[a] = rlink[b];
	llink[a] = b;
	rlink[b] = a;
	
	return;
}

int main() {
	freopen("data.in", "r", stdin);
	
	
	
	
	int k = 0;
	while (scanf("%d%d", &n, &m) == 2) {
		Init(n);
		for (int i = 0; i < m; i++) {
			int op = 0;
			scanf("%d", &op);
			if (op == 4) { // 反轉(zhuǎn)整條鏈 
				if (inv == 1) {
					inv = 0;
				} else {
					inv = 1;
				}
			} else if (op == 3) { // 交換位置 
				int a, b;
				scanf("%d%d", &a, &b);			
				SWAP(a, b);
			} else { // 移動(dòng)到左邊或者右邊 
				if (inv == 1) {
					op = 3 - op;
				}
				int a, b;
				scanf("%d%d", &a, &b);
				if (op == 1) { // 將a移動(dòng)到b左邊 
					if (llink[b] == a) {
						continue;
					}
					InsertToLeft(a, b); 
				} else {
					if (rlink[b] == a) {
						continue;
					}
					InsertToRight(a, b); // 將a移動(dòng)到b右邊 
				}
			}
		}
		
		long long ans = 0; // 最大的50億超了int 
		int cur = rlink[0]; // 指向第一個(gè)元素 
		int i;
		for (i = 1; cur != 0; i++) {
			if (i % 2 == 1) {
				ans += cur;
			}
			cur = rlink[cur];
		}
		if (inv == 1 && n % 2 == 0) {
			ans = (long long)(n + 1) * (n / 2) - ans; 
		}
		printf("Case %d: %lld\n", ++k, ans);
	}
	return 0;
}