BZOJ 1012【线段树】

题意：

Q L 询问数列最后 L 个数中最大的数。

A n 将 n + t ( t_init = 0 )，然后插到最后去。

思路：

感觉动态地插入，很有问题。

数组地长度会时常变化，但是可以先预处理就是有2e5个结点（最多）。

然后就是插咯？

它保证query 的时候 L < n（当前数组的长度）

水题。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e5+20;

LL mod;

struct Seg{

    LL Max;

    int Left,Right;

}q[N*4];

void Build(int num,int Left,int Right)

{

    q[num].Left=Left;q[num].Right=Right;

    if(Left==Right)

        return;

    int Mid=(Left+Right)>>1;

    Build(num<<1,Left,Mid);

    Build(num<<1|1,Mid+1,Right);

}

void Update(int num,int k,LL w)

{

    if(q[num].Left==q[num].Right&&q[num].Left==k){

        q[num].Max=w;

        return;

    }

    int Mid=(q[num].Left+q[num].Right)>>1;

    if(Mid>=k)

        Update(num<<1,k,w);

    else

        Update(num<<1|1,k,w);

    q[num].Max=max(q[num<<1].Max,q[num<<1|1].Max);

}

int query(int num,int Left,int Right)

{

    if(q[num].Left>=Left && q[num].Right<=Right)

        return q[num].Max;

    int Mid=(q[num].Left+q[num].Right)>>1;

    if(Mid>=Right)

        return query(num<<1,Left,Right);

    else if(Mid<Left)

        return query(num<<1|1,Left,Right);

    else

        return max(query(num<<1,Left,Mid),query(num<<1|1,Mid+1,Right));

}

int main()

{

    char x[5];

    int m;

    int n=0,L;

    LL k,t=0;

    Build(1,1,200000);

    scanf("%d%lld",&m,&mod);

    while(m--)

    {

        scanf("%s",x);

        if(x[0]=='A'){

            scanf("%lld",&k);

            k=(k+t)%mod;

            n++;

            Update(1,n,k);

        }

        else

        {

            scanf("%d",&L);

            int s=n-L+1;

            t=query(1,s,n);

            printf("%lld\n",t);

        }

    }

    return 0;

}

巴特西

BZOJ 1012【线段树】

最新文章

热门文章