题意：
首先输入一个数字m(1?≤?m?≤?10^5) ，表示有m次操作（通过m次操作构造一个数字串，数字串初始化为空），接下有m行操作，每一行第一个数字表示操作类型，1：表示往数字串末尾加一个新数字，2：表示往数字串加Ci(1?≤?ci?≤?10^4)次已有串的前Li(1?≤?Li?≤?10^5)个数字；
接着输入一个数字n，表示查询次数，下一行是查询数字串相应位置的值
链接：http://codeforces.com/problemset/problem/380/A
解法：用一个数组t存数字串前10^5数字，开一数组d记录每一次操作完数字串长度，对于每一次查询位置a，二分查找d数组，然后查询数组t。
#define N 1000005 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; __int64 d[N],t[N],m,n; struct node { __int64 f; __int64 x; __int64 y; }; node p[N]; int main() { __int64 i,j,c,s,k; while(scanf("%I64d",&m)!=EOF) { d[0]=0; s=1; for(i=1;i<=m;i++) { scanf("%I64d",&p[i].f); if(p[i].f==1) { scanf("%I64d",&p[i].x); d[i]=d[i-1]+1; if(s<=100000) t[s++]=p[i].x; } else { scanf("%I64d%I64d",&p[i].x,&p[i].y); d[i]=d[i-1]+p[i].x*p[i].y; for(int h=1;h<=p[i].y&&s<=100000;h++) { for(j=1;j<=p[i].x&&s<=100000;j++) t[s++]=t[j]; } } } scanf("%I64d",&n); for(i=0;i<n;i++) { scanf("%I64d",&c); k=binarySearch(c); k=(upper_bound(d+1,d+m+1,c)-d)-1; if(d[k]==c) { if(p[k].f==1) { printf("%I64d\n",p[k].x); } else { printf("%I64d\n",t[p[k].x]); } } else { c-=d[k]; c%=p[k+1].x; if(c==0) c=p[k+1].x; printf("%I64d\n",t[c]); } } } return 0; }
C++ STL二分搜索函数：
STL中包含丰富的二分搜索算法。注意：这些算法是要求输入范围[first, last)是有序的!
bool binary_search(first, last, value); //返回bool型！
bool binary_search(first, last, value, comp);//以满足comp(*it, value)的比较函数代替 "等于"
lower_bound(first, last, value); //返回有序序列中第一个不小于value的元素的迭代器位置。
upper_bound(first, last, value); //返回第一个大于value的元素的迭代器，找不到或者有序范围内最后一个元素等于value，那就返回last了。
lower_bound(first, last, value, comp); //用comp比较函数取代“<"。返回第一个使得comp(*it, value)为false的it。
equal_range(first, last, value); //返回一个迭代器对，由对应的lower_bound, upper_bound返回值组成。
equal_range(first, last, value, comp);
Binary Search Demo:
#include<stdio.h> #include<iostream> #include<algorithm> #include<vector> using namespace std; bool mygreater(int i,int j) { return i>j; } int main() { int myints[] = {10,20,30,30,20,10,10,20}; vector<int> v(myints, myints+8); sort(v.begin(), v.end()); vector<int>::iterator low, up; low = lower_bound(v.begin(), v.end(), 20); up = upper_bound(v.begin(), v.end(), 20); pair<vector<int>::iterator, vector<int>::iterator> bounds; bounds=equal_range(v.begin(), v.end(), 20); cout << "lower_bound at position " << (low-v.begin()) <<‘\n‘; cout << "upper_bound at position " << (up-v.begin()) << ‘\n‘; cout << "bounds at positions " << (bounds.first - v.begin()); cout << " and " << (bounds.second - v.begin()) << ‘\n‘; return 0; }