Jun 26 2015

b415. 輸出優化練習

Problem

寫題目不只會遇到算法複雜度問題，還會遇到語法上的瓶頸，了解更深入的作業系統架構、語言特性，了解每一個函數的實作方法，就能把代碼效能發揮到淋淋盡緻。當然，對於代碼轉成執行檔的最佳化技巧也是如此，接下來就來做個基礎題吧。

現在請處理一個偽隨機數計算，輸出前 $m$ 個值。

$$x_{i+1} \equiv x_{i}^{2} \mod n$$

有興趣的同學，可以查閱 Blum Blum Shub (BBS) Generator 相關隨機數算法。

Sample Input

1
2
3

90 141 5
52 57 5
19 129 5

Sample Output

1
2
3

90 63 21 18 42
52 25 55 4 16
19 103 31 58 10

Solution

手動轉字串，減少函數 printf() 的呼叫，一次將答案吐出來便可以達到加速，由於有一部分時間都花在取模，速度最多提升個兩到三倍。

用 putchar() 速度也會比 printf() 快一點，但沒有實作 buffer 來得快。

#include <bits/stdc++.h> 
  
namespace mLocalStream {
	inline int readchar() {
	    const int N = 1048576;
	    static char buf[N];
	    static char *p = buf, *end = buf;
	    if(p == end) {
	        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
	        p = buf;
	    }
	    return *p++;
	}
	inline int ReadInt(int *x) {
	    static char c, neg;
	    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
	    neg = (c == '-') ? -1 : 1;
	    *x = (neg == 1) ? c-'0' : 0;
	    while((c = readchar()) >= '0')
	        *x = (*x << 3) + (*x << 1) + c-'0';
	    *x *= neg;
	    return 1;
	}
	class Print {
	public:
		static const int N = 1048576;
		char buf[N], *p, *end;
		Print() {
			p = buf, end = buf + N - 1;
		}
		void printInt(int x, char padding) {
			static char stk[16];
			int idx = 0;
			stk[idx++] = padding;
			if (!x)	
				stk[idx++] = '0';
			while (x)
				stk[idx++] = x%10 + '0', x /= 10;
			while (idx) {
				if (p == end) {
					*p = '\0';
					printf("%s", buf), p = buf;
				}
				*p = stk[--idx], p++;
			}
		}
		static inline void online_printInt(int x) {
			static char ch[16];
			static int idx;
			idx = 0;
			if (x == 0)	ch[++idx] = 0;
			while (x > 0) ch[++idx] = x % 10, x /= 10;
			while (idx) 
				putchar(ch[idx--]+48);
		}
		~Print() {
			*p = '\0';
			printf("%s", buf);
		}
	} bprint;
}
int main() {
	int x0, p, n;
	while (scanf("%d %d %d", &x0, &p, &n) == 3) {
		for (int i = 0; i < n; i++) {
			mLocalStream::bprint.printInt(x0, i == n-1 ? '\n' : ' ');
//			mLocalStream::Print::online_printInt(x0);
//			putchar(i == n-1 ? '\n' : ' ');
			x0 = ((long long) x0 * x0)%p;
		}
	}
	return 0;
}

Read More +

Jun 25 2015

解題區►解題區 - Zerojudge

d476. 區間查詢

Problem

一個長度為 n 的序列，支持兩種操作：

输出 $[A, B]$ 區間第 k 小的數 (從小到大排序後第 k 個)
修改第 I 個數為 W

Sample Input

Sample Output

1
2

2
3

Solution

前言

在討論用一些雜七雜八的樹類結構去跟莫隊算法搏鬥之餘，用了轉幾何方向去兜資料結構，隨後發現題目尋找的是 unique 而非計數，因此很多想法就垮台，當然出成另一道題目也是不錯。決定尋找其他想法！

開始

整體二分是什麼呢？假設操作只有修改、詢問，不包含插入、刪除，而且詢問是一個數值結果，這個數值結果可以藉由二分 + 掃描來完成，那就可以使用整體二分來離線支持。

對答案值域分治，將相關操作分治在一起，同時要保留順序性，分治過程中會不斷地累加每一個詢問的掃描數值，最後滿溢時紀錄答案。每一個操作最多在 $\log \text{MAXV}$ 層計算，因此複雜度是 $O(Q \log \text{MAXV})$。

好處是可以用常數較低的結構，所以會比較快？

應用

這一道經典題有很多作法，如持久化線段樹、塊狀鏈表、歸併樹、劃分樹、 … 等。其中能支持修改的有塊狀鏈表、複雜的持久化線段樹 (主席樹)。

帶修改的區間 K 小，概略說明二分答案 $x$，然後去查找小於等於 $x$ 的數字在區間 $[l, r]$ 內出現的次數是否大於等於 $K$。然後修改元素有加入跟移除，二分答案 mid，要將加入、移除會影響的 $A[i] \le mid$，加入或移除時對該數字的索引值 $i$ 建造統計方案。

對於(位置, 值) $\left \langle i, A[i] \right \rangle$ 來說，一開始的前 $N$ 個操作是加入 $\left \langle i, A[i] \right \rangle$，二分答案時，用一個 binary indexed tree 去維護 index 的個數，也就是說，對於修改元素 $\left \langle i, A[i] \right \rangle$ 相當於在二分答案 mid 時，插入 BIT.add(i, 1)，那對於區間詢問，相當於查找 BIT.query([l, r]) 如此一來就能知道區間 $[l, r]$ 在 mid 以內有幾個數字符合。

假設計數大於 k，詢問往左放，反之扣除已知 mid 以內的數量，詢問往右放，如此一來就完成了。

#include <bits/stdc++.h> 
using namespace std;
const int MAXQ = 65536;
const int MAXN = 65536;
const int INF = 0x3f3f3f3f;
class Offline {
public:
	struct Event {
		int x, y, k, qtype, qid;
		int calc; //
		Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0):
			x(a), y(b), k(c), qtype(d), qid(e), calc(f) {}
	};
	vector<Event> event;
	int N, ret[MAXQ];
	void init(int N) {
		this->N = N;
		event.clear();
	}
	void addEvent(int qtype, int qid, int x, int y, int k) {
		event.push_back(Event(x, y, k, qtype, qid));
	}
	void run() {
		DC(0, event.size()-1, 0, INF);
	}
