这题大多数人用的是二分查找，我想到了一个双指针的写法，虽然综合时间复杂度仍然是的，但二分写法实际上是，而该写法可以优化成，即对于T次询问，总时间复杂度是。

首先先对区间左端点排序，对于一个询问x，我们不做在线回答，而是收集起来做离线回答。 先对询问进行排序。

记当前的询问是 ，当前的区间是，有以下几种情况

  • ：说明x正中下怀，只需要将答案记录为 即可（从0开始）
  • ：由于区间被排序了，若当前的x连左端点都够不到，说明往后都不会够到了，故答案是-1
  • ：即当前的很大，能够越过的右端点，此时需要i++，也就是寻找下一个左端点更强的区间，才能保证右端点能够包住

特别地： 不需要重新枚举，因为越大的数，对区间的要求越高，即若当前的数字符合，往后一个询问（即我们排过序的询问集合）只会要求比这个不差的区间（至少是i，不可能是比i小的下标）

另外：当，且当前询问还没结束，而i只有区间不够的时候才会++,说明在此之后的，更大的询问数字不再可能落入这个区间（当前的询问都已经超出了这个最强的区间，往后的也一定会）

因此， 是单调不降的，最差的情况是，而i与T是同数量级的，故可简化为

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
	int l,r,idx;
};
const int N=2e5+7;
vector<node> a;

bool cmp(node a,node b){
	return a.l<b.l;
}
int n,q;
vector<pair<int,int>> qu;
int ans[N];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		a.push_back({l,r,i});
	}
	sort(a.begin(),a.end(),cmp);
	for(int i=1;i<=q;i++){
		int x;
		cin>>x;
		qu.push_back({x,i});
	}
	sort(qu.begin(),qu.end());
	int i=0;
	for(int j=0;j<qu.size();){
		int x=qu[j].first;
		int y=qu[j].second;
		if(i==n){
			ans[y]=-1; //如果当前的数字已经走到了最末尾，说明往后的数字都是大于右端点的
			j++;//继续
			continue;
		}
		if(a[i].l<=x && x<=a[i].r){ //如果当前恰好满足
			ans[y]=a[i].idx;
			j++;//继续
		}
		else if(x<a[i].l){ //如果当前的数小于当前区间端点，往后都不可能符合
			ans[y]=-1;
			j++;//继续
		}
		else if(x>a[i].r){ //如果当前的数大于当前区间右端点，需要往后移动
			while(i<n && x>a[i].r)i++;
		}
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
	return 0;
}

事实上，这个写法写蠢了（为了牺牲可读性），另外一种聪明的写法可以减少常数(AI写的）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
    int l, r, idx;
};

// 存储查询：值x + 查询的原始下标（用于按输入顺序输出）
struct Query {
    int x, id;
};

const int N = 2e5 + 7;
vector<node> a;
vector<Query> qs;
vector<int> ans; // 存储每个查询的答案

// 区间按l升序排序
bool cmp_node(node a, node b) {
    return a.l < b.l;
}

// 查询按x升序排序
bool cmp_query(Query a, Query b) {
    return a.x < b.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    // 输入区间
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        a.push_back({l, r, i});
    }
    sort(a.begin(), a.end(), cmp_node);
    
    // 输入查询，记录原始下标（用于按输入顺序输出）
    qs.resize(q);
    ans.resize(q, -1); // 默认答案为-1
    for (int i = 0; i < q; i++) {
        cin >> qs[i].x;
        qs[i].id = i;
    }
    sort(qs.begin(), qs.end(), cmp_query);
    
    // 双指针遍历：i遍历区间，j遍历查询
    int i = 0;
    for (auto& query : qs) {
        int x = query.x;
        int qid = query.id;
        
        // 移动区间指针：找到所有l ≤ x的区间，检查是否包含x
        while (i < n) {
            if (a[i].l > x) {
                // 后续区间的l更大，不可能包含x，跳出
                break;
            }
            if (a[i].r >= x) {
                // 找到第一个包含x的区间，记录答案并跳出
                ans[qid] = a[i].idx;
                break;
            }
            // 当前区间l≤x但r<x，继续看下一个区间
            i++;
        }
        // 若i==n，说明没有区间包含x，ans[qid]保持-1
    }
    
    // 按原始输入顺序输出答案
    for (int x : ans) {
        cout << x << "\n";
    }
    
    return 0;
}