数列分块入门 6
链接：LibreOj6282
题目描述
给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问。
输入格式
第一行输入一个数字n。
第二行输入n个数字，第i个数字为 a[i]，以空格隔开。
接下来输入n行询问，每行输入四个数字op、l、r、c，以空格隔开。
若 op==0，表示在第l个数字前插入数字r（ c忽略）。
若 op==1，表示询问a[r]的值（ l 和c忽略）。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例输入
4 1 2 2 3 0 1 3 1 1 1 4 4 0 1 2 2 1 1 2 4
样例输出
2 3
分析：
之前分块题目得数据都是存放同一个数组上得。 这题得用vector(或者其他?)分开存放每个块得数据。 这样得好处是每个块可以使用stl得很多操作。就比如这题的插入。 但是一个块如果一直插入数据，块的数据量会一直增大。 所以在块的数据多大的时候(比如大于三个block大小)，我们就重新分块。 这样能保证之后的操作耗时不会太大。
ps：不过这题不重新分块也能过(但是会花两倍多时间)。
完整代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<memory>
#include<utility>
#include<functional>
#include<iterator>
typedef long long ll
;
const int inf
=0x3f3f3f3f;
const int inn
=0x80808080;
using namespace std
;
const int maxm
=1e5+5;
int belong
[maxm
];
int mark
[maxm
];
int a
[maxm
*2];
int block
,num
;
int n
;
int all
;
vector
<int>temp
[maxm
];
void build(){
block
=sqrt(n
);
num
=all
/block
;
if(all
%block
)num
++;
for(int i
=1;i
<=n
;i
++){
belong
[i
]=(i
-1)/block
+1;
temp
[belong
[i
]].push_back(a
[i
]);
mark
[belong
[i
]]++;
}
}
void reset(){
int cnt
=1;
for(int i
=1;i
<=num
;i
++){
int len
=temp
[i
].size();
for(int j
=0;j
<len
;j
++){
a
[cnt
++]=temp
[i
][j
];
}
temp
[i
].clear();
mark
[i
]=0;
}
}
void update(int x
,int val
){
int now
=1;
while(x
>mark
[now
]){
x
-=mark
[now
];
now
++;
}
temp
[now
].insert(temp
[now
].begin()+x
-1,val
);
mark
[now
]++;
all
++;
if(mark
[now
]>2*block
){
reset();
build();
}
}
void ffind(int x
){
int now
=1;
while(x
>mark
[now
]){
x
-=mark
[now
];
now
++;
}
printf("%d\n",temp
[now
][x
-1]);
}
int main(){
scanf("%d",&n
);
all
=n
;
for(int i
=1;i
<=n
;i
++){
scanf("%d",&a
[i
]);
}
build();
for(int i
=1;i
<=n
;i
++){
int d
,x
,y
,c
;
scanf("%d%d%d%d",&d
,&x
,&y
,&c
);
if(d
==0){
update(x
,y
);
}else{
ffind(y
);
}
}
return 0;
}