private:
	// buffer
	int buf[MAXQ];
	Event ebuf1[MAXQ], ebuf2[MAXQ];
	// binary indexed tree
	int bit[MAXN];
	void add(int x, int val) {
		while (x <= N) {
			bit[x] += val;
			x += (x)&(-x);
		}
	}
	int query(int x) {
		int ret = 0;
		while (x) {
			ret += bit[x];
			x -= (x)&(-x);
		}
		return ret;
	}
	void DC(int q_l, int q_r, int val_l, int val_r) {
		if (q_l > q_r)	return ;
		if (val_l == val_r) {	// find
			for (int i = q_l; i <= q_r; i++)
				if (event[i].qtype == 2)
					ret[event[i].qid] = val_l;
			return ;
		}
		int mid = (val_l + val_r)/2;
		for (int i = q_l; i <= q_r; i++) {
			if (event[i].qtype == 0 && event[i].y <= mid)
				add(event[i].x, 1);
			else if (event[i].qtype == 1 && event[i].y <= mid)
				add(event[i].x, -1);
			else if (event[i].qtype == 2)
				buf[i] = query(event[i].y) - query(event[i].x-1);
		}
		for (int i = q_l; i <= q_r; i++) { // resume
			if (event[i].qtype == 0 && event[i].y <= mid)
				add(event[i].x, -1);
			else if (event[i].qtype == 1 && event[i].y <= mid)
				add(event[i].x, 1);
		}
		int lidx = 0, ridx = 0;
		for (int i = q_l; i <= q_r; i++) {
			if (event[i].qtype == 0 || event[i].qtype == 1) {
				if (event[i].y <= mid)
					ebuf1[lidx++] = event[i];
				else
					ebuf2[ridx++] = event[i];
			} else {
				if (event[i].calc + buf[i] > event[i].k - 1)
					ebuf1[lidx++] = event[i];
				else {
					event[i].calc += buf[i];
					ebuf2[ridx++] = event[i];
				}
			}
		}
		for (int i = 0; i < lidx; i++)
			event[q_l+i] = ebuf1[i];
		for (int i = 0; i < ridx; i++)
			event[q_l+lidx+i] = ebuf2[i];
		DC(q_l, q_l+lidx-1, val_l, mid);
		DC(q_l+lidx, q_r, mid+1, val_r);
	}
} off;
int main() {
	int n, m, x, y, k, v;
	int A[65536];
	char cmd[10];
	while (scanf("%d %d", &n, &m) == 2) {
		off.init(n);
		// qtype 0:add, 1:remove, 2: query
		for (int i = 1; i <= n; i++) {
			scanf("%d", &A[i]);
			off.addEvent(0, 0, i, A[i], 0);
		}
		
		int qid = 0;
		for (int i = 0; i < m; i++) {
			scanf("%s", cmd);
			if (cmd[0] == 'Q') {
				scanf("%d %d %d", &x, &y, &k);
				off.addEvent(2, qid++, x, y, k);
			} else {
				scanf("%d %d", &x, &v);
				off.addEvent(1, 0, x, A[x], 0);
				off.addEvent(0, 0, x, v, 0);
				A[x] = v;
			}
		}
		
		off.run();		
		for (int i = 0; i < qid; i++)
			printf("%d\n", off.ret[i]);
	}
	return 0;
}

Read More +

Jun 22 2015

解題區►解題區 - Zerojudge

b412. 記憶中的并查集

Problem

維護一個並查集的操作，並且支持版本回溯。

合併兩個堆
詢問兩個元素是否同堆
版本回溯

Sample Input

Sample Output

1
2
3

0
1
0

Solution

持久化概念，相當於維護 parent[] 陣列的版本，這一點可以利用可持久化線段樹來維護。

並查集的查詢功能不修改 parent[] 陣列，合併操作卻有可能修改數個 parent[]，為了降低記憶體用量，盡可能少用路徑壓縮這個技巧，雖然在一般並查集都會使用這個來加速，否則很容易變很慢，是因為持久化是會拉低速度，因為持久化需要 $O(\log N)$ 的時間去更改 parent[]，單筆路徑壓縮長度為 $M$ 個點，需要 $O(M \log N)$ 的調整，$M$ 在並查集中是常數類。

