题目描述
给出一个长为 nn 的数列，以及 nn 个操作，操作涉及单点插入，单点询问，数据随机生成。
输入格式
第一行输入一个数字 nn。
第二行输入 nn 个数字，第 ii 个数字为 a_iai，以空格隔开。
接下来输入 nn 行询问，每行输入四个数字 \mathrm{opt}opt、ll、rr、cc，以空格隔开。
若 \mathrm{opt} = 0opt=0，表示在第 ll 个数字前插入数字 rr（cc 忽略）。
若 \mathrm{opt} = 1opt=1，表示询问 a_rar 的值（ll 和 cc 忽略）。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
样例输入
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4样例输出
2
3数据范围与提示
对于 100\%100% 的数据，1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}1≤n≤100000,−231≤others、\mathrm{ans} \leq 2^{31}-1ans≤231−1。
代码:
//#6282. 数列分块入门 6-单点插入，单点查询，数据随机生成
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+; int n,m;
int a[maxn*],b[maxn],tag[maxn],pos[maxn];
vector<int> vec[maxn]; void rebuild()
{
memset(a,,sizeof(a));
int h=;
for(int i=;i<=m+;i++){
for(auto it:vec[i]){
a[++h]=it;
}
vec[i].clear();
}
m=sqrt(h);
for(int i=;i<=h;i++)
pos[i]=(i-)/m+;
for(int i=;i<=h;i++){
vec[pos[i]].push_back(a[i]);
}
} pair<int,int> find_pos(int r)
{
int i=,cnt;
while(){
if(r>vec[i].size()){
r-=vec[i].size();
i++;
}
else{
cnt=i;
break;
}
}
return make_pair(cnt,r);
} void update(int l,int r)
{
pair<int,int> pr=find_pos(l);
vec[pr.first].insert(vec[pr.first].begin()+pr.second-,r);
if(vec[pr.first].size()>*m) rebuild();
} int query(int r)
{
pair<int,int> pr=find_pos(r);
return vec[pr.first][pr.second-];
} int main()
{
scanf("%d",&n);
m=sqrt(n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
pos[i]=(i-)/m+;
}
for(int i=;i<=n;i++){
vec[pos[i]].push_back(a[i]);
}
for(int i=;i<=n;i++){
int op,l,r,c;
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op==){
update(l,r);
}
else{
printf("%d\n",query(r));
}
}
return ;
} /*
10
1 3 4 2 5 7 11 3 5 1
0 1 5 1
1 1 7 2
0 3 9 1
1 4 8 7
1 1 10 6
1 3 5 3
1 5 9 7
1 6 12 6
1 2 7 4
1 3 4 5 7
7
3
4
11
1
5
3
*/