题解 P1198 【[JSOI2008]最大数】

abandentsky · 2019-09-27 15:37:12 · 题解

思路：写的线段树总是超时，splay又不会写。树状数组虽然也可以手动维护区间最值，但是树状数组只能从左到右的更新，所以只好用楼下大佬的想法，用RMQ处理了。从右到左更新，每插入一个数，就以这个数为起点向左更新。每次其实只更新一个点。不再是RMQ的两层循环。dp[i][j]表示从i点开始，长度为(1<<j)的区间最大值。得记住是从i开始向左数(1<<j)个哦。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define MAXN  200005
using namespace std;

int n,M,D,t;
int dp[MAXN][20];

void add(int u,int tt)        //在u位置插入大小为tt的数
{
    dp[u][0]=tt;
    for(int i=1;(1<<i)<=n;i++)
    {
        dp[u][i]=max(dp[u][i-1],dp[u-(1<<(i-1))][i-1]);
    }
}

int query(int L,int R)            //查询区间，区间长度(1<<j)一定要从左右全部覆盖
{
    int log=0;
    while((R-L+1)>=(1<<(log+1)))       //提前log+1完了直接使用
        log++;
    return max(dp[R][log],dp[L+(1<<log)-1][log]);      //一定要完全覆盖查询的区间哦
}

int main()
{
    scanf("%d %d",&M,&D);
    char ch;
    int pp;
    t=0;
    n=0;
    while(M--)
    {
        cin>>ch;
        cin>>pp;
        if(ch=='A')
        {
            pp+=t;
            pp%=D;
            n++;
            add(n,pp);
        }
        else if(ch=='Q')
        {
            if(n==0)
            {
                printf("0\n");
               continue;
            }
            t=query(n-pp+1,n);
            printf("%d\n",t);
        }
    }
    return 0;
}