詢問不多時用啟發式合併就好，將小堆的元素合併到大堆中。效能會比較好。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
const int MAXN = 3000000;
class SegementTree {
public:
	struct Node {
		Node *lson, *rson;
	    pair<int, int> val;
	} nodes[MAXN];
	int nodesize, L, R;
	Node* init(int l, int r) {
		nodesize = 0;
		L = l, R = r;
		Node* root = build(l, r);
		return root;
	}
	Node* newNode() {
		if (nodesize >= MAXN)
			exit(0);
		return &nodes[nodesize++];
	}
	Node* cloneNode(Node *p) {
		if (nodesize >= MAXN)
			exit(0);
		Node* u = &nodes[nodesize++];
		*u = *p;
		return u;
	}
	Node* build(int l, int r) {
	    if (l > r)  return NULL;
	    Node *u = newNode();
	    u->lson = u->rson = NULL;
	    if (l == r) {
			u->val = make_pair(l, 1);
		} else {
			int m = (l + r)/2;
	    	u->lson = build(l, m);
	    	u->rson = build(m+1, r);
		}
	    return u;
	}
	Node* change(Node *p, int x, pair<int, int> val, int l, int r) {
		Node *u = cloneNode(p);
	    if (l == r) {
	    	u->val = val;
	    } else {
	    	int mid = (l + r)/2;
	    	if (x <= mid)
	        	u->lson = change(p->lson, x, val, l, mid);
	    	else
	     		u->rson = change(p->rson, x, val, mid+1, r);
	    }
	    return u;
	}
	Node* change(Node *p, int x, pair<int, int> val) {
		return change(p, x, val, L, R);
	}
	pair<int, int> find(Node *ver, int x, int l, int r) {
	    if (l == r)
	    	return ver->val;
	    int mid = (l + r)/2;
	    if (x <= mid)
	        return find(ver->lson, x, l, mid);
	    else
	        return find(ver->rson, x, mid+1, r);
	}
	pair<int, int> find(Node *ver, int x) {
	    return find(ver, x, L, R);
	}
	// disjoint set
	pair<int, int> findp(Node *ver, int x) {
		pair<int, int> p = find(ver, x);
		return x == p.first ? p : findp(ver, p.first);
	}
	Node* joint(Node *ver, int x, int y) {
		pair<int, int> a = findp(ver, x);
		pair<int, int> b = findp(ver, y);
		if (a.first == b.first)
			return ver;
		Node *u = ver;
		if (a.second > b.second) {
			u = change(u, b.first, make_pair(a.first, b.second));
			u = change(u, a.first, make_pair(a.first, a.second + b.second));
		} else {
			u = change(u, a.first, make_pair(b.first, a.second));
			u = change(u, b.first, make_pair(b.first, a.second + b.second));
		}
		return u;
	}
} segTree;
const int MAXQ = 262144;
SegementTree::Node *ver[MAXQ];
int main() {
	int n, m;
	int cmd, x, y, v;
	while (scanf("%d %d", &n, &m) == 2) {
		ver[0] = segTree.init(1, n);
		int encrypt = 0;
		for (int i = 1; i <= m; i++) {
			scanf("%d", &cmd);
			cmd ^= encrypt;
			if (cmd == 0) { 		// back
				scanf("%d", &v);
				v ^= encrypt;
				ver[i] = ver[v];
			} else if (cmd == 1) {	// joint
				scanf("%d %d", &x, &y);
				x ^= encrypt, y ^= encrypt; 
				ver[i] = segTree.joint(ver[i-1], x, y);
			} else if (cmd == 2) {	// find
				scanf("%d %d", &x, &y);
				x ^= encrypt, y ^= encrypt;
				pair<int, int> a = segTree.findp(ver[i-1], x);
				pair<int, int> b = segTree.findp(ver[i-1], y);
				int t = a.first == b.first;
				printf("%d\n", t);
				ver[i] = ver[i-1];
				encrypt = t;
			} else {
				puts("WTF");
				return 0;
			}
		}
	}
	return 0;
}

Read More +

Jun 22 2015

解題區►解題區 - Zerojudge

b411. 記憶中的序列 2

Problem

動態區間 K 小，有四種操作

插入元素
刪除元素
修改元素
版本回溯
詢問某個區間的第 K 小元素

Sample Input

Sample Output

1
2
3

2
1
2

Solution

每次操作最多增加 $O(\sqrt{n})$ 記憶體，需要針對節點作抽象化，修改節點時再進行實體化，如此一來不用針對搜索路徑上的每一節點都進行複製，一般持久化平衡樹進行時，會直接複製整個節點，但塊狀鏈表若是複製下去會退化成時間、空間都是 $O(n)$ 的情況。

詢問時仍然需要二分搜索答案，看答案是否符合 K 小元素，也就是說要得到某個元素在區間中的排名。

塊狀鏈表代碼很醜，看看就好。如果需要支持修改、增加元素的區間 K 小，雖然複雜度高，但常數小、記憶體快取優勢，速度不比二元樹類型的資料結構來得慢，不管需不需要持久化塊狀鏈表都是這類型不錯的選擇。

另解

假設詢問為 $Q$ 個，聽說可以用區間 $[1, 2NQ]$ 的線段樹之類的超大區間線段樹，必要的探訪時進行開花 (將子節點打開)，利用標記計算相對位置來進行查詢。相對位置計算大概會在邊緣情況崩潰。

至於柳柳州提到的替罪羊樹是樹套樹下去持久化，每一個節點表示一個區間，接著在節點中建造一個平衡樹來查找區間 K 小元素。這樣的做法一樣需要二分搜索答案。但塊狀鏈表在速度跟記憶體都贏了，因為樹套樹的常數比較大，增加的記憶體也多。

