比赛时虽然贪了心，不过后面没想到怎么处理和set的排序方法忘了- -，其实是和优先队列的仿函数一样的。。。
比赛后用set pair过了。。。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200005;
const ll mod = 1e9 + 7;
const double eps = 1e-12;
ll a[N];
struct node1 {
ll d, dm, pos;
}f[N];
struct node2 {
ll d, pos;
}g[N];
bool cmp1(node1 a, node1 b) {
return a.d > b.d;
}
bool cmp2(node2 a, node2 b) {
return a.d > b.d;
}
ll l[N], r[N], ans[N];
set<pair<ll, ll> >s;
int main() {
ll n, m;
cin >> n >> m;
for (ll i = 1;i <= n;i++) {
cin >> l[i] >> r[i];
if (i >= 2) {
f[i - 1].d = l[i] - r[i - 1];
f[i - 1].dm = r[i] - l[i - 1];
f[i - 1].pos = i - 1;
}
}
for (ll i = 1;i <= m;i++) {
cin >> a[i];
g[i].d = a[i];
g[i].pos = i;
}
sort(f + 1, f + n, cmp1);
sort(g + 1, g + m + 1, cmp2);
ll flag = 1, j = 1;
for (int i = 1;i <= m;i++)s.insert(make_pair(g[i].d,g[i].pos));
for (ll i = 1;i < n;i++){
auto it = s.upper_bound(make_pair(f[i].dm,1e18));
if (it != s.begin())it--;
/*while (it!=s.end()&& (!(g[it->second].d >= f[i].d&&g[it->second].d <= f[i].dm))) {
j++;
}*/
if(it!=s.end()&&it->first >= f[i].d&&it->first <= f[i].dm){
ans[f[i].pos] = it->second;
s.erase(it);
}
else {
flag = 0;
break;
}
}
if (flag == 0)puts("No");
else {
puts("Yes");
for (ll i = 1;i < n;i++)
cout << ans[i] << " ";
}
return 0;
}
然后又作死，自己脑补平衡树套平衡树用的splay过了，两个都错在过24组，set里错24组因为不知道排序内部到底会有什么鬼，splay二分查找时要保存满足条件的最大值，这里不是循环到最后的y值可能y会由一个相等的值转到一个小于或大于的值，因为没判断想等跳出，后面判断了为更大的才赋值。
其实这里本来只用写单层splay就可以了，另一个用个vector保存就可以了，不过想练练splay了。。。其实和普通平衡树差不多，只不过每一个节点又是一课平衡树，操作的时候注意第一个点建树为空删树，把操作部分变为对子树中节点操作，当然这个题没有复杂的up或者down。另外要注意要先声明一些东西，不然后面调用前面，前面又调用后面- -。。。
另外两种时间好似差不多- -。估计c++11中stl优化的比较好吧-w-。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 800005;
const ll maxn = 800005;
const ll mod = 1e9 + 7;
const double eps = 1e-12;
ll a[N];
struct node {
ll d, dm, pos;
}f[N];
pair<ll, ll>g[N];
bool cmp(node a, node b) {
return a.d > b.d;
}
struct SplayTree;
struct SplayTree *cstm;
ll l[N], r[N], ans[N];
struct Node {
ll key;
SplayTree *st;
Node *c[2], *p;
}mem[N], *cur;
//Initialize functions without memory pool
//Splay tree
struct SplayTree {
Node *root,*nil;
void Rotate(Node *x, ll f) {
if (x == nil) return;
Node *y = x->p;
y->c[f ^ 1] = x->c[f], x->p = y->p;
if (x->c[f] != nil)
x->c[f]->p = y;
if (y->p != nil)
y->p->c[y->p->c[1] == y] = x;
x->c[f] = y, y->p = x;
}
void Splay(Node *x, Node *f) {
while (x->p != f) {
Node *y = x->p;
if (y->p == f)
Rotate(x, x == y->c[0]);
else {
ll fd = y->p->c[0] == y;
if (y->c[fd] == x)
Rotate(x, fd ^ 1), Rotate(x, fd);
else
Rotate(y, fd), Rotate(x, fd);
}
}
if (f == nil)
root = x;
}
Node *newNode(ll v, Node *p, Node *nil) {
cur->c[0] = cur->c[1] = nil;
cur->p = p;
cur->key = v;
cur->st = cstm++;
return cur++;
}
void Insert(ll v) {
Node *x = root, *y = nil;
while (x != nil) {
y = x;
x = x->c[v >= x->key];
}
y->c[v >= y->key] = x = newNode(v, y, nil);
Splay(x, nil);
}
void Insert(ll v,ll pos) {
Node *x = root, *y = nil;
while (x != nil&&x->key != v) {
y = x;
x = x->c[v >= x->key];
}
if (x == nil) {
y->c[v >= y->key] = x = newNode(v, y, nil);
cur->c[0] = cur->c[1] = nullptr;
cur->p = cur;
cur->key = 0;
cur->st = cstm++;
x->st->nil = cur++;
x->st->root = x->st->nil;
}
x->st->Insert(pos);
Splay(x, nil);
}
pair<ll, ll> fun(ll v) {
Node *x = root, *y = nil;
while (x!=nil) {
if (x->key <= v&&x->key > y->key)
y = x;
x = x->c[v > x->key];
}
if(y!=nil)
return make_pair(y->key, y->st->root->key);
return make_pair(-1, -1);
}
void Del() {
Node *x = root;
if (x->c[0] == nil&&x->c[1] == nil)root = nil;
else if (x->c[0] == nil) {
x = x->c[1];
while (x->c[0] != nil)
x = x->c[0];
Splay(x, nil);//x->c[0]->p = nil;//x->c[0]->c[0] = x->c[0]->c[1] = nil;
x->c[0] = nil;
}
else if (x->c[1] == nil) {
x = x->c[0];
while (x->c[1] != nil)
x = x->c[1];
Splay(x, nil);//x->c[1]->p = nil;//x->c[1]->c[0] = x->c[1]->c[1] = nil;
x->c[1] = nil;
}
else {
x = x->c[1];
while (x->c[0] != nil)
x = x->c[0];
Node *y = root;
Splay(x, nil);
Splay(y, x);
x->c[0] = x->c[0]->c[0];
x->c[0]->p = x;
}
//Splay(x->c[0], x->c[1]);
}
void Remove(ll v) {
Node *x = root;
while (x->key != v) {
x = x->c[v >= x->key];
}
Splay(x, nil);
Del();
}
void Remove(pair<ll, ll> it) {
Node *x = root;
while (x->key != it.first) {
x = x->c[it.first >= x->key];
}
Splay(x, nil);
x->st->Remove(it.second);
if (x->st->root == x->st->nil)
Del();
}
}s,stm[N];
void Init() {
cur = mem;
cstm = stm;
}
int main() {
ll n, m;
cin >> n >> m;
for (ll i = 1;i <= n;i++) {
cin >> l[i] >> r[i];
if (i >= 2) {
f[i - 1].d = l[i] - r[i - 1];
f[i - 1].dm = r[i] - l[i - 1];
f[i - 1].pos = i - 1;
}
}
for (ll i = 1;i <= m;i++) {
cin >> a[i];
g[i].first = a[i];
g[i].second = i;
}
sort(f + 1, f + n, cmp);
sort(g + 1, g + m + 1);
ll flag = 1, j = 1;
Init();cur->c[0] = cur->c[1] = nullptr;cur->key = 0;cur->p = cur;cur->st = cstm++;s.nil = cur++;s.root = s.nil;
for (ll i = m;i >= 1;i--)s.Insert(g[i].first,g[i].second);
for (ll i = 1;i < n;i++){
auto it = s.fun(f[i].dm);
if(it.first!=-1&&it.first >= f[i].d&&it.first <= f[i].dm){
ans[f[i].pos] = it.second;
s.Remove(it);
}
else {
flag = 0;
break;
}
}
if (flag == 0)puts("No");
else {
puts("Yes");
for (ll i = 1;i < n;i++)
cout << ans[i] << " ";
}
return 0;
}