lightoj1087 【线段树】

题意：

给你n个数，然后给你q个询问，有两种询问：

a：表示在右边插入一个数

c：表示从左边拿出一个数，然后输出；

思路：

一开始在想，自己手上的黑科技：线段树和树状数组

线段树上的操作：

求区间最大，没说区间第几个啊；

树状数组：

搞一发前缀和，妈个鸡，树状数组还需要知道下标和位置；

还有什么：

数组，感觉黑科技没什么了；

然后。。。

线段树维护区间有多少个数，好像很对啊，初始化建树就是n+q长度的区间，然后每次插入就是第n+i个，每次插入，删除都是log级别的；

后来线段树打完居然没什么错，感动啊；

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e5+10;

struct SegT{

    bool flag;

    int left,right;

    int num,v;

};

SegT q[N*4];

int n,Q;

void Build(int num,int L,int R)

{

    q[num].left=L;

    q[num].right=R;

    if(L==R)

    {

        if(L<=n)

        {

            scanf("%d",&q[num].v);

            q[num].flag=true;

            q[num].num=1;

            return;

        }

        else

        {

            q[num].flag=false;

            q[num].num=0;

            return;

        }

    }

    int mid=(L+R)/2;

    Build(2*num, L,mid);

    Build(2*num+1,mid+1,R);

    q[num].num=q[2*num].num+q[2*num+1].num;

}

void add(int num,int id,int x)

{

    if(q[num].left==id&&q[num].left==q[num].right)

    {

        q[num].flag=true;

        q[num].v=x;

        q[num].num=1;

        return;

    }

    int mid=(q[num].left+q[num].right)/2;

    if(mid>=id)

        add(2*num,id,x);

    else

        add(2*num+1,id,x);

    q[num].num=q[2*num].num+q[num*2+1].num;

}

int DEL(int num,int id)

{

    if(q[num].left==q[num].right)

    {

        q[num].num=0;

        q[num].flag=false;

        return q[num].v;

    }

    int ans=0;

    if(q[2*num].num>=id)

        ans=DEL(2*num,id);

    else

        ans=DEL(2*num+1,id-q[2*num].num);

    q[num].num=q[2*num].num+q[2*num+1].num;

    return ans;

}

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        char txp[5];

        int temp;

        scanf("%d%d",&n,&Q);

        Build(1,1,n+Q);

        printf("Case %d:\n",cas++);

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

        {

            scanf("%s%d",txp,&temp);

            if(txp[0]=='a')

                add(1,n+i,temp);

            else

            {

                if(q[1].num<temp)

                    puts("none");

                else

                    printf("%d\n",DEL(1,temp));

            }

        }

    }

    return 0;

}

巴特西

lightoj1087 【线段树】

最新文章

热门文章