Codeforces Round #223 (Div. 2): C. Sereja and Prefixes（二分+递归）

题意：

你有一个序列，一开始为空，之后进行m次操作，操作有两种：

• 1 x：在当前序列后面添加一个数x
• 2 x, y：将序列的前x个数复制y遍接序列后面（x<10000）

之后n次询问，每次询问位置p上面的数字是多少，保证p不超过序列长度

思路：

对于每次询问，直接暴力递归当前位置上的数字是哪次操作①添加的就行了，因为复制操作每次只会复制前10000个数字，所以递归次数不会超过15次（递归时可能需要用到二分）

当然也可以直接记下来前10000个数字是多少， 这样应该就是线性的了

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 1000000007
typedef struct Res
{
	int op;
	int x, y;
	LL l, r;
}Res;
Res s[200005];
int Gao(int p, LL x)
{
	int l, r, m;
	if(s[p].op==1)
		return s[p].x;
	else
	{
		r = x-s[p].l+1;
		x = (r-1)%s[p].x+1;
		l = 1, r = p-1;
		while(l<r)
		{
			m = (l+r+1)/2;
			if(x<s[m].l)
				r = m-1;
			else
				l = m;
		}
		return Gao(r, x);
	}
}
int main(void)
{
	LL now, p;
	int m, n, i, R;
	scanf("%d", &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d", &s[i].op);
		if(s[i].op==1)
			scanf("%d", &s[i].x);
		else
			scanf("%d%d", &s[i].x, &s[i].y);
	}
	R = now = 0;
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld", &p);
		while(R!=m && p>now)
		{
			R++;
			s[R].l = now+1;
			if(s[R].op==1)
				s[R].r = s[R].l;
			else
				s[R].r = s[R].x*s[R].y+now;
			now = s[R].r;
		}
		printf("%d ", Gao(R, p));
	}
	puts("");
	return 0;
}