本文主要是介绍数列分块入门 6（LibreOj-6282），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入、单点询问、数据随机生成。
【输入格式】
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 ai，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。
若 opt=0，表示在第 l 个数字前插入数字 r（c 忽略）
若 opt=1，表示询问位于 ar 的值（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【数据范围与提示】
对于 100% 的数据，1<=n<=100000,-2^31<=other,ans<=2^31-1。
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;int block,lastBlock;//block为块的长度,lastBlock为最后的块
int a[N*2];//存放数列元素，考虑插入操作，数组大小扩大两倍
vector<int> V[N];//V[i][j]表示元素在第i块中的第j个位置
void init(int n){//分块block=sqrt(n);//块的长度lastBlock=(n-1)/block+1;//最后的块for(int i=1;i<=n;i++)//第i个元素在第几块中V[(i-1)/block+1].push_back(a[i]);
}
void rebuild(){//重新分块int cnt=0;for(int i=1;i<=lastBlock;i++){//将位置向量中已有的元素存储回a[i]for(int j=0;j<V[i].size();j++)a[++cnt]=V[i][j];V[i].clear();//情况位置向量}init(cnt);//分块
}
pair<int,int> query(int L){int cnt=1;while(L>V[cnt].size()){L-=V[cnt].size();cnt++;}int blockNum=cnt;//块序号int elementNum=L-1;//块中元素位置pair<int,int> pos(blockNum,elementNum);return pos;
}
void Insert(int L,int R){pair<int,int> pos=query(L);//找到插入位置int blockNum=pos.first;//块序号int elementNum=pos.second;//块中元素位置V[blockNum].insert(V[blockNum].begin()+elementNum,R);if(V[blockNum].size()>10*block)//如果插入太多，会导致块变得过大，需要重新分块rebuild();
}int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);init(n);lastBlock=(n-1)/block+1;for(int i=1;i<=n;i++){int op;int left,right,x;scanf("%d",&op);scanf("%d%d%d",&left,&right,&x);if(op==0)Insert(left,right);else if(op==1){pair<int,int> pos=query(right);printf("%d\n",V[pos.first][pos.second]);}}return 0;
}
这篇关于数列分块入门 6（LibreOj-6282）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
