题解 P1198 【[JSOI2008]最大数】

· · 题解

这题不难吧

解法和最大异或和差不多

解法：

  1. 先不管插入，只有查询

    这时候我们可以跑ST表，线段树······

    但是我用了Trie

    将int以32位01串插入(以下将Trie中数字称为"串")

    设latest[x]为以x为根的子树的latest[]的最大值

    latest[x]=max\{latest[trie[x][0],latest[trie[x][1]\}

    然后我们对所有串建立可持久化Trie，root[n]就是第n次插入串后的Trie的根，查询时从root[n]出发就好了

    查询时，要使答案更大，就要尽量走trie[x][1],(在Trie中即向右走)，同时不能超过[N-L+1,N]的区间

    这时候latest[]就有用了

    当我们走到节点x时(设latest[x]>N-L+1)，如果latest[trie[x][1]]>N-L+1，那么x=trie[x][1](向右走)

    否则只能放弃这一位，x=trie[x][0](向左走)

    走到叶子节点后，从根到当前节点形成的串就是答案

  2. 查询&插入

    查询都解决了，插入还难吗

    回到上面，我们在初始化的时候是将每个数字按顺序插入的

    我们把插入指令和初始化一样处理，不就好了吗

至此，问题就玄学解决啦

Talk\ is\ cheap\ ,show\ you\ the\ code. 
#include<algorithm>
#include<cstdio>
#include<cctype>
#define N 200010
using namespace std;
int trie[N*32][2],latest[N*32];
int s[N],root[N],n,m,mod,tot;
inline int cread()
{char c=getchar();while(!isupper(c))c=getchar();return c=='A';}
void insert(int k,int p,int q)//可持久化Trie
{
    if(k<0){latest[q]=n;return;}
    int c=s[n]>>k&1;
    if(p)trie[q][c^1]=trie[p][c^1];
    trie[q][c]=++tot;
    insert(k-1,trie[p][c],trie[q][c]);
    latest[q]=max(latest[trie[q][0]],latest[trie[q][1]]);//计算latest[]
}
int ask(int p,int k,int limit)
{
    if(k<0)return s[latest[p]];
    if(latest[trie[p][1]]>=limit)return ask(trie[p][1],k-1,limit);//贪心
    else return ask(trie[p][0],k-1,limit);
}
int main()
{
    int x,t=0;
    latest[0]=-1;root[n=0]=++tot;
    scanf("%d%d",&m,&mod);
    while(m--)
    {
        if(cread())
        {
            scanf("%d\n",&x);root[++n]=++tot;s[n]=(x+t)%mod;//不打括号出人命
            insert(31,root[n-1],root[n]);
        }
        else
        {
            scanf("%d",&x);
            t=ask(root[n],31,n-x+1);printf("%d\n",t);
        }
    }
    return 0;//养成好习惯
}

思路改进：

通过分析可以发现，因为查询的右边界始终是当时状态下的n，所以我们可以直接用Trie代替可持久化Trie.

代码略.