#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
const int MAXQ = 131072;
class UnrolledLinkedList {
public:
	struct Node {
		vector<int> A, B;
		Node *next, *alias;
		Node() {
			A.clear(), B.clear(), next = alias = NULL;
		}
		Node* real() {
			if (alias)	return alias;
			return this;
		}
		void insert(int x, int val) {
			if (alias) {
				A = alias->A, B = alias->B;
				alias = NULL;
			}
			A.insert(A.begin() + x, val);
			B.resize(A.size());
			B[A.size()-1] = val;
			for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
				swap(B[i], B[i-1]);
		}
		void erase(int x) {
			int val = A[x];
			A.erase(A.begin()+x);
			B.erase(lower_bound(B.begin(), B.end(), val));
		}
		void change(int x, int val) {
			int t = A[x];
			A[x] = val;
			B.erase(lower_bound(B.begin(), B.end(), t));
			B.resize(A.size());
			B[A.size()-1] = val;
			for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
				swap(B[i], B[i-1]);
		}
		void relax() {
			B = A;
			sort(B.begin(), B.end());
		}
	};
	int PSIZE;
	stack<Node*> mem;
	Node* init(int A[], int n) { // A[1:n]
		free();
		PSIZE = max((int) sqrt(n), 2);
		for (int i = 1; ; i <<= 1) {
			if (i >= PSIZE) {
				PSIZE = i;
				break;
			}
		}
		
		Node *u, *v, *head;
		
		head = newNode();
		u = head, v = NULL;
		for (int i = 1; i <= n; i++) {
			if (u->A.size() == PSIZE) {
				u->next = newNode();
				v = u, u = u->next;
			}
			u->A.push_back(A[i]);
		}
		for (u = head; u != NULL; u = u->next)
			u->relax();
		return head;
	}
	Node* newNode() {
		Node* p = new Node();
		mem.push(p);
		return p;
	}
	Node* cloneNode(Node *u) {
		Node *t = u->real();
		Node *p = new Node();
		*p = *t, p->next = u->next, mem.push(p);
		return p; 
	}
	Node* aliasNode(Node *u) {
		Node *t = u->real();
		Node* p = new Node();
		p->alias = t, p->next = u->next, mem.push(p);
		return p;
	}
	Node* erase(Node *ver, int x) {
		Node *a, *b, *u, *v, *t;
		u = ver, a = NULL;
		for (int l = 1, r; u; l = r+1, u = u->next) {
			r = l + u->real()->A.size() - 1;
			if (l <= x && x <= r) {
				t = cloneNode(u);
				if (a == NULL)
					a = t, b = a;
				else
					b->next = t, b = b->next;
				t->erase(x - l);
				t->next = u->next;
				break;
			} else {
				if (a == NULL)
					a = aliasNode(u), b = a;
				else
					b->next = aliasNode(u), b = b->next;
			}
		}
		return relaxList(a);
	}
	Node* insert(Node *ver, int x, int val) {
		Node *a, *b, *u, *v, *t;
		u = ver, a = NULL;
		for (int l = 1, r; u; l = r+1, u = u->next) {
			r = l + u->real()->A.size() - 1;
			if (l-1 <= x && x <= r) {
				t = cloneNode(u);
				if (a == NULL)
					a = t, b = a;
				else
					b->next = t, b = b->next;
				t->insert(x - l + 1, val);
				t->next = u->next;
				break;
			} else {
				if (a == NULL)
					a = aliasNode(u), b = a;
				else
					b->next = aliasNode(u), b = b->next;
			}
		}
		return relaxList(a);
	}
	Node* change(Node *ver, int x, int val) {
		Node *a, *b, *u, *v, *t;
		u = ver, a = NULL;
		for (int l = 1, r; u; l = r+1, u = u->next) {
			r = l + u->real()->A.size() - 1;
			if (l <= x && x <= r) {
				t = cloneNode(u);
				if (a == NULL)
					a = t, b = a;
				else
					b->next = t, b = b->next;
				t->change(x - l, val);
				t->next = u->next;
				break;
			} else {
				if (a == NULL)
					a = aliasNode(u), b = a;
				else
					b->next = aliasNode(u), b = b->next;
			}
		}
		return a;
	}
	int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
		Node *u, *v;
		int ret = 0;
		u = ver;
		for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
			r = l + u->real()->A.size() - 1;
			if (L <= l && r <= R) {
				ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
				L = r + 1;
			} else if ((l <= L && L <= r) || (l <= R && R <= r)) {
				int i = L - l;
				while (i < u->real()->A.size() && L <= R) {
					if (u->real()->A[i] <= val)
						ret++;
					i++, L++;
				}
			}
			if (ret >= threshold)	return ret;
		}
		return ret;
	}
	int find(Node *ver, int L, int R, int k)  {	// kth-number
		int l = 0, r = 100000, mid, t = 0; // value in A[]
		while (l <= r) {
			mid = (l + r)/2;
			if (findRank(ver, L, R, mid, k) >= k)
				r = mid - 1, t = mid;
			else
				l = mid + 1;
		}
		return t;
	}
	Node* mergeNode(Node *u, Node *v) {
		Node *p, *q;
		Node *a = newNode();
		p = u->real(), q = v->real();
		a->next = v->next;
		a->A.insert(a->A.end(), p->A.begin(), p->A.end());
		a->A.insert(a->A.end(), q->A.begin(), q->A.end());
		a->B.resize(a->A.size());
		merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
		return a;
	}
	Node* splitNode(Node *u) {
		Node *t = u->real();
		Node *a = newNode(), *b = newNode();
		int n = t->A.size()/2;
		a->next = b, b->next = u->next;
		a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
		b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
		a->relax(), b->relax();
		return a;
	}
	Node* relaxList(Node *ver) {
	    Node *a, *b, *u, *v, *t;
	    int need = 0;
		for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
	        if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
	        	need = 1;
	        if (u->real()->A.size() > (PSIZE<<1))	// split
	        	need = 1;
	    }
	    if (!need)
	    	return ver;
	    	
	    for (u = ver, a = NULL; u != NULL; u = u->next) {
	        if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
	        	if (a == NULL)
	        		a = mergeNode(u, u->next), b = a;
	        	else
	        		b->next = mergeNode(u, u->next), b = b->next;
				u = u->next;
	        } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
	        	if (a == NULL)
	        		a = splitNode(u), b = a->next;
	        	else
	        		b->next = splitNode(u), b = b->next->next;
	        } else {
	        	if (a == NULL)	
					a = aliasNode(u), b = a;
	        	else			
					b->next = aliasNode(u), b = b->next;
	        }
	    }
	    return a;
	}
	void debug(Node *head) {
		Node *u = head;
		printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
	}
	void free() {
		while (!mem.empty()) {
			Node *u = mem.top();
			mem.pop();
			delete u;
		}
	}
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
	int x, y, v, cmd;
	while (scanf("%d", &n) == 1) {
		for (int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
		int encrypt = 0;
		scanf("%d", &q);
		for (int i = 1; i <= q; i++) {
			scanf("%d", &cmd);
			cmd ^= encrypt;
			if (cmd == 0) {			// back version v
				scanf("%d", &v);
				v ^= encrypt;
				ver[i] = ver[v];
			} else if (cmd == 1) { 	// insert A[x] = v
				scanf("%d %d", &x, &v);
				x ^= encrypt, v ^= encrypt;
				ver[i] = dream.insert(ver[i-1], x, v);
			} else if (cmd == 2) {	// delete A[x]
				scanf("%d", &x);
				x ^= encrypt;
				ver[i] = dream.erase(ver[i-1], x);
			} else if (cmd == 3) {	// make A[x] = v
				scanf("%d %d", &x, &v);
				x ^= encrypt, v ^= encrypt;
				ver[i] = dream.change(ver[i-1], x, v);
			} else if (cmd == 4) {
				scanf("%d %d %d", &x, &y, &v);
				x ^= encrypt, y ^= encrypt, v ^= encrypt;
				int t = dream.find(ver[i-1], x, y, v);
				printf("%d\n", t);
				encrypt = t;
				ver[i] = ver[i-1];
			} else {
				puts("WTF");
				return 0;
			}
//			dream.debug(ver[i]);
		}
	}
	return 0;
}

Read More +

Jun 16 2015

解題區►解題區 - Zerojudge

b405. 記憶中的序列

