您的位置: 首页  >  IT文章  >  【BZOJ】1012: [JSOI2008]最大数maxnumber 树状数组求区间最值

【BZOJ】1012: [JSOI2008]最大数maxnumber 树状数组求区间最值

分类: IT文章 • 2022-07-17 09:43:30

题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1012

题意:维护一个数列，开始时没有数值，之后会有两种操作，

Q L :查询数列末k位的最大值；

A n:上一次查询的结果加上n添加到数列的末尾；第一次添加时，认为t = 0;

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96
思路:保留输入的原值和用树状数组处理过的mx[i];其中mx[i]所管辖的范围就是lowbit(i)的值，即(i - lowbit(i),i];这样在之后查找时，每次先和原值比较，之后和比较比较的区间就是lowbit(i),但里面要两重循环来模拟整个比较的个数。如区间长度为10，比较的长度为 1,1,2,4,1,1.
#include<bits/stdc++.h>
using namespace std;
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define ok puts(" ok")
#define bug puts(" bug ")
#define INF 0x3f3f3f3f
#define esp 1e-8

typedef long long ll;
const int maxx=200200;
ll num[maxx],len=0,mx[maxx];
int lowbit(int i){return i&(-i);}
void modify(int pos)//更改1~pos的max
{
    mx[pos]=num[pos];
    for(int j=1;j<lowbit(pos);j<<=1)
    {
        mx[pos]=max(mx[pos],mx[pos-j]);
    }
}
int query(int l,int r)
{
    ll ans=-INF;
    //lowbit()会出现1 2 4,这里面出现的间隔，就需要要两层循环里避免中间值；
    //并且lowbit的值代表的就是该值代表的数的个数；
    while(l<=r)
    {
        ans=max(ans,num[r]);
        for(--r;l+lowbit(r)<=r;r-=lowbit(r))
        ans=max(ans,mx[r]);
    }
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ll m,mod;
    scanf("%lld%lld",&m,&mod);
    ll t=0,x;char op[2];
    for(int i=1;i<=m;i++)
    {
        scanf("%s%lld",op,&x);
        if(op[0]=='A')
        {
            num[++len]=(t+x)%mod;
            modify(len);
        }
        else{
            t=query(len-x+1,len);
            printf("%lld
",t);
        }
    }
    return 0;
}

相关推荐