Bài toán
Cho các truy vấn
D x y: Thêm một người có chỉ số x và y
P i: Tìm một người j khác i đã có ở thời điểm gặp truy vấn này sao cho x[j]>=x[i] và y[j]>=y[i], y[j] nhỏ nhất, nếu có nhiều j thỏa mãn thì x[j] phải nhỏ nhất.
Độ phức tạp
O((m+n) logn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
#define X first
#define Y second
int m, n, nkey;
int a[1230997];
ii e[1230997];
ii key[1230997];
map<int, int> ma;
map<int, int> mb;
int bolji(int p, int q){
if (p&&q) return a[p]<a[q] ? q : p;
else return p|q;
}
bool y_cmp(ii A, ii B){
return A.Y==B.Y ? A<B : A.Y<B.Y;
}
struct tournament_tree {
// leaf node contains index only
int T[1230997];
void update(int node, int ll, int rr, int key){
if (ll>key || rr<key || ll>rr) return ;
if (ll==rr) { T[node]=key; return; }
update(node*2, ll, (ll+rr)/2, key);
update(node*2+1, (ll+rr)/2+1, rr, key);
T[node] = bolji(T[node*2], T[node*2+1]);
}
int get(int node, int ll, int rr, int key){
if (rr<=key) return 0;
if (T[node]==0 || a[T[node]]<a[key]) return 0;
if (ll==rr) return ll;
int r = get(node*2, ll, (ll+rr)/2, key);
if (r==0) r = get(node*2+1, (ll+rr)/2+1, rr, key);
return r;
}
};
tournament_tree tr;
main(){
int i; char c;
scanf("%d", &m);
for (i=1; i<=m; i++){
scanf(" %c", &c);
if (c=='D') {
scanf("%d%d", &e[i].X, &e[i].Y);
key[++nkey]=e[i];
}
else scanf("%d", &e[i].Y);
}
sort(key+1, key+nkey+1, y_cmp);
for (i=1; i<=m; i++)
if (e[i].X){
e[i].Y=lower_bound(key+1, key+nkey+1, e[i], y_cmp) - key;
ma[++n]=e[i].Y;
mb[e[i].Y]=n;
a[e[i].Y]=e[i].X;
//printf("%d %d\n", e[i].X, e[i].Y);
}
else e[i].Y=ma[e[i].Y];
/*printf("\n\n");
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
printf("\n\n");*/
for (i=1; i<=m; i++)
if (e[i].X) tr.update(1, 1, n, e[i].Y);
else {
int z = tr.get(1, 1, n, e[i].Y);
if (z==0) printf("NE\n");
else printf("%d\n", mb[z]);
}
}
Nhận xét
Ta có thể biến đổi để các a[i].Y phân biệt và nhận các giá trị từ 1 đến n bằng cách nén. Dùng một segment_tree hoặc có thể gọi là tournament_tree quản lý n nút. Với mỗi yêu cầu D x y (x và y đã được nén), ta gán giá trị ở nút lá thứ y bằng x (vì vậy cần đảm bảo y phân biệt, lưu ý là trong code trên, ta không gán giá trị nút thứ y bằng x mà gán bằng y, vì rõ ràng là từ y ta suy ra được x, hay nói cách khác là lưu chỉ số). Các nút không phải lá sẽ chứa giá trị là số lớn nhất trong cây con nó quản lý (trong code trên là lưu chỉ số).Với mỗi yêu cầu P x, giả sử ta tìm kiếm giá trị y thoả mãn mà nằm trong đoạn (ll..rr) mà quản lý bởi nút node, ta xét các trường hợp:
- Nếu rr<=x, thì đoạn này không có giá trị y nào thỏa mãn.
- Nếu T[node]=0 hoặc T[node]<a[x].X thì không có giá trị y nào thỏa mãn
- Nếu tìm kiếm trên cây con trái không thành công thì ta tìm trên cây con phải.
Các thao tác trên đàm bảo một truy vấn thực hiện trong O(logn)
Mô tả
Các lỗi thường gặp