题目描述
blablabla
样例
//无论插入多少个树,都是idx=k-1后的数删掉 标下标为k就是按插入顺序的
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int e[N],ne[N],head,idx;
void init()
{
head=-1;
idx=0;
}
void add_head(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];//not ne[idx]=ne[idx-1];否则超时
ne[k]=idx;//not ne[idx-1]=idx;否则超时
idx++;
}
void remove(int k)
{
ne[k]=ne[ne[k]];
}
int main()
{
init();
int m;
cin>>m;
char op;
int k,x;
while(m--)
{
cin>>op;
if(op=='H')//not if(op='H')否则输出全是H
{
cin>>x;
add_head(x);
}
else if(op=='D')
{
cin>>k;
if(k==0) head=ne[head];//需要特判删除头节点==头节点指向下一个的结点
remove(k-1);
}
else if(op=='I')
{
cin>>k>>x;
add(k-1,x);//下标是从0开始的
}
//cout<<op<<endl;
}
for(int i=head;i!=-1;i=ne[i])//not for(int i=0;i<e[].size())
{
cout<<e[i]<<' ';
}
cout<<endl;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla