[洛谷P1198/BZOJ1012][JSOI2008] 最大数 - 树状数组/线段树?

时间：2024-04-12 12:36:00

其实已经学了树状数组和线段树，然而懒得做题，所以至今没写多少博客

Description

现在请求你维护一个数列，要求提供以下两种操作：

1、 查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：L不超过当前数列的长度。(L>=0)

2、 插入操作。

语法：A n

功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

限制：n是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

Input&Output

Input

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)

接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。

Output

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

Sample

Input

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

Output

96
93
96

Solution

  • 本来一开始打的线段树，但洛谷的加强数据T了最后一个点，所以改用了树状数组。因为只在队列末尾插入数据，所以其实线段树有点大材小用了。树状数组可以维护区间最大值，查询时通过不断更新ret即可。

  • 90分线段树(也可能是本蒟蒻太水了)：

    #include<iostream>
#include<cstdio>
#include<algorithm>
#define maxm 200001
using namespace std;
typedef long long ll;
struct node{
ll mx;
int l,r,lc,rc;
node(){
    lc=rc=-1;
}
}tree[maxm<<1];
ll m,d,L,n,sum,t;
char c;
inline ll rd()
{
ll x=0;bool f=0;
char c=getchar();
while(c<'0'||c>'9'){
    if(c=='-')f=1;
    c=getchar();
}
while(c>='0'&&c<='9'){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
}
return f?-x:x;
}
int cnt;
int rt=cnt++;
void pushup(int cur)
{
int lc=tree[cur].lc,rc=tree[cur].rc;
tree[cur].mx=max(tree[lc].mx,tree[rc].mx);
tree[cur].l=tree[lc].l;
tree[cur].r=tree[rc].r;
}
void build(int l,int r,int cur)
{
if(l==r){
    tree[cur].mx=0;
    tree[cur].l=tree[cur].r=l;
    return;
}
int mid=(l+r)>>1;
tree[cur].lc=cnt++;
tree[cur].rc=cnt++;
build(l,mid,tree[cur].lc);
build(mid+1,r,tree[cur].rc);
pushup(cur);
}
void upd(int pos,ll c,int cur)
{
if(tree[cur].l==tree[cur].r)
{
    tree[cur].mx=c;
    return;
}
int mid=(tree[cur].l+tree[cur].r)>>1;
if(pos<=mid)upd(pos,c,tree[cur].lc);
if(pos>mid)upd(pos,c,tree[cur].rc);
pushup(cur);
}
ll query(int l,int r,int cur)
{
if(tree[cur].l>=l&&tree[cur].r<=r){
    return tree[cur].mx;
}
int mid=(tree[cur].l+tree[cur].r)>>1;
ll mx=0;
if(l<=mid)mx=max(mx,query(l,r,tree[cur].lc));
if(r>mid)mx=max(mx,query(l,r,tree[cur].rc));
return mx;
}
int main()
{
m=rd();
d=rd();
build(1,200000,rt);
for(int i=1;i<=m;++i)
{
    cin>>c;
    if(c=='Q'){
        L=rd();
        t=query(sum-L+1,sum,rt);
        printf("%d\n",t);
    }
    else if(c=='A'){
        n=rd();
        ll tmp=(n%d+t%d)%d;
        upd(sum+1,tmp,rt);
        sum++;
    }
}
return 0;
}

  • 树状数组：

    #include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 200005
using namespace std;
typedef long long ll;
ll mx(ll a,ll b)
{
return (a>b)?a:b;
}
inline ll rd()
{
ll x=0;char c=getchar();
bool f=false;
while(c<'0'||c>'9'){
    if(c=='-')f=true;
    c=getchar();
}
while(c>='0'&&c<='9'){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
}
return f?-x:x;
}
ll b[maxn],d;
int sum;
int lowbit(int x)
{
return x&-x;
}
int add(ll v)
{
for(int x=sum;x;x-=lowbit(x))
    b[x]=mx(b[x],v);
}
int query(int pos)
{
ll ans=0;
for(int x=sum-pos+1;x<=sum;x+=lowbit(x))
    ans=mx(ans,b[x]);
return ans;
}
int main()
{
int m,p;
char q;
ll t=0;
scanf("%d%lld",&m,&d);
for(int i=1;i<=m;++i)
{
    cin>>q;
    if(q=='A'){
        sum++;
        ll n;
        scanf("%lld",&n);
        add((n+t)%d);
    }
    else{
        scanf("%d",&p);
        t=query(p);
        printf("%lld\n",t);
    }
}
return 0;
}

    写了快读居然没用上

相关文章