Problem

給一個序列，支持插入元素、刪除元素、反轉區間、區間極值、區間總和、區間修改以及最重要的 版本回溯 。

題目輸入會拿上一個答案進行 XOR 的加密，

Sample Input

10
9 81 28 6 40 68 74 50 82 62 
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
85 82 89
14 13 13
56 61
57 57 40
58 61
59 61 63
60 57 59 4
61 58 49
137 139 136
37 38 42

decrypt input

10
9 81 28 6 40 68 74 50 82 62
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
6 1 10
7 4 4
0 5
1 1 16
2 5
3 5 7
4 1 3 60
5 2 9
6 4 7
7 4 8

Sample Output

Solution

持久化 treap，區間反轉，區間最大值，區間最小值，區間總和，插入元素，刪除元素，操作回溯。

這坑爹的題目描述擺明就是拖人下水，只好含淚地寫下去。持久化類型的題目應該是告一段落，就差一個 LCP + HASH 的維護了吧。麻煩的地方在於持久化的懶操作標記傳遞時都要新增加一個節點，這項舉動導致記憶體量非常多，1 秒處理的資訊吃掉 512 MB。二分記憶體上限，終於找到內存池的最多元素個數，中間不小心把多項資訊的 int 型態宣告成 long long，導致內存池一直不夠大。

如果不考慮回溯操作，速度上沒有比暴力算法來得快上很多，treap 基於隨機數的調整，而且每一次修改元素都要增加很多記憶體來補，導致速度上無法領先太多。但如果用暴力法，會造成版本回溯問題，空間會到 $O(
n^2)$，不允許的狀態，持久化造就的平均空間使用 $O(Q log N \times sizeof(Node))$，看起來仍然是很巨大的。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 7100000
#define MAXQ 60005
class PersistentTreap {
public:
    struct Node;
    static Node *null;
    struct Node {
        Node *lson, *rson;
        int key, size;
        long long val, mnval, mxval, sumval;
        long long adel; // delivery
        int rdel;
        
        Node(long long c = 0, int s = 1): size(s) {
            lson = rson = null;
            key = rand();
            val = mnval = mxval = sumval = c;
            adel = rdel = 0;
        }
        void update() {
            size = 1;
            size += lson->size + rson->size;
        }
        void pushUp() {
            mnval = mxval = sumval = val;
            if (lson != null) {
                mnval = min(mnval, lson->mnval + lson->adel);
                mxval = max(mxval, lson->mxval + lson->adel);
                sumval += lson->sumval + lson->adel * lson->size;
            }
            if (rson != null) {
                mnval = min(mnval, rson->mnval + rson->adel);
                mxval = max(mxval, rson->mxval + rson->adel);
                sumval += rson->sumval + rson->adel * rson->size;
            }
        }
        void pushDown(PersistentTreap &treap) {
            if (adel) {
                val += adel, mnval += adel, mxval += adel;
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->adel += adel;
                }
                if (rson != null) {
                	rson = treap.cloneNode(rson);
                    rson->adel += adel;
                }
                adel = 0;
            }
            if (rdel&1) {
                if (lson == null)
                    lson = rson, rson = null;
                else if (rson == null)
                    rson = lson, lson = null;
                else
                    swap(lson, rson);
                
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->rdel += rdel;
                } 
				if (rson != null) {
					rson = treap.cloneNode(rson);
                    rson->rdel += rdel;
                }
                rdel = 0;
            }
            pushUp();
        }
    } nodes[MAXN], *root[MAXQ];
    int bufIdx, verIdx;
    
    Node* merge(Node* a, Node* b) {
        if (a == null)	return cloneNode(b);
        if (b == null)	return cloneNode(a);
        if (a != null)	a->pushDown(*this);
    	if (b != null)	b->pushDown(*this);
        Node *ret;
        if (a->key < b->key) {
            ret = cloneNode(a);
            ret->rson = merge(a->rson, b);
        } else {
            ret = cloneNode(b);
            ret->lson = merge(a, b->lson);
        }
        ret->update();
        ret->pushUp();
        return ret;
    }
    void split(Node* a, Node* &l, Node* &r, int n) {
        if (n == 0) {
            l = null, r = cloneNode(a);
            return ;
        } 
		if (a->size <= n) {
            l = cloneNode(a), r = null;
            return ;
        }         
		if (a != null)
            a->pushDown(*this);
		if (a->lson->size >= n) {
            r = cloneNode(a);
            split(a->lson, l, r->lson, n);
            r->update();
            r->pushUp();
        } else {
            l = cloneNode(a);
            split(a->rson, l->rson, r, n - (a->lson->size) - 1);
            l->update();
            l->pushUp();
        }
    }
    
    void insert(Node* &a, Node *ver, int pos, long long s[], int sn) {
        Node *p, *q, *r;
        int n = sn;
        split(ver, p, q, pos);
        build(r, 0, n - 1, s);
        p = merge(p, r);
        a = merge(p, q);
    }
    void erase(Node* &a, Node *ver, int pos, int n) {
        Node *p, *q, *r;
        split(ver, p, q, pos - 1);
        split(q, q, r, n);
        a = merge(p, r);
    }
    void reverse(Node* &a, Node *ver, int left, int right) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->rdel++;
        a = merge(p, q);
        a = merge(a, r);
    }
    void add(Node* &a, Node *ver, int left, int right, long long val) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->adel += val;
        a = merge(p, q);
        a = merge(a, r);
    }
    long long q_sum, q_max, q_min;
    void q_dfs(Node *u, int left, int right) {
        left = max(left, 1);
        right = min(right, u->size);
        if (left > right)
            return;        
		if (u != null)
            u->pushDown(*this);
        int lsz = u->lson != null ? u->lson->size : 0;
        int rsz = u->rson != null ? u->rson->size : 0;
        if (left == 1 && right == lsz + rsz + 1) {
            q_sum += u->sumval;
            q_max = max(q_max, u->mxval);
            q_min = min(q_min, u->mnval);
            return ;
        }
        if (left <= lsz+1 && lsz+1 <= right) {
            q_sum += u->val;
            q_max = max(q_max, u->val);
            q_min = min(q_min, u->val);
        }
        
        if (u->lson != null && left <= lsz)
            q_dfs(u->lson, left, right);
        if (u->rson != null && right > lsz+1)
            q_dfs(u->rson, left - lsz - 1, right - lsz - 1);
    }
    void q_init() {
        q_max = LONG_LONG_MIN;
        q_min = LONG_LONG_MAX;
        q_sum = 0;
    }
    long long findMax(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_max;
    }
    long long findMin(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_min;
    }
    long long findSum(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_sum;
    }
    void print(Node *ver) {
        if (ver == null)	return;
        ver->pushDown(*this);
        print(ver->lson);
        printf("[%3lld]", ver->val);
        print(ver->rson);
    }
    void init() {
        bufIdx = verIdx = 0;
        root[verIdx] = null;
    }
