bzoj1012(洛谷P1198)

Author : hiang

bzoj1012     洛谷 P1198

Time Limit: 3 Sec     Memory Limit: 162 MB

Description

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

1、 查询操作。

语法：Q L

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

限制：L不超过当前数列的长度。

2、 插入操作。

语法：A n

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

限制：n是非负整数并且在长整范围内。

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

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

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

Sample Output

96
93
96

 

 

这里提供四种思路：

1.线段树     2.ST表     3.单调队列+并查集     4.树状数组

一、线段树

这道题虽然可以用线段树的思路来做，但其实连建树都不用，因为一开始数列中并没有数，只需要在数列末尾加数，并查询已有数列即可，所以我只用了一个数组来存储区间最大值。

注：本题洛谷的数据非常变态，数据加了全是负数和L为0的情况，所以wa了无数发....以下代码是bzoj的AC代码，本代码在洛谷提交的话会全部MLE，需要把char改成字符数组，具体原因不详。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const long long inf=2*1e9;
#define LL long long
LL d,val[800005];
int m,ans;//ans为数组元素个数
char c;
void add(int p,int ll,int rr,int x,LL k)
{//p为下标，ll，rr为p对应区间的左右端点
    if(ll==rr)
    {
        val[p]=k;
        return;
    }
    int mid=(ll+rr)>>1;
    if(x<=mid)
        add(p<<1,ll,mid,x,k);
    if(x>mid)
        add(p<<1|1,mid+1,rr,x,k);
    val[p]=max(val[p<<1],val[p<<1|1]);
}
LL query(int p,int pl,int pr,int ll,int rr)
{//pl，pr为p对应区间左右端点，ll，rr为要查询的区间左右端点
    LL maxx=-inf;
    if(pl>=ll&&pr<=rr)
        return val[p];
    int mid=(pl+pr)>>1;
    if(ll<=mid)
        maxx=max(maxx,query(p<<1,pl,mid,ll,rr));
    if(rr>mid)
        maxx=max(maxx,query(p<<1|1,mid+1,pr,ll,rr));
    return maxx;
}
int main()
{
    LL n,t=0;
    scanf("%d%lld",&m,&d);
    for(int i=0;i<m;i++)
    {
        scanf("%*c%c%lld",&c,&n);//bzoj上能过，洛谷要改成字符数组
        if(c=='A')
        {
            n=(n+t)%d;
            ans++;
            add(1,1,m,ans,n);
        }
        else
        {
            t=query(1,1,m,ans-n+1,ans);
            printf("%lld
",t);
        }
    }
    return 0;
}

二、ST表

ST表是一种用于解决RMQ(查询区间最值)的算法，运用了dp思想，查询复杂度仅为O(1)，本代码比线段树快了0.8秒左右，代码也更为简洁

简单介绍一下原理：

用一个数组st[i][j]来存储区间[i,i+(1<<j)-1]的最值，而该区间最值就等于[i,i+(1<<(j-1))-1]和[1<<(j-1),i+(1<<j)-1]的最大值，存储区间长度为2^j，所以预处理复杂度为O(nlogn)

查询时只需要将需查询区间[x,y]分成两部分，令k=(int)log2(y-x+1)，区间[x,y]的长度就在2^k~2^(k+1)范围内，所以我们就可以将区间分成长度为2^k的两部分，即[x,x+(1<<k)-1]，[y-(1<<k)+1,y]，两部分可能有重合，只要保证覆盖了区间[x,y]即可

因为每次修改复杂度与预处理相同，所以不支持在线修改，但因为本题只需要在最后添加元素，所以我们可以反向建ST表(参考了大佬的思路)，即st[i,j]存储[i-(1<<j)+1,i]的最值，这样每次修改时前面元素的ST表不受影响，每次修改的复杂度仅为O(logn)

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int m,ans;
char c[2];
LL d,st[200005][21];
void add(int u,LL k)
{
    st[u][0]=k;
    for(int j=1;u-(1<<j)>=0;j++)
        st[u][j]=max(st[u][j-1],st[u-(1<<(j-1))][j-1]);
}
LL ask(int l,int r)
{
    int k=(log(r-l+1))/log(2);
    return max(st[r][k],st[l+(1<<k)-1][k]);
}
int main()
{
    LL n,t=0;
    scanf("%d%lld",&m,&d);
    for(int i=0;i<m;i++)
    {
        scanf("%s%lld",c,&n);
        if(c[0]=='A')
        {
            n=(n+t)%d;
            ans++;
            add(ans,n);
        }
        else
        {
            t=ask(ans-n+1,ans);
            printf("%lld
",t);
        }
    }
    return 0;
}

三、单调队列+并查集

本题只要求在数列末尾加数，所以很容易联想到单调队列，本代码比ST表又快了0.3秒左右

具体思路：

令队列中小于等于新元素的数全部出队，再另新元素入队，这样可以得到一个递减队列，队列中的每个数就代表数列中从该元素开始到末尾的最大值

假如要查询第x个元素到末尾的最大值，那么我们只需要从第x个元素开始，找第一个在单调队列里出现的数，该数即为该区间最大值

但如果要从x开始一个个遍历的话复杂度过高，这里就可以用并查集，将第i个元素与它后面第一个比它大的元素放到一个集合里，这样查询x时就可以直接找到后面第一个比它大的元素，并一直往后找，直到找不到更大的数为止

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
int m,d,ans,s;//ans为数列元素个数，s为队列元素个数
int a[MAXN];//原始数列
int q[MAXN];//单调队列，存储下标
int pre[MAXN];//并查集，存储数列中i之后第一个比a[i]大的数的下标
char c[2];
int ufind(int x)
{
    while(x!=pre[x])
        x=pre[x];
    return x;
}
int main()
{
    int n,t=0;
    scanf("%d%d",&m,&d);
    for(int i=0;i<m;i++)
    {
        scanf("%s%d",c,&n);
        if(c[0]=='A')
        {
            a[++ans]=(n+t)%d;
            pre[ans]=ans;//每个数的上级初始化为自己
            while(s>0&&a[q[s]]<a[ans])
            {
                pre[q[s]]=ans;
                s--;
            }//将队列中小于新元素的上级改为新元素，并出队
            q[++s]=ans;//新元素入队
        }
        else
        {
            t=a[ufind(ans-n+1)];
            printf("%d
",t);
        }
    }
    return 0;
}

 四、树状数组

树状数组可用于单点修改，区间查询，本题符合该特点

需要注意的是，查询区间是从L到末尾，所以要反向建树状数组，即更新时从后往前更新，查询时从前往后查询

AC代码：

#include<bits/stdc++.h>
using namespace std;
int m,ans,d;
char c[2];
int s[200005];//树状数组
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int k)
{
    for(int i=x;i>0;i-=lowbit(i))
        s[i]=max(s[i],k);
}
int query(int x)
{
    int maxx=-1e9;
    for(int i=x;i<=ans;i+=lowbit(i))
        maxx=max(maxx,s[i]);
    return maxx;
}
int main()
{
    int n,t=0;
    scanf("%d%d",&m,&d);
    for(int i=0;i<m;i++)
    {
        scanf("%s%d",c,&n);
        if(c[0]=='A')
        {
            n=(n+t)%d;
            ans++;
            update(ans,n);
        }
        else
        {
            t=query(ans-n+1);
            printf("%d
",t);
        }
    }
    return 0;
}