分块例题6

题面描述

给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问，数据随机生成。

输入格式

第一行输入一个数字 n

第二行输入 n 个数字，第 i 个数字为a[i]，以空格隔开

接下来输入 n 行询问，每行输入四个数字 opt, l，r，c, 以空格隔开

若 opt = 0，表示在 第l个数字前插入数字r (c没有用)

若 opt = 1，表示询问 第 r个数字的值

输出格式

对于每次询问，输出一行一个数字表示答案

样例

此题是相隔了一个井冈山“开心”旅行，回来补的QAQ，此题一看，是不是无从下手，QAQ，数组插入的话需要遍历所插入点之前的所有的节点，这样时间效率就不是很高了，而且插入多了，块内数量不相等，时间复杂度会恢复，这就非常的恶心了，我们的分块没有用了，QAQ，那就只能进行重构了，对这个序列进行重新分块，用vector进行存储，插入的话比较方便

代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],t,n;
vector<int>op[100010];
void chonggou()
{
	int temp1=0;
	for(int i=1;i<=t;i++)
	{
		for(int j=0;j<op[i].size();j++)
		b[++temp1]=op[i][j];
		op[i].clear();
	}
	t=sqrt(temp1);
	int temp=0;
	for(int i=1;i<=t;i++)
	for(int j=1;j<=t;j++)
	op[i].push_back(b[++temp]);
	if(temp<temp1)
	{
		t++;
		while(temp<temp1)
		{
			op[t].push_back(b[++temp]);
		}
	}
}
void cha(int x,int y)
{
	int i=1;
	while(x>op[i].size())
	{
		x-=op[i].size();
		i++;
	}
	op[i].insert(op[i].begin()+x-1,y);
	if(op[i].size()>sqrt(n)*20)
	chonggou();
}
int ask(int x)
{
	int i=1;
	while(x>op[i].size())
	{
		x-=op[i].size();
		i++;
	}
	return op[i][x-1];
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	t=sqrt(n);
	int temp=0;
	for(int i=1;i<=t;i++)
	for(int j=1;j<=t;j++)
	op[i].push_back(a[++temp]);
	if(temp<n)
	{
		t++;
		while(temp<n)
		{
			op[t].push_back(a[++temp]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		int op,x,y,z;
		scanf("%d%d%d%d",&op,&x,&y,&z);
		if(op==0)
		cha(x,y);
		else
		printf("%d\n",ask(y));
	}
}