private:
    Node* cloneNode(Node* u) {
        Node *ret;
        if (u == null) {
            return u;
        } else {
        	if (bufIdx >= MAXN)
        		exit(0);
            assert(bufIdx < MAXN);
            ret = &nodes[bufIdx++];
            *ret = *u;
            return ret;
        }
    }
    void build(Node* &a, int l, int r, long long s[]) {
        if (l > r)	return ;
        int m = (l + r) /2;
        Node u = Node(s[m]), *p = &u, *q;
        a = cloneNode(p), p = null, q = null;
        build(p, l, m-1, s);
        build(q, m+1, r, s);
        p = merge(p, a);
        a = merge(p, q);
        a->update();
        a->pushUp();
    }
} tree;
PersistentTreap::Node t(0, 0);
PersistentTreap::Node *PersistentTreap::null = &t;
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        tree.init();
        tree.insert(tree.root[0], tree.null, 0, A+1, N);
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            cmd ^= encrypt;
            if (cmd == 1) { 		// insert
                scanf("%lld %lld", &x, &v);
                x ^= encrypt, v ^= encrypt;
                long long B[] = {v};
                tree.insert(tree.root[i], tree.root[verIdx], (int) x, B, 1);
                verIdx = i;
            } else if (cmd == 2) { 	// erase
                scanf("%lld", &x);
                x ^= encrypt;
                tree.erase(tree.root[i], tree.root[verIdx], (int) x, 1);
                verIdx = i;
            } else if (cmd == 3) { 	// reverse
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                tree.reverse(tree.root[i], tree.root[verIdx], (int) x, (int) y);
                verIdx = i;
            } else if (cmd == 4) { 	// [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                tree.add(tree.root[i], tree.root[verIdx], (int) x, (int) y, v);
                verIdx = i;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMax(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMin(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ret = tree.findSum(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                x ^= encrypt;
                tree.root[i] = tree.root[x];
                verIdx = i;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}

Test Code

暴力法驗證用，不支持加密的輸入運行，用一個 vector 完成。

#include <bits/stdc++.h>
using namespace std;
#define MAXN (1<<19)
#define MAXQ 65536
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        vector< vector<long long> > L;
        L.push_back(vector<long long>(A+1, A+1+N));
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            vector<long long> TA = L[verIdx];
            if (cmd == 1) {         // insert
                scanf("%lld %lld", &x, &v);
                TA.insert(TA.begin()+x, v);
            } else if (cmd == 2) {  // erase
                scanf("%lld", &x);
                TA.erase(TA.begin()+x-1);
            } else if (cmd == 3) {  // reverse
                scanf("%lld %lld", &x, &y);
                reverse(TA.begin()+x-1, TA.begin()+y);
            } else if (cmd == 4) {  // [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                for (int i = (int) x-1; i < y; i++)
                    TA[i] += v;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MIN;
                for (int i = (int) x-1; i < y; i++)
                    ret = max(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MAX;
                for (int i = (int) x-1; i < y; i++)
                    ret = min(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = 0;
                for (int i = (int) x-1; i < y; i++)
                    ret += TA[i];
                printf("%lld\n", ret);
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                TA = L[x];
            } else {
                puts("WTF");
                return 0;
            }
            L.push_back(TA), verIdx = i;
            printf("version %d\n", i);
            for (auto &x: TA)
                printf("[%3lld]", x);
            puts("");
        }
    }
    return 0;
}

Test Generator

小測資檢驗用

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
	 srand (time(NULL));
	int testcase, n, m, x, y;
    int A[100];
	testcase = 1;
	freopen("in.txt", "w+t", stdout);
//    printf("%d\n", testcase);
	while (testcase--) {
        n = 32;
        printf("%d\n", n);
        for (int i = 0; i < n; i++) {
            printf("%d%c", rand(), i == n-1 ? '\n' : ' ');
        }
        m = 1000;
        printf("%d\n", m);
        vector<int> L;
        L.push_back(n);
        for (int i = 1; i <= m; i++) {
            while (true) {
                int cmd = rand()%8;
                if (n == 1 && cmd == 2)
                    continue;
                if (cmd == 0) {
                	int x = rand()%i;
                	printf("%d %d\n", cmd, x);
                	n = L[x];
                }
                if (cmd == 1)
                    printf("%d %d %d\n", cmd, rand()%(n+1), rand()), n++;
                if (cmd == 2)
                    printf("%d %d\n", cmd, rand()%n+1), n--;
                if (cmd == 3) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                if (cmd == 4) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d %d\n", cmd, x, y, rand());
                }
                if (cmd == 5 || cmd == 6 || cmd == 7) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                break;
            }
            L.push_back(n);
        }
	}
	return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b327. 學姊日談

內容：

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

輸入說明：

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

輸出說明：

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行，保證總和可以在 signed 32 bits 內。

範例輸入：

範例輸出：

Solution 1

先將一棵樹壓平，壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後，每個節點對應一個左右括弧位置，當我們增加節點 v 權重時，相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

操作 [l, r]：將區間內的所有數字加上 k
詢問 x：詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整，單點詢問。

對於 ADD [l, r] k 時，相當於 BIT[l] += k, BIT[r+1] -= k，單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
struct Tree {
	vector<int> g[MAXN];
	int root;	
	void init(int n) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		root = 0;
	}
	void addEdge(int x, int y) {
		g[x].push_back(y);
		g[y].push_back(x);
	}
} tree;
int bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
	bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
	for (int i = 0; i < tree.g[u].size(); i++) {
		int v = tree.g[u][i];
		if (v == p)	continue;
		prepare(v, u);
	}
	ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
    while (x <= N) {
        bitTree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += bitTree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
	int n, q, x, y;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		tree.init(n);
		
		int on[MAXN] = {};
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree.addEdge(x, y);
		}
		
		inIdx = 0;
		prepare(tree.root = 0, -1);
		memset(bitTree, 0, sizeof(bitTree));
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d %d", &x, &y);
			modify(bPos[x], inIdx, y);
            modify(ePos[x] + 1, inIdx, -y);
			printf("%d\n", query(bPos[x]));
		}
		puts("");
	}
	return 0;
}

