Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề cấu trúc dữ liệu nâng cao

  • Số trang: 27 |
  • Loại file: PDF |
  • Lượt xem: 1356 |
  • Lượt tải: 0

Mô tả:

CHUYÊN ĐỀ: CẤU TRÚC DỮ LIỆU NÂNG CAO Đặng Tuấn Thành Trường THPT Chuyên Nguyễn Tất Thành, tỉnh Yên Bái Interval Tree là công cụ rất hữu dụng được sử dụng nhiều trong các bài toán trên dãy số, hoặc được quy về các bài toán xử lí trên dãy số, đặc biệt là các bài toán có nhiều công việc cần xử lí và nhiều truy vấn xen kẽ nhau. Phần lí thuyết về Interval Tree đã được trình bày rất rõ ràng ở nhiều tài liệu do các chuyên gia, đồng nghiệp dạy bồi dưỡng học sinh giỏi chia sẻ, nên tôi mạn phép không đề cập tại đây. Do năng lực có hạn nên tôi không viết hoặc nghĩ ra những bài tập mới mà có sử dụng Interval Tree để giải được. Vì thế, trong chuyên đề này thực chất là các bài tập tôi sưu tầm, biên tập thành tập tài liệu để phục vụ trong công tác giảng dạy bồi dưỡng HSG môn Tin học. Ở đây, tôi trích dẫn các bài tập nguồn từ SPOJ, Codeforce và nhiều nguồn khác. Với mỗi bài tập tôi đề cập đến ba vấn đề:  Tóm tắt đề bài rõ ràng  Thuật toán tốt  Code demo (nếu có). Khi áp dụng tài liệu này vào giảng dạy, tôi thường bỏ phần “code demo” để không “làm hỏng học sinh”, chỉ phát đề cho học sinh. Với mỗi bài tập, sau khi học sinh nghiên cứu và đề xuất ý tưởng (hoặc code nộp mà chưa AC), tôi dẫn dắt, đưa ra giải thuật của bài toán đó để học sinh “ngấm” bài toán hơn. Dần dần học sinh nắm được tư tưởng Interval Tree và ứng dụng linh động vào các bài toán khác. Tôi cũng xin trích dẫn các tài liệu tôi tham khảo để biên tập thành chuyên đề này:  http://laptrinh.ntu.edu.vn/Problem/List  http://codeforces.com/problemset  http://vn.spoj.com/problems/oi/  https://onlylove97.wordpress.com/category/it/  https://doraemonvodanh.wordpress.com/category/thuat-toan/segment-tree/baitap-interval-tree/ 1  Quyển: Một số vấn đề chú ý môn Tin học – Nhóm tác giả của Đại học Vinh 2 Ứng dụng Interval Tree để giải các bài toán sau: Bài 1. Phần tử thứ K http://vn.spoj.com/problems/YPKTH/ Cho dãy số A có N phần tử nguyên phân biệt. Cho Q truy vấn, mỗi truy vấn có dạng: L R K Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử AL, AL+1, …, AR theo thứ tự tăng dần. Giới hạn: 1 ≤ N, Q ≤ 105 |Ai| ≤ 109 với 1 ≤ i ≤ N 1≤L≤R≤N 1 ≤ K ≤ R-L+1 Input: - Dòng đầu tiên chứa số N. - Dòng tiếp theo chứa N số A1, A2, …, AN. - Dòng tiếp theo chứa số Q. - Q dòng tiếp theo, mỗi dòng chứa 3 số L, R, K. Output: Q dòng, mỗi dòng chứa câu trả lời cho một truy vấn theo thứ tự nhập vào. Ví dụ: Input Output 7 2 2154368 6 4 4 122 3 374 462 551 Thời gian chạy: 1s-3s THUẬT TOÁN : 3 Dùng Segment Tree với mỗi nút lưu lại dãy con từ l->r đã được sort. Dùng vector cho mỗi nút để giảm bộ nhớ: mỗi nút sẽ xuất hiện logN lần trên cây, do đó bộ nhớ là NlogN. Có thể tạo cây trong O(NlogN), mỗi lần hợp hai nút con lại ta trộn hai đoạn con trong O(n+m) với n, m là kích thước của hai đoạn con. Với mỗi truy vấn ta làm như sau: Xét các giá trị (gọi là res) có trong dãy bằng cách chặt nhị phân, (nút 1 thực chất đã sort dãy tăng dần nên có thể chặt nhị phân trên nút 1), đếm xem trong đoạn l..r có bao nhiêu phần tử nhỏ hơn nó, nếu nhỏ hơn k tức là phải tìm số lớn hơn nữa và tương tự. Với mỗi lần truy vấn l..r thì ta lại chặt nhị phân những nút nằm trong đoạn l..r để tìm phần tử lớn nhất ≤ res đồng thời kiểm tra xem res có mặt cũng như đếm số lượng phần tử nhỏ hơn res (Chú ý là các phần tử là phân biệt). Điều kiện để res là nghiệm chính là cnt == k-1 (cnt là số lượng số < res) và tìm thấy res trong đoạn l..r. Code demo: http://ideone.com/GTScHq #include using namespace std; typedef long long ll; typedef int64_t ll; typedef pair ii; #define EL printf("\n") #define pb push_back #define mp make_pair #define X first #define Y second typedef vector data; const int N = 100100; int n, q, a[N], L, R, k, res, cnt, f; data t[4*N], nil; data combine(data u, data v) { data ans = nil; int i = 0, j = 0; while (i < u.size() and j < v.size()) { if (u[i] < v[j]) ans.pb(u[i++]); else ans.pb(v[j++]); } while (i < u.size()) ans.pb(u[i++]); while (j < v.size()) ans.pb(v[j++]); return ans; } void build(int k, int l, int r) void get(int node, int l, int r) { if (r < L or R < l) return ; if (L ≤ l and r ≤ R) { int i = 0, j = t[node].size()-1, pos = -1; while (i ≤ j) { int mid = (i+j)/2; if (t[node][mid] ≤ res) { pos = mid; i = mid+1; } else j = mid-1; } if (pos == -1) return ; if (t[node][pos] == res) f = true; cnt += pos + 1; if (t[node][pos] == res) cnt--; return ; } int mid = (l+r)/2; get(node*2,l,mid); get(node*2+1,mid+1,r); } int main() { //freopen("YPKTH.INP","r",stdin); //freopen("YPKTH.OUT","w",stdout); scanf("%d", &n); 4 { for (int i=1;i≤n;i++) scanf("%d", &a[i]); build(1,1,n); scanf("%d", &q); while (q--) { scanf("%d%d%d", &L,&R,&k); int l = 0, r = t[1].size()-1; while (l ≤ r) { int mid = (l+r)/2; res = t[1][mid]; cnt = 0; f = 0; get(1,1,n); if (cnt == k-1 and f) { printf("%d\n", res); break; } if (cnt < k) l = mid+1; else r = mid-1; } } return 0; if (l == r) { t[k].pb(a[l]); return ; } int mid = (l+r)/2; build(k*2, l, mid); build(k*2+1, mid+1, r); t[k] = combine(t[k*2], t[k*2+1]); } } Bài 2. Đoạn con có tổng lớn nhất http://vn.spoj.com/problems/GSS/ Cho dãy số a[1], a[2], ..., a[n] (|a[i]| ≤ 15000, n ≤ 50000). Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x ≤ i ≤ j ≤y }. Cho m câu hỏi dạng x, y (1 ≤ x ≤ y ≤ n), (m ≤ 50000) -> hãy tính các q(x, y). Input - Dòng đầu là n. - Dòng thứ hai là dãy a. - Dòng thứ 3 là m. - m dòng tiếp theo mỗi dòng là 1 cặp số x, y. Output Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng. Example Input: 3 -1 2 3 1 12 5 Output: 2 Thời gian chạy: 0.100s Thuật toán: Sử dụng Segment Tree Một nút lưu các giá trị : sum : tổng đoạn pre : tổng lớn nhất của đoạn tiền tố suf : tổng lớn nhất của đoạn hậu tố ans : tổng lớn nhất của đoạn Công thức hợp hai nút trên cây như sau : res.sum = l.sum + r.sum; res.pre = max(l.pre, l.sum + r.pre); res.suf = max(r.suf, r.sum + l.suf); res.ans = max(l.ans, r.ans, l.suf + r.pre); Code demo: #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include data make_data (int x) { data res; res.sum = x; res.pre = res.suf = res.ans = x; return res; } void make_tree(int k, int l, int r) { if (l == r) { t[k] = make_data(a[l]); return ; } int mid = (l+r)/2; make_tree(k*2, l, mid); make_tree(k*2+1, mid+1, r); using namespace std; t[k] = combine(t[k*2], t[k*2+1]); typedef long long ll; typedef int64_t ll; typedef double real; } data query(int k, int l, int r, int L, int R) 6 { const const const const int int ll real base = 1000000007; oo = INT_MAX; ooo = LONG_LONG_MAX; pi = acos(-1.0); if (l == L and r == R) return t[k]; int mid = (l+r)/2; if (R ≤ mid) return query(k*2, l, mid, L, R); #define openf {freopen("INP.INP","r",stdin);freopen("OU T.OUT","w",stdout);} #define closef {fclose(stdin);fclose(stdout);} #define readln scanf("\n") #define writeln printf("\n") if (L > mid) return query(k*2+1, mid+1, r, L, R); return combine ( query(k*2, l, mid, L, mid), query(k*2+1, mid+1, r, mid+1, R) ); //--------------------------------------------------// } struct data { int sum, pre, suf, ans; }; int main() { //openf; const int maxn = 100000, maxt = 4*maxn; int n, a[maxn], m, L, R; data t[maxt]; data combine (data l, data r) { data res; res.sum = l.sum + r.sum; res.pre = max(l.pre, l.sum + r.pre); res.suf = max(r.suf, r.sum + l.suf); res.ans = max( max(l.ans, r.ans), l.suf + r.pre); return res; } scanf("%d", &n); for (int i=1;i≤n;i++) scanf("%d", &a[i]); make_tree(1,1,n); scanf("%d", &m); while (m--) { scanf("%d%d",&L,&R); printf("%d\n",query(1,1,n,L,R).ans); } //closef; return 0; } Bài 3. Diện tích hình chữ nhật - http://vn.spoj.com/problems/AREA/ Trên mặt phẳng toạ độ người ta vẽ ra N hình chữ nhật. Hãy tính diện tích che phủ bởi N hình chữ nhật này, biết rằng N hình chữ nhật này song song với 2 trục Ox và Oy . Input Dòng 1 : Số nguyên N ( 1 ≤ N ≤ 10000 ). N dòng tiếp theo, mỗi dòng gồm 4 số nguyên x1, y1, x2, y2 tương ứng là toạ độ góc trái dưới và góc phải trên của hình chữ nhật thứ i.( 0 ≤ x1 ≤ x2 ≤ 30000, 0 ≤ y1 ≤ y2 ≤ 30000 ). 7 Output Gồm 1 dòng ghi ra diện tích phủ bởi N hình chữ nhật Example Input: 2 10 10 20 20 15 15 25 30 Output: 225 Thời gian chạy: 0.100s Thuật toán: Sử dụng Segment Tree (IT). Chuyển dữ liệu đề cho sang một dãy tọa độ x, mỗi x có lưu lại y1 và y2 tương ứng hàng giới hạn dưới và trên, đồng thời lưu lại type là -1 hay 1 tương ứng là cạnh đóng hay mở. Sau đó sort lại mảng này theo x. Mục đích của cách xử lí trên là tại mỗi khoảng từ xi -> xi+1 xét trên dãy đã sort ta đi tính phần diện tích được bao phủ bởi các y1 và y2. Lúc này ta dùng Segment Tree, mỗi nút lưu lại cnt là số lượng đoạn phủ và len là tổng chiều dài. Code demo: http://ideone.com/tGGNUI #include #include #include #include #include #include #include #include #include #include #include #include #include #include void update(int k, int l, int r, int L, int R, int type) { if (r < L or R < l) return ; if (L ≤ l and r ≤ R) { t[k].cnt += type; if (type == 1) // them hcn nen bao phu ca canh nay t[k].len = (r-l+1); // chang han l = 5, r = 8 thi t[k].len = 4 do (5,6,7,8) else { // truong hop xoa thi phai lay thong tin tu node con if (t[k].cnt == 0) t[k].len = t[k*2].len + t[k*2+1].len; } 8 return ; } int mid = (l+r)/2; update(k*2,l,mid,L,R,type); update(k*2+1,mid+1,r,L,R,type); if (t[k].cnt == 0) t[k].len = t[k*2].len + t[k*2+1].len; using namespace std; typedef long long typedef int64_t typedef double ll; ll; real; //-------------------------------------// } struct Node { int x, y1, y2, type; }; int main() { //freopen("INP.INP","r",stdin); struct Tree { //freopen("OUT.OUT","w",stdout); int len, cnt; scanf("%d", &n); }; for (int i=1;i≤n;i++) { int x1, y1, x2, y2; //-----------------------------------// scanf("%d%d%d%d", &x1,&y1,&x2,&y2); const int N = 30010; a[i].x = x1; int n, x0; // x0 la vi tri cuoi cung dang a[i+n].x = x2; xet a[i].y1 = a[i+n].y1 = y1; ll res; a[i].y2 = a[i+n].y2 = y2; Node a[N]; a[i].type = 1; Tree t[5*N]; // luu ve phuong dien do a[i+n].type = -1; dai, khong phai toa do (*) } //------------------------------------// n *= 2; sort(a+1,a+n+1,cmp); bool cmp(const Node u, const Node v) { //for (int i=1;i≤n;i++) return (u.x < v.x or (u.x == v.x and u.type // printf("%d %d %d %d\n", a[i].x, a[i].y1, < v.type)); a[i].y2, a[i].type); } for (int i=1;i≤n;i++) { //cout << (a[i].x-x0)*(t[1].len) << endl; res += (a[i].x - x0) * (t[1].len); x0 = a[i].x; update(1,0,N, a[i].y1, a[i].y2-1, a[i].type); // a[i].y2-1 la do (*) } cout << res; return 0; } Bài 4. http://vn.spoj.com/problems/CRATE/ Cho danh sách N lập trình viên (1 ≤ N ≤ 300000), đánh số lần lượt từ 1 đến N. Mỗi người đều tham gia cả hai giải thi đấu: Giải THPT và giải Mở rộng. Với mỗi lập trình viên, bạn sẽ được cung cấp điểm số của giải Mở rộng Ai và điểm số của giải THPT Hi (Các điểm số đều là số nguyên không âm và không vượt quá 100000). Lập trình 9 viên i được coi là giỏi hơn lập trình viên j khi và chỉ khi cả 2 điểm số của lập trình viên i đều lớn hơn hoặc bằng điểm số tương ứng của lập trình viên j, trong đó có ít nhất 1 điểm số phải lớn hơn. Hãy tính xem với mỗi lập trình viên i thì có bao nhiêu lập trình viên mà i giỏi hơn. Input Dòng đầu tiên chứa số nguyên N. N dòng tiếp theo, dòng thứ i+1 chứa 2 số nguyên Ai và Hi. Output Dòng i chứa số lượng lập trình viên mà lập trình viên i giỏi hơn. Example Input: 8 1798 1832 862 700 1075 1089 1568 1557 2575 1984 1033 950 1656 1649 1014 1473 Output: 6 0 2 4 7 1 5 1 Thuật toán: Ở bài này, giới hạn của bài toán khá lớn (300000) nên nếu dùng N log N thì cũng còn nguy hiểm. Chú ý giới hạn của số điểm là 0..100000 nên ta sẽ xử lí trên số điểm. + Tạo một danh sách các thông tin của từng người: struct(C++) ds gồm d1,d2 là điểm lần 1 và 2, vt là vị trí ban đầu của nó. Mảng A sẽ lưu danh sách này. 10 + Tạo một mảng res sẽ chứa mảng cần xuất ra khi đã thực hiện xong chương trình. Cách tạo res là for i = 1 -> n rồi lưu res[a[i].vt] = giá trị tìm được của thằng a[i].vt (vị trí ban đầu của nó). Sau đó xuất ra theo thứ tự trong res. + Tạo một cây IT là mảng t[k] lưu thông tin của nút k quản lí đoạn l..r (xét trên số điểm) và một mảng f lưu nghiệm của bài toán, tức là f[i] là số lượng những thằng tồi hơn thằng i sau khi đã sort lại. + Tạo thêm biến m lưu số điểm d2 lớn nhất vì theo như tài liệu d1 ta đã sort lại rồi thì không cần quan tâm điểm lớn hay nhỏ. + Sau khi nhập dữ liệu thì sort lại dãy. + Tạo biến q là vị trí đang duyệt trên dãy a ( từ 1 -> n, lần lượt xét các đoạn có cùng d1). Khi q > n thì xuất nghiệm ra, halt luôn. trước hết q = 0. + Tạo biến L và R lưu đoạn xét nói trên. Khi đó ban đầu L = q và R = q. lần lượt tăng R lên đến khi d1 thay đổi. Xong thì xét đoạn L..R mới tìm được. + Khởi tạo f[L] = 0. Tạo f. + Sau đó lấy giá trị cho f trên cây t (nhớ là xét trên số điểm từ 0..m, đoạn ban đầu findans) : điểm đang xét là x. Ta sẽ tìm những đoạn mà r ≤ x để lấy ans còn những đoạn nào mà x < l ( điểm thấp hơn ) thì ta bỏ qua. Trường hợp còn lại thì chia ra 2 đoạn mà làm như các bài IT cơ bản. + Lấy giá trị xong thì cập nhật lại cây t: bỏ qua những đoạn x không thuộc, tăng số lượng nút này lên, nếu l = r thì thôi. chia hai đoạn để it. + q = R. + Duyệt Code demo: #include #include #include #include #include #include using namespace std; struct ds { int d1,d2,vt; }; bool compare(const ds u, const ds v) { if (u.d1 < v.d1) return true; if (u.d1 == v.d1 and u.d2 < v.d2) return true; return false; } int main(){ scanf("%d",&n); for (int i=1;i≤n;i++) { scanf("%d%d",&a[i].d1,&a[i].d2); a[i].vt = i; 11 const int maxn = 300010, maxt = maxn*4 + 1; int n,m,q,L,R; ds a[maxn]; int t[maxt],f[maxn],res[maxn]; void findans(int k, int l, int r, int x, int &ans) { if (x < l) return; if (r ≤ x) { ans += t[k]; return; } int m = (l+r)/2; findans(k*2,l,m,x,ans); findans(k*2+1,m+1,r,x,ans); } void update(int k, int l, int r, int x) { if (x < l or r < x) return; t[k]++; if (l == r) return; int m = (l+r)/2; update(k*2,l,m,x); update(k*2+1,m+1,r,x); } m = max(m,a[i].d2); } //-------------------------------------// sort(a+1,a+n+1,compare); q = 0; while (1 == 1) { q++; if (q > n) { for (int i=1;i≤n;i++) res[a[i].vt] = f[i]; for (int i=1;i≤n;i++) printf("%d\n",res[i]); return 0; } L = q; R = q; while (R < n and a[R].d1 == a[R+1].d1) R++; f[L] = 0; for (int i=L+1;i≤R;i++) if (a[i].d2 ≤ a[i-1].d2) f[i] = f[i-1]; else f[i] = i - L; for (int i=L;i≤R;i++) { int ans = 0; findans(1,0,m,a[i].d2,ans); f[i] += ans; } for (int i=L;i≤R;i++) update(1,0,m,a[i].d2); q = R; } return 0; } Bài 5. http://vn.spoj.com/problems/QMAX2/ Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0. Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị. Cho q câu hỏi, mỗi câu có dạng (u, v): Cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v] Input – n: số phần tử của dãy (n ≤ 50000). – m: số lượng biến đổi và câu hỏi (m ≤ 100000). +) biến đổi có dạng: 0 x y value +) câu hỏi có dạng : 1 x y. Output 12 Ghi ra trả lời cho lần lượt từng câu hỏi. Example Input: 63 0133 0464 116 Output: 4 Thuật toán: Để làm bài này, ta gọi F[k] là giá trị lớn nhất trong đoạn mà nút k quản lí, trong lúc cập nhật, muốn đảm bảo thủ tục này không vượt quá log(n) thì khi đi đến 1 nút mà nằm gọn trong đoạn x..y thì ta không được đi vào các nút con của nó nữa (nếu không sẽ đi đến tất cả các đoạn có trong đoạn x..y và độ phức tạp tỷ lệ với n). Nếu như vậy, ta cần có 1 mảng phụ T để lưu lại giá trị cần tăng lên cho tất cả các phần tử của đoạn này, khi ta truy vấn đến 1 nút k đồng thời ta tăng T[k] lên cho T[k*2], T[k*2+1] và F[k]. (do T[k] là giá trị cần tăng lên cho tất cả những phần tử của đoạn nút k quản lí, nên các nút con của nó cũng phải tăng lên T[k]). Sau khi đã cập nhật cho mảng F và các nút con, ta gán lại T[k]=0 để tránh trường hợp cộng lại nhiều lần. Nếu đã đến đoạn nằm gọn trong đoạn x..y thì ta tăng mỗi biến F[k], T[k*2], T[k*2+1] lên v. Khi muốn lấy kết quả, ta vẫn làm như bài QMAX, nhưng đến mỗi nút con, ta vẫn cần thực hiện tăng giá trị T[k] cho T[k*2], T[k*2+1] và F[k] để lấy được kết quả. Tức là khi đến được 1 nút nào đó (trong bất kì thao tác nào, cập nhật hay lấy kết quả) thì đều thực hiện như vậy. Điều này đảm bảo là ta có thể lấy được giá trị chính xác, đây là kiểu cây IT có thông tin truyền từ nút cha xuống nút con. Các bạn có thể tham khảo chương trình để thấy rõ hơn. 13 #include #include #include #include #include #include #include #include usingnamespace std; void solve0(){ scanf("%li%li%li",&L,&R,&v); update(1,1,n); } void solve1(){ scanf("%li%li",&L,&R); res = 0; findres(1,1,n); printf("%li\n",res); } const long maxn = 50000 + 100; long n,m,L,R,loai,v,a[maxn],f[8*maxn],t[8* int main() maxn],res; { /** scanf("%li%li",&n,&m); t[k] la max cua doan nut k quan li for(long i=1;i≤m;i++){ f[k] la mang phu luu phan can tang len cua scanf("%li",&loai); doan nut k if(loai == 0) solve0(); quan li else solve1(); **/ } void update(long k,long l,long r){ return0; t[k] += f[k]; } f[k*2] += f[k]; f[k*2+1] += f[k]; f[k] = 0; if(r < L or R < l)return; if(L ≤ l and r ≤ R){ t[k] += v; f[k*2] += v; f[k*2+1] += v; return; } long m = (l+r)/2; update(k*2,l,m); update(k*2+1,m+1,r); t[k] = max(t[k*2],t[k*2+1]); } void findres(long k,long l,long r){ t[k] += f[k]; f[k*2] += f[k]; f[k*2+1] += f[k]; f[k] = 0; if(r < L or R < l)return; if(L ≤ l and r ≤ R){ res = max(res,t[k]); return; } long m = (l+r)/2; findres(k*2,l,m); findres(k*2+1,m+1,r); } 14 Bài 6. http://vn.spoj.com/problems/NKLINEUP/ Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao. Bác John đã chuẩn bị một danh sách gồm Q (1 ≤ Q ≤ 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1, 1000000]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này. Dữ liệu  Dòng đầu tiên chứa 2 số nguyên N và Q.  Dòng thứ i trong số N dòng sau chứa 1 số nguyên duy nhất, là độ cao của con bò thứ i.  Dòng thứ i trong số Q trong tiếp theo chứa 2 số nguyên A, B (1 ≤ A ≤ B ≤ N), cho biết đoạn các con bò từ A đến B. Kết quả Gồm Q dòng, mỗi dòng chứa 1 số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng. Ví dụ Dữ liệu: 63 1 7 3 4 2 5 15 46 22 Kết qủa 6 15 3 0 Thuật toán: Đây là 1 bài toán xử lí trên dãy số và cần truy cập đến những đoạn A..B bất kì trong dãy, vì vậy interval tree là 1 trong những lựa chọn tốt. Bài này chúng ta có 1 điều may mắn là không cần phải cập nhật lại chiều cao của các con bò, vì vậy thông tin trong cây interval tree là cố định và ta sẽ tạo cây interval tree dựa trên mảng chiều cao của các con bò. Mỗi đoạn thì ta cần in ra chênh lệch độ cao con bò cao nhất và con bò thấp nhất, vì vậy chúng ta cần tìm được giá trị lớn nhất và giá trị nhỏ nhất trong các phần tử từ A đến B. Ta có thể dùng 1 cây interval tree với mỗi nút lưu 2 thông tin, giá trị lớn nhất và giá trị nhỏ nhất trong đoạn mà nó biểu diễn, cũng có thể dùng 2 cây interval tree, 1 cây dùng để lưu giá trị lớn nhất, cây còn lại là giá trị nhỏ nhất. Ở đây ta gọi 2 cây này là maxt và mint. Khi muốn tìm kết quả thì dựa vào mảng Maxt để tìm GTLN trên đoạn A..B, dùng mảng Mint để tìm GTNN trên đoạn A..B, việc này làm tương tự như trong ví dụ của bài viết giới thiệu về Interval tree phía trên. Chú ý là khi tìm max hay tìm min ta đều phải đi đến những nút giống nhau (do đi đến những nút nào thì chỉ phụ thuộc A và B) nên mỗi lần tìm chỉ cần gọi chung 1 thủ tục. #include #include int main() #include { #include scanf("%li%li",&n,&q); #include for (long i=1;i≤n;i++) scanf("%li",&a[i]); using namespace std; update(1,1,n); const long maxn = 50000+100, maxh = for (long Q=1;Q≤q;Q++) { 1000000; scanf("%li%li",&L,&R); long n,q,L,R,a[maxn],tmax[4*maxn],tmin[4 hmax = 1; *maxn],hmax,hmin; hmin = maxh; findres(1,1,n); void update(long k,long l,long r) { printf("%li\n",hmax- hmin); if (l == r) tmin[k] = tmax[k] = a[l]; } else { return 0; long m = (l+r)/2; } update(k*2,l,m); update(k*2+1,m+1,r); tmax[k] = max(tmax[k*2],tmax[k*2+1]); 16 tmin[k] = min(tmin[k*2],tmin[k*2+1]); } } void findres(long k,long l,long r) { if (not(r < L or R < l)) { if (L ≤ l and r ≤ R) { hmax = max(hmax,tmax[k]); hmin = min(hmin,tmin[k]); } else { long m = (l+r)/2; findres(k*2,l,m); findres(k*2+1,m+1,r); } } } Bài 7. http://vn.spoj.com/problems/QMAX/ Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0. Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị. Cho q câu hỏi, mỗi câu có dạng (u, v): cho biết phần tử có giá trị lớn nhất thuộc đoạn [u, v]. Giới hạn  n, m, q ≤ 50000  k>0  Giá trị của một phần tử luôn không vượt quá 231-1 Input  Dòng 1: n, m  m dòng tiếp theo, mỗi dòng chứa u, v, k cho biết một phép biến đổi  Dòng thứ m+2: p  p dòng tiếp theo, mỗi dòng chứa u, v cho biết một phép biến đổi Output  Gồm p dòng chứa kết quả tương ứng cho từng câu hỏi. Example Input: 62 17 132 463 1 34 Output: 3 Thuật toán: Bài này thì ta có m phép biến đổi tăng dãy trước rồi mới yêu cầu tìm giá trị lớn nhất trong các đoạn chứ không phải xen kẽ nhau, vì vậy ta sẽ tìm cách xây dựng dãy số sau m phép biến đổi. Khi có được mảng giá trị sau m phép biến đổi, công việc còn lại của ta là tạo 1 cây interval tree với mỗi nút lưu giá trị lớn nhất của đoạn mà nó quản lí trong khi các phần tử của mảng đã xác định, với mối truy vấn tìm GTLN thì ta có thể làm không mấy khó khăn. Vấn đề bây giờ là xây dựng dãy số sau m phép biến đổi. Ta có thể sử dụng 1 kĩ thuật đơn giản những rất hiệu quả như sau. Giả sử mảng ta cần có là mảng A[0..n+1], lúc đầu A[i]=0 với mọi i. Mỗi yêu cầu u,v,k tức là tăng các phần tử từ vị trí u đến vị trí v lên k đơn vị, ta làm như sau: A[u]:=A[u]+k;A[v+1]:=A[v+1]-k; Sau khi đọc xong m phép biến đổi và làm như trên, cuối cùng là tính mảng A: For i:=1 to n do A[i]:=A[i]+A[i-1]; Các bạn có thể tự chứng minh tính đúng đắn hay có thể viết đoạn chương trình này ra và kiểm nghiệm lại. Như vậy ta đã có thể giải quyết trọn vẹn bài toán. #include #include #include #include #include using namespace std; const long maxn = 50000+100; long n,m,k,u,v,q,L,R,a[maxn],t[4*maxn],res; void update(long k,long l,long r) { if (l == r) t[k] = a[l]; void findres(long k,long l,long r) { if (not(r < L or R < l)) { if (L ≤ l and r ≤ R) res = max(res,t[k]); else { long m = (l+r)/2; findres(k*2,l,m); findres(k*2+1,m+1,r); } } } 18 else { long m = (l+r)/2; update(k*2,l,m); update(k*2+1,m+1,r); t[k] = max(t[k*2],t[k*2+1]); } } int main() { scanf("%li%li",&n,&m); for (long i=1;i≤m;i++) { scanf("%li%li%li",&u,&v,&k); a[u] += k; a[v+1] -= k; } for (long i=1;i≤n;i++) a[i] += a[i-1]; update(1,1,n); scanf("%li",&q); for (long Q=1;Q≤q;Q++) { scanf("%li%li",&L,&R); res = 0; findres(1,1,n); printf("%li\n",res); } return 0;} Bài 8. Dãy ngoặc http://laptrinh.ntu.edu.vn/Problem/Details/3270/?contestid=9 Khái niệm dãy ngoặc đúng được định nghĩa dưới dạng đệ quy như sau: 1. () là dãy ngoặc đúng 2. C là dãy ngoặc đúng nếu C = (A) hay C = AB với A, B là các dãy ngoặc đúng. Ví dụ dãy ngoặc đúng: (), (()), ()(), (())() Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()( Cho trước một dãy ngoặc bất kỳ gồm n dấu ngoặc được đánh số từ 1 đến n. Có m câu hỏi, mỗi câu gồm hai số nguyên 1 ≤ p ≤ r ≤ n, yêu cầu xác định xem dãy ngoặc con từ vị trí p đến vị trí r có phải là dãy ngoặc đúng hay không. Hãy cho biết kết quả của m câu hỏi trên. Dữ liệu nhập: – Dòng đầu tiên là hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 105) – Dòng thứ hai là dãy ngoặc ban đầu gồm n dấu ngoặc ‘(‘ hay ‘)’. – Trong m dòng tiếp theo, tại dòng thứ i là hai số p i và ri của câu hỏi thứ i tương ứng, hai số cách nhau một khoảng trắng. (1 ≤ p i ≤ ri ≤ n). Dữ liệu xuất: – Gồm m dòng ứng với m câu hỏi, nếu dãy ngoặc con tương ứng là dãy ngoặc đúng, in ra YES, nếu dãy ngoặc con tương ứng là không phải dãy ngoặc đúng, in ra NO. Ví dụ 19  input 85 (((()))) 14 36 48 45 27 output NO YES NO YES YES Thuật toán: #include using namespace std; int n, m, x, y, bb[400001], cc[400001]; char ch; void update(int k, int x, int y, int d, int c, int v) { if (c= z); } main() { scanf("%d %d\n", &n, &m); for (int i=1; i≤n; i++) { scanf("%c", &ch); x += (ch == '(') ? 1 : -1; update(1, 1, n, i, i, x); } while (m--) { scanf("%d %d\n", &x, &y); printf("%s\n", check(x,y) ? "NO"); "YES" : 20
- Xem thêm -