Set可解，Treap也可解。
（1） Treap
/* */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct Node {
Node* ch[];
int r, v, s, id; Node() {} Node(int v_, int id_) {
ch[] = ch[] = NULL;
r = rand();
v = v_;
id = id_;
s = ;
} int cmp(int v_) const {
if (v == v_) return -;
return v<v_ ? :;
} friend bool operator< (const Node& a, const Node& b) {
return a.r < b.r;
} void maintain() {
s = ;
if (ch[] != NULL) s += ch[]->s;
if (ch[] != NULL) s += ch[]->s;
} } Node; const int maxn = 1e5+;
const int maxm = 5e6+;
int id[maxm];
Node* root; void rotate(Node*& o, int d) {
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
} void insert(Node*& o, int x, int id) {
if (o == NULL) {
o = new Node(x, id);
} else {
int d = x<o->v ? :;
insert(o->ch[d], x, id);
if (o->ch[d]->r > o->r)
rotate(o, d^);
}
o->maintain();
} void remove(Node*& o, int x) {
int d = o->cmp(x); if (d == -) {
Node* u = o;
if (o->ch[]!=NULL && o->ch[]!=NULL) {
int d2 = o->ch[]->r > o->ch[]->r ? :;
rotate(o, d2);
remove(o->ch[d2], x);
} else {
if (o->ch[] == NULL)
o = o->ch[];
else
o = o->ch[];
delete u;
}
} else {
remove(o->ch[d], x);
} if (o != NULL)
o->maintain();
} void del(Node*& o) {
if (o->ch[] != NULL) del(o->ch[]);
if (o->ch[] != NULL) del(o->ch[]);
delete o;
o = NULL;
} int findK(Node* o, int x) {
if (o == NULL)
return -; int d = o->cmp(x);
if (d == -)
return (o->ch[]==NULL ? :o->ch[]->s) + ;
if (d == ) {
return findK(o->ch[], x);
} else {
int tmp = findK(o->ch[], x);
if (tmp < )
return -;
tmp += (o->ch[]==NULL ? :o->ch[]->s) + ;
return tmp;
}
} Node* kth(Node* o, int k) {
if (o==NULL || k<= || k>o->s)
return NULL; int s = o->ch[]==NULL ? :o->ch[]->s;
if (k == s+)
return o;
else if (k <= s)
return kth(o->ch[], k);
else
return kth(o->ch[], k-s-);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, m;
int x, g, k;
int ans;
Node *gtp, *ltp; while (scanf("%d", &n)!=EOF && n) {
insert(root, 1e9, );
rep(i, , n) {
scanf("%d %d", &x, &g);
insert(root, g, x);
m = findK(root, g);
ltp = kth(root, m-);
gtp = kth(root, m+);
if (ltp != NULL) {
if (gtp->v - g < g - ltp->v) {
ans = gtp->id;
} else {
ans = ltp->id;
}
} else {
ans = gtp->id;
}
printf("%d %d\n", x, ans);
}
del(root);
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
（2）set
/* 4585 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = 5e6+;
int id[maxn]; int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif sti st;
sti::iterator iter;
int n;
int k, g, tmp; while (scanf("%d", &n)!=EOF && n) {
st.clr();
rep(i, , n) {
scanf("%d %d", &k, &g);
iter = st.lower_bound(g);
if (iter == st.end()) {
if (iter == st.begin()) {
printf("%d 1\n", k);
} else {
--iter;
printf("%d %d\n", k, id[*iter]);
}
} else {
if (iter == st.begin()) {
printf("%d %d\n", k, id[*iter]);
} else {
tmp = *iter;
--iter;
if (tmp-g < g-*iter) {
printf("%d %d\n", k, id[tmp]);
} else {
printf("%d %d\n", k, id[*iter]);
}
}
}
id[g] = k;
st.insert(g);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}