Solution 2

這個解法直接使用樹鏈剖分，樹鏈剖分將子樹節點數量最大的當作重邊，其餘皆為輕邊。將以重邊相連的所有節點，看似一個鏈狀，當作一個 1D Array 看待。

保證每個點爬到 root，只會經過 log n 的輕邊，而中間鏈狀處理，可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法，詢問效率 O(log^2 n)，調整 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
	int p, pPos;
	vector<int> A;
	vector<int> BIT;
	void init() {
		A.clear(), BIT.clear();
		p = -1;
	}
} nodes[262144];
struct Tree {
	vector<int> g[MAXN];
	int root;	
	void init(int n) {
		for (int i = 0; i < n; i++)
			g[i].clear();
		root = 0;
	}
	void addEdge(int x, int y) {
		g[x].push_back(y);
		g[y].push_back(x);
	}
} tree;
int prepare(int u, int p) {
	int sz = 1, mx = 0, hedge = -1;
	int v, t;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i], t;
		if (v == p)	continue;
		sz += (t = prepare(v, u));
		if (mx < t)
			mx = t, hedge = v;
	}
	hNext[u] = hedge;
	return sz;
}
void build(int u, int p) {	
	if (used[u] == 0) {
		Node &nd = nodes[++nodesize];
		nd.init();
		for (int i = u; i != -1; i = hNext[i]) {
			used[i] = 1;
			iNode[i] = nodesize, aPos[i] = nd.A.size();
			nd.A.push_back(i);
		}
		nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
		if (p != -1)	nd.p = iNode[p], nd.pPos = aPos[p];
	}
	int v;
	for (int i = 0; i < tree.g[u].size(); i++) {
		v = tree.g[u][i];
		if (v == p)	continue;
		build(v, u);
	}
}
int queryBIT(vector<int> &BIT, int x) {
	int ret = 0;
	while (x)
		ret += BIT[x], x -= x&(-x);
	return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
	while (x <= L)
		BIT[x] += val, x += x&(-x);
}
void search(int u) {
	int sum = 0;
	set< pair<int, int> >::iterator it, jt;
	for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
		sum += queryBIT(nodes[i].BIT, in + 1);
	printf("%d", sum);
	puts("");
}
void modify(int u, int val) {
	Node &nd = nodes[iNode[u]];
	int pos = aPos[u];
	modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
	int n, q, x, y;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		tree.init(n);
		
		int on[MAXN] = {};
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree.addEdge(x, y);
		}
		
		prepare(tree.root = 0, -1);
		memset(used, 0, sizeof(used));
		nodesize = 0;
		build(tree.root = 0, -1);
		
		scanf("%d", &q);
		for (int i = 0; i < q; i++) {
			scanf("%d %d", &x, &y);
			modify(x, y);
			search(x);
		}
		puts("");
	}
	return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b322. 樹形鎖頭

內容：

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

輸入說明：

輸入有多組測資。

每一組測資第一行會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

輸出說明：

每組測資輸出一行，分別將節點權重輸出。

範例輸入：

範例輸出：

1	5 3 5 3 2 4 8

Solution

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
int visited[32767];
vector<int> tree[32767];
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
		int v = tree[u][i];
    	if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
	int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
		int v = tree[u][i];
    	if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	int n, m, x, y, u, v, k;
	int X[32767], Y[32767], K[32767];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			tree[i].clear();
		for (int i = 1; i < n; i++) {
			scanf("%d %d", &x, &y);
			tree[x].push_back(y);
			tree[y].push_back(x);
		}
		
		int weight[32767] = {}, extra[32767] = {};
		for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &X[i], &Y[i], &K[i]);
			Q[X[i]].push_back(make_pair(i, Y[i]));
        	Q[Y[i]].push_back(make_pair(i, X[i]));
		}
		tarjan(0, -1);
		for (int i = 0; i < m; i++) {
			extra[LCA[i]] += K[i];
			weight[X[i]] += K[i];
			weight[Y[i]] += K[i];
			weight[LCA[i]] -= 2 * K[i];
		}
		dfs(0, -1, weight);
		for (int i = 0; i < n; i++)
			printf("%d%s", weight[i] + extra[i], i == n-1 ? "" : " ");
		puts("");
	}
	return 0;
}

Read More +

Oct 17 2014

解題區►解題區 - Zerojudge

b321. 河道分界

內容：

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

輸入說明：

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

輸出說明：

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

範例輸入：

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

範例輸出：

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

Solution

建造一個 BST，這裡使用內建 std::set 的紅黑樹，查找 lower_bound 即可。如果是靜態的河道，一開始對其排序即可，然後二分查找 lower_bound。

如果測資有錯，歡迎打我。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct seg {
	Pt s, e;
	int label;
	seg(Pt a, Pt b):s(a), e(b) {}
};
struct CMP {
	static double y;
	
	double interpolate(const Pt& p1, const Pt& p2, double& y) {
        if (p1.y == p2.y) return p1.x;
        return p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (y - p1.y);
    }
    
	bool operator()(const seg &i, const seg &j) {
		double v1 = interpolate(i.s, i.e, y), v2 = interpolate(j.s, j.e, y);
		if (fabs(v1 - v2) > eps)
			return v1 < v2;
		return false;
	}
};
double CMP::y = 0;
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
	int n;
	double x, y, up, down;
	char cmd[10];
	while (scanf("%d", &n) == 1) {
		set<seg, CMP> S;
		for (int i = 0, k = 1; i < n; i++) {
			scanf("%s", cmd);
			if (cmd[0] == 'A') {
				scanf("%lf %lf", &up, &down);
				seg tmp = seg(Pt(up, 1), Pt(down, 0));
				tmp.label = k;
				S.insert(tmp), k++;
			} else {
				scanf("%lf %lf", &x, &y);
				CMP::y = y;
				set<seg>::iterator it = S.lower_bound(seg(Pt(x, 1), Pt(x, 1))), jt;
				if (it != S.end()) {
					if (onSeg(it->s, it->e, Pt(x, y))) {
						puts("[?, ?]");
						continue;
					}
				}
				int l = -1, r = -1;
				if (it != S.begin()) {
					jt = it, jt--;
					l = jt->label;
					if (onSeg(jt->s, jt->e, Pt(x, y))) {
						puts("[?, ?]");
						continue;
					}
				}
				if (it != S.end())
					r = it->label;
				if (l == -1)
					printf("[S, ");
				else
					printf("[%d, ", l);
				if (r == -1)
					printf("M]");
				else
					printf("%d]", r);
				puts("");
			}
		}
	}
	return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b317. 紅圓茵可的野望

內容：

紅圓茵可最近隱居在板擦山研究魔法師的夢想，傳說中的魔法－「召喚蘿莉」。
只要成功練就這個魔法，茵可就可以召喚出一堆蘿莉，然後跟一堆蘿莉一起……嘿嘿嘿…..
目前茵可已經研究出N種可能可以成功魔法陣，接下來就是要測試這些魔法陣能不能成功召喚蘿莉，因為數量實在太多了，所以他決定先測試其中K種。為了測試魔法陣，茵可需要先開一個異次元空間，並且在裡面做測試(因為召喚蘿莉是個極大的魔法，發動時可能會造成空間扭曲，不小心毀掉可茵城就不好了。)。魔法陣都是圓形的，半徑為r，發動一個魔法陣需要以魔法陣為底高度為h的圓柱體空間。而茵可只能開出長方體的異次元空間，一個異次元空間有其長、寬、高，而魔法陣只能放置在該空間的地板上(長 x 寬那一面)，所以要發動一個半徑為r，高度為h的魔法陣，茵可需要開一個長2r寬2r高h的異次元空間(體積2r x 2r x h)。現在茵可想要開一個異次元空間，而這個空間至少要能發動K個魔法陣(不必同時發動)，這個空間的體積至少是多少。

輸入說明：

第一行有兩個正整數 N,K(K<=N)
接下來N行每行有兩個正整數r,h代表一個魔法陣的半徑及發動需要高度(r,h<=100)

測資

N<=100
N<=100
N<=100
N<=100000
N<=100000

輸出說明：

輸出要發動其中K個魔法陣所需最小的異次元空間的體積是多少

範例輸入：

範例輸出：

提示：

範測所需體積為 224=16

可發動第1、2、5個魔法陣

Solution

這一題有兩種做法，直接窮舉 O(100 * 100) 的針對 [r, h] 找到 [0, r] x [0, h] 的數量是否大於 K，那麼可以在線性時間內完成。

而下面的做法，算是多此一步，原本想說能不能用 O(n log n) 時間內完成，但是會缺少部分調整資訊，也就是單純排序，以掃描線的基準會漏到資訊。

如果這一題的 r, h 很大的話，窮舉還是會耗費 O(n^2 log n)，套用當前最佳解剪枝應該快上很多。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int BIT[256];
int query(int x) {
	int ret = 0;
	for (; x; x -= x&(-x))
		ret += BIT[x];
	return ret;
}
void modify(int x, int L) {
	for (; x <= L; x += x&(-x))
		BIT[x]++;
}
int main() {
	int N, K, r, h, w;
	while (scanf("%d %d", &N, &K) == 2) {
		vector<pair<int, int> > D;
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &r, &h);
			assert(r <= 100 && h <= 100 && r > 0 && h > 0);
			D.push_back(make_pair(r * 2, h));
		}
		int ret = 0x3f3f3f3f;
		sort(D.begin(), D.end());
		memset(BIT, 0, sizeof(BIT));
		for (int i = 0; i < N; i++) {
			modify(D[i].second, 255);
			for (int j = D[i].second; j <= 100; j++) {
				int q = query(j);
				w = D[i].first, h = j;
				if (q >= K)
					ret = min(ret, w*w*h);
			}
		}
		if (K == 0)	ret = 0;
		printf("%d\n", ret);
	}
	return 0;
}

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b316. 紅圓茵可的消失

內容：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

N<=10,K<=100
N<=10,K<=100
N<=1000,K<=1000
N<=1000,K<=1000000000，整張圖為一棵樹
N<=1000,K<=1000000000

輸出說明：

輸出第K天時茵可會走到哪個點。

範例輸入：

範例輸出：

提示：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式 $cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
	int N, M, K;
	int x, y;
	while (scanf("%d %d %d", &N, &M, &K) == 3) {
		for (int i = 0; i < N; i++)
			g[i].clear();
		for (int i = 0; i < M; i++) {
			scanf("%d %d", &x, &y);
			if (x > y)	swap(x, y);
			g[x].push_back(y);
		}
		for (int i = 0; i < N; i++)
			sort(g[i].begin(), g[i].end());
		int pass[1024] = {};
		int now = 0, x, sum = 0;
		pass[0] = --K;
		for (int i = 0; i < N; i++) {
			if (g[i].size() == 0)	continue;
			int u = i, v, div = pass[u] % g[i].size();
			for (int j = 0; j < g[i].size(); j++) {
				v = g[i][j];
				pass[v] += pass[u] / g[i].size();
				if (j < div)
					pass[v]++;
			} 
		}
		for (; g[now].size(); ) {
			x = pass[now]%g[now].size();
			now = g[now][x];
//			printf("-> %d\n", now);
		}
		printf("%d\n", now);
	}
	return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/

Read More +

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

前言

開始

應用

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

另解

Problem

Sample Input

Sample Output

Solution

Test Code

Test Generator

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution 1

Solution 2

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：