一开始用sort+binary_search,结果还是超时了，后来看到用lower_bound做。首先用map< int, vector<int> >,对每一个出现的数字用vector<int>记录出现位置，最后查找时如果位置不在vector里说明没有，若有相交的区间，说明有这个数。
iterator lower_bound(beg, end, val):返回一个迭代器，它引用[beg, end)范围最低的位置，要求[beg, end)按照升序排列，此时插入val不会破坏该顺序。，如果val大于所有元素，返回end。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <map> 6 using namespace std; 7 int main() 8 { 9 int n; 10 scanf("%d", &n); 11 map< int, vector<int> > ivmap; 12 int t; 13 for (int i = 1; i <= n; ++i) 14 { 15 scanf("%d", &t); 16 ivmap[t].push_back(i); //按顺序记录每个数据出现位置 17 } 18 int q; 19 scanf("%d", &q); 20 while (q--) 21 { 22 int l, r, x; 23 scanf("%d %d %d", &l, &r, &x); 24 if (ivmap.count(x) == 0) 25 { 26 printf("0"); 27 continue; 28 } 29 vector<int>::iterator it; 30 it = lower_bound(ivmap[x].begin(), ivmap[x].end(), l); 31 if (it == ivmap[x].end()) 32 printf("0"); 33 else if (*it <= r) 34 printf("1"); 35 else 36 printf("0"); 37 } 38 //system("pause"); 39 return 0; 40 }