ppip @ 2022-07-09 12:01:17
rt。
#include <bits/stdc++.h>
using namespace std;
const int N(1e5),K{316};
list<vector<int>> bt;
pair<list<vector<int>>::iterator,vector<int>::iterator> Find(int k)
{
auto it{bt.begin()};
for (;it!=bt.end();++it)
{
k-=it->size();
if (k<=0)
{
k+=it->size();
break;
}
}
return {it,it->begin()+k-1};
}
void rebuild(list<vector<int>>::iterator t)
{
auto ers{t->begin()+t->size()/2};
copy(ers,t->end(),back_inserter(*bt.emplace(next(t))));
t->erase(ers,t->end());
}
void push_back(int p)
{
if (bt.size()==0) bt.emplace_back();
prev(bt.end())->push_back(p);
if (prev(bt.end())->size()>K) rebuild(prev(bt.end()));
}
void Insert(int k,int x)
{
auto it{Find(k)};
it.first->insert(it.second,x);
if (it.first->size()>K) rebuild(it.first);
}
int main()
{
int n;cin>>n;
for (int i{1};i<=n;++i)
{
int p;scanf("%d",&p);
push_back(p);
}
while (n--)
{
int op,l,r,c;scanf("%d %d %d %d",&op,&l,&r,&c);
if (op==0) Insert(l,r);
else printf("%d\n",*Find(r).second);
}
return 0;
}
其中
copy(ers,t->end(),back_inserter(*bt.inserte(next(t),{})));
RE,但是替换为
copy(ers,t->end(),back_inserter(*bt.emplace(next(t))));
后正常,蒟蒻不得其解。