ADALIST - Ada and List

这道题时限6.5s，激动人心啊，好多人STL一顿乱写AC，哈哈，如果熟悉双端队列的话这道题其实是很水的。

题意：n个数的数列，然后接下来Q次操作，每次可以将某个数x插入第k个位置，那后面的数往后移。也可以删除第k个位置上的数，还可以是查询第k个位置上的数。

这就是双端队列的裸模板啊。下面简单介绍一下双端队列。

deque双端队列容器

deque与vector一样，采用线性表顺序存储结构，但deque采用分块的线性存储结构来存储数据，每个deque块用map块管理。deque块在头部和尾部都可以插入和删除元素而不需要移动其他元素。使用deque需要声明头文件包含“#include<deque>”。

1.创建deque对象：

①：创建没有任何元素的deque对象：deque<int/double>d。

②：创建具有n个元素的deque对象:deque<int>d(10)//创建具有10个整型元素的deque对象d。

③：创建具有n个元素的deque对象并赋初值:deque<int>d(10,8);10个整型元素的deque对象每个元素值为8。

2.插入元素

①：使用push_back()从尾部插入元素，会不断扩张队列。

②：使用push_front()从头部插入元素，其余元素后移。

③：d.insert(q.begin()+k,x)//从中间k位置插入元素x。

3.遍历元素

①：以数组形式遍历：for(int i=0;i<d.size();i++) cout<<d[i]<<" ";

②：以前向迭代器的方式遍历：for(it=d.begin();it!=d.end();it++) cout<<*it<<" ";//it为迭代器，声明省略。

③：采用反向迭代器对双端队列容器进行反向遍历。

for(deque<int>::reverse_iterator rit=d.rbegin();rit!=q.rend();rit++) cout<<*rit<<" ";

4.删除元素：从首部、尾部、中间删除，也可以清空双端对列容器。

①：采用pop_front()从头部删除元素。

②：采用pop_back()从尾部删除元素。

③：使用erase()从中间删除元素，其参数是迭代器位置。d.erase(d.begin()+k)。

④：清空deque对象：d.clear()。

deque容器有基本常用操作都在这了，熟悉了这些这个题就是水题了，不过也要看时间复杂度，对于时间复杂度较高的题还是不建议使用stl。

int main()

{

    int n,Q,k,p,x;

    while(~scanf("%d%d",&n,&Q))

    {

        deque<int>q;

        for(int i=1; i<=n; i++)

        {

            scanf("%d",&x);

            q.push_back(x);

        }

        while(Q--)

        {

            scanf("%d",&k);

            if(k==1)

            {

              scanf("%d%d",&k,&x);

              q.insert(q.begin()+k-1,x);

            }

            else if(k==2)

            {

               scanf("%d",&k);

               q.erase(q.begin()+k-1);

            }

            else

            {

                scanf("%d",&k);

                printf("%d\n",q[k-1]);

            }

        }

    }

    return 0;

}