# hiho1299&hihocoder挑战赛20-t1:打折机票 – 我是思博

### 输出

```7 6
1 1
2 1
4 3
4 4
4 5
6 9
7 9
1 7
1 2
6 7
3 3
4 4
5 5```

```9
1
9
None
5
None
```

（好吧其实都是我的错）

]

1. 我特么把大数组存为临时变量了;
2. 我没及时return.

AC

```#include
#include
#include
#define MAXN 400100
using namespace std;
int l[MAXN], r[MAXN];
struct Node{
int l, r, v;
}node[MAXN];

void build(int i, int l, int r){
//	if (l > r) return;
//	cout << i << " " <<  l << " " <<  r << endl;
node[i].l = l;
node[i].r = r;
node[i].v = -1;
if (l == r) return;
build(i << 1, l, (l + r) >> 1);
build((i << 1) + 1,((l + r) >> 1) + 1, r);
}

int query(int i, int l, int r){
//	cout << i << endl;
int s = -1;
if (node[i].l > r || node[i].r < l) return s;
if (node[i].l >= l && node[i].r <= r) return node[i].v;
if (node[i].l == node[i].r) return s;
int mid = i << 1;
s = max(s, query(mid, l, r));
s = max(s, query(mid + 1, l, r));
return s;
}

void insert(int i, int v, int n){
//	cout << i << " " << node[i].l << " " << node[i].r << endl;

if (node[i].l > n || node[i].r < n) return;
if (node[i].l <= n && node[i].r >= n) node[i].v = max(node[i].v ,v);
//	cout << i << endl;
int l = node[i].l, r = node[i].r;
if (l == r){
return;
}
insert(i << 1, v, n);
insert((i << 1) + 1, v, n);

}
int main(){
int n, m;
//	freopen("c.in", "r", stdin);
//	freopen("c.out", "w", stdout);
scanf("%d%d", &n, &m);

int bt = -1;
for (int i = 0; i < n; i++){
scanf("%d%d", &l[i], &r[i]);
bt = max(l[i], bt);
}
//	cout << bt << endl;
build(1, 1, bt + 1);
for (int i = 0; i < n; i++){
insert(1, r[i], l[i]);
}
//	cout << query(1, 4, 5) << " xxsxsxs" << endl;
for (int i = 0; i < m; i++){
scanf("%d%d", &l[i], &r[i]);
//		cout << l[i] << " " << r[i] << endl;
}
for (int i = 0; i < m; i++){
int a = query(1, l[i], r[i]);
if (a != -1){
printf("%dn", a);
}else{
printf("Nonen");
}
}
return 0;
}
```