题目链接：http://codeforces.com/gym/101149/problem/G
题目大意：给你n对数字，为(a[i], b[i])，给你m对数字，为(w[i], c[i])。给n对数字找配对，这个配对必须是m中的，而且m中的每个只能和n中的配对一次。
配对条件，w[i]>=a[j], c[i]>=b[j]即可配对。
输出n个数字，每个数字在m个数字当中的配对。
思路：假定n对数字的是x，m对数字的是y
离散化以后sort一下x和y，这样我们就得到了第一维是排序好了的。
然后我们暴力x，每次都把a[i]的值相同的放入线段树，线段树里面储存的是b[i]。
然后如果a[i] != a[i+1]，那么我们就暴力y，对于y，暴力其中所有的w[j] < a[i+1]的，然后再线段树中找离c[i]左边最近的那个数字即可。
ORZ，第一次知道queue这么消耗空间，一直MLE了。
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") const int inf = 0x3f3f3f3f; const int maxn = 4e5 + 5; const int maxf = 2e5 + 5; int n, m; pair<int, pair<int, int> > a[maxf]; pair<int, pair<int, int> > b[maxf]; vector<int> ve; vector<int> que[maxn * 2]; /* 线段树上二分，每次找到和当前的pos最靠近的左端的即可。并且每次保存id */ struct Tree{ int cost; int lft; }tree[maxn << 3]; int ans[maxf]; int update(int pos, int l, int r, int o, int add, int ID = 0){ if (pos == l && pos == r){ tree[o].cost += add; if (add == 1) {que[l].push_back(ID); return 0;} if (add == -1) { ID = que[l][tree[o].lft]; tree[o].lft++; return ID; } } int mid = (l + r) / 2; int id = 0; if (pos <= mid) id = update(pos, l, mid, o << 1, add, ID); if (pos > mid) id = update(pos, mid + 1, r, o << 1 | 1, add, ID); tree[o].cost = tree[o << 1].cost + tree[o << 1 | 1].cost; return id; } int query(int ql, int qr, int l, int r, int o){ if (l == r){ return l; } int mid = (l + r) / 2; int res = 0; if (qr > mid && tree[o << 1 | 1].cost > 0) res = max(res, query(ql, qr, mid + 1, r, o << 1 | 1)); if (res == 0 && ql <= mid && tree[o << 1].cost > 0) res = max(res, query(ql, qr, l, mid, o << 1)); return res; } void solve(){ int len = ve.size(); int pos2 = 1; while (b[pos2].fi < a[1].fi) pos2++; a[n + 1] = mk(inf, mk(inf, inf)); for(int i = 1; i <= n; i++){ update(a[i].se.fi, 1, len, 1, 1, a[i].se.se); if(a[i].fi != a[i + 1].fi) { while (pos2 <= m && b[pos2].fi < a[i + 1].fi){ if (tree[1].cost != 0){ int x = query(1, b[pos2].se.fi, 1, len, 1); if (x){ int id = update(x, 1, len, 1, -1); ans[id] = b[pos2].se.se; } } pos2++; } } } for (int i = 1; i <= n; i++){ if (ans[i] == 0) { printf("-1 "); return; } } for (int i = 1; i <= n; i++){ printf("%d%c", ans[i], i == n ? ' ' : ' '); } } int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++){ scanf("%d%d", &a[i].fi, &a[i].se.fi); a[i].se.se = i; ve.push_back(a[i].fi); ve.push_back(a[i].se.fi); } scanf("%d", &m); for (int i = 1; i <= m; i++){ scanf("%d%d", &b[i].fi, &b[i].se.fi); b[i].se.se = i; ve.push_back(b[i].fi); ve.push_back(b[i].se.fi); } if (n > m) { printf("-1 "); return 0; } sort(ALL(ve)); ve.erase(unique(ve.begin(), ve.end()), ve.end()); for (int i = 1; i <= n; i++){ a[i].fi = lower_bound(ALL(ve), a[i].fi) - ve.begin() + 1; a[i].se.fi = lower_bound(ALL(ve), a[i].se.fi) - ve.begin() + 1; } for (int i = 1; i <= m; i++){ b[i].fi = lower_bound(ALL(ve), b[i].fi) - ve.begin() + 1; b[i].se.fi = lower_bound(ALL(ve), b[i].se.fi) - ve.begin() + 1; } sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + m); solve(); return 0; }