Codeforces Round 919 (Div. 2) D题 偏移量，二分，子问题

Problem - D - Codeforces

题意：

用两种方式制作一个很大的数组，然后查询对应下标对应的数字。

难点：

制作的方式有复制n次原数组接到后面，样例的数据很大，很快就会溢出unsigned long long。暴力做出这个数组是不可以的。

细节：

查询的大小不会超过1e18，所以我们超过上限的不进行记录了。

方法：

我们用记录数字偏移量的方法。查找时找对应偏移量即可。->代码上我们记录操作，计算这次操作末尾的偏移量，这样查找的话可以用二分查找，很快就能找到是哪次操作的位置。

为什么要这么做：

因为是对应数字的偏移量，那么这个位置就是这个数字。

如果这个位置是复制操作，我们取余就可以得到复制前的偏移量，得到的数字也是这个数字。（如果前面还是复制操作呢？ ->其实就是子问题啦）

————

根据题目第一个样例做解释：

（pos数组是偏移量，options数组就是操作类型，val数组就是操作的值）

代码：注意看对超过1e18位置的处理：

#define ll unsigned long long
const ll inf = 1e18;
void solve()
{
	ll n, q;
	cin >> n >> q;
	vector<ll>pos;//偏移量
	vector<ll>val;
	vector<ll>options;
	for (ll i = 0; i < n; i++)
	{
		ll op, num; cin >> op >> num;
		options.push_back(op);
		val.push_back(num);
		if (op == 1)
		{
			if (pos.size() == 0)//第一次
				pos.push_back(1);
			else
			{
				pos.push_back(pos[i - 1] + 1);
			}
		}
		else
		{
			//查询不会查老后面，但是前面操作会超出
			if ((inf) / num < pos[i - 1]) //#### 这里是对超过1e18的处理，inf加个num向上取整更合适，不过这里也可以过
				pos.push_back(inf + 5);
			else
				pos.push_back(pos[i - 1] * (num + 1));
		}
	}

	for (ll i = 0; i < q; i++)
	{
		ll num; cin >> num;
		//
		ll left = 0, right = pos.size() - 1;
		while (1)
		{
			while (left < right)//根据偏移量二分。二分就是找到自己在的对应操作的位置。
			{
				ll mid = left + (right - left) / 2;
				if (pos[mid] >= num)right = mid;
				else left = mid + 1;
			}

			if (options[right] == 1)//！！！偏移量正好对应的是一个数字
			{
				cout << val[right] << " ";
				break;
			}
			else//调整位置接着二分（num变了,划成子问题了
			{
				ll snum = pos[right - 1];//pos[right] / (val[right]+1);//这次操作的原始数组大小
				num %= snum;//换到对应位置
				if (num == 0)num = snum;


				left = 0;//只会在左边了，再次找
			}
		}
	}
	cout << endl;
}