题目链接：https://loj.ac/problem/6282
参考博客：http://www.cnblogs.com/stxy-ferryman/p/8560551.html
这里如果用数组的话元素右移肯定会超时，如果用链表查询时O（n），n次询问就是O（n^2），然后刚刚又瞟了几眼别人的博客，用分块的话主要好像是有查询位置，插入元素，重构三个操作，查询就是找我们要的这个点在第几层的第几个位置（用的是vector），大概是√n的时间复杂度，因为分成了√n块；然后找到位置之后就可以插入，也是√n,因为插入时要把元素右；然后因为极端数据数据有可能只在一个块里插入元素，所以这个块里面的元素可能远远多于其他块，导致查询时候的时间复杂度变成n，所以要把所有元素重新分块，所以重构的时间复杂度是√n，我看他们都是当一个块里的元素大于10*√n，前面10这个系数应该是可以自己看清况给的，这样的话重构次数是小于√n次的，整体的时间复杂度不太会加，^_^，反正就是比n^2低好多就是了...。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 100005
/*struct point{
int u,w;
};
bool operator <(const point &s1,const point &s2)
{
if(s1.w!=s2.w)
return s1.w>s2.w;
else
return s1.u>s2.u;
}*/
int lump[maxn],a[maxn*];//lump数组用不到，可以不要，a数组是等下重构时用来存所有元素的
vector<int>ve[];//存每一层的元素
int n,m,k,t,block,Max; //Max是用来存最多有多少层
pair<int,int> query(int l)//这个函数是用来寻找第l个元素在第几层第几个，返回一个pair<int,int>类型
{ //它的fist表示层数，second表示第几个，vector里元素从0开始
int pos=;
while(l>ve[pos].size())
{
l-=ve[pos].size();
pos++;
}
return make_pair(pos,l-);
}
void rebuild()//重构操作
{
int top=;
for(int i=;i<=Max;i++)
{
for(int j=;j<ve[i].size();j++)
{
a[++top]=ve[i][j];//把所有元素存起来
}
ve[i].clear();//记得清空
}
int block1=sqrt(top);//新的块的大小
for(int i=;i<=top;i++)
{
ve[(i-)/block1+].push_back(a[i]);
}
Max=(top-)/block+;
}
void insert(int l,int r)
{
pair<int,int>w=query(l);//找到位置
ve[w.first].insert(ve[w.first].begin()+w.second,r);//插入元素
if(ve[w.first].size()>block*)//如果块太大就重构
rebuild();
}
int find(int l,int r)
{
pair<int,int>w=query(r);
return ve[w.first][w.second];
}
int main()
{
scanf("%d",&n);
block=sqrt(n);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
lump[i]=(i-)/block+;
ve[lump[i]].push_back(x);
}
Max=(n-)/block+;
for(int j=;j<=n;j++)
{
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if(!op)
insert(l,r);
else
{
int ans=find(l,r);
printf("%d\n",ans);
}
}
return ;
}