M_sea

洛谷4036 [JSOI2008]火星人
LuoguBZOJ吐槽同样的代码在Luogu上交了三次,第一次TLE on #7,第二次TLE on #8,第三次...
扫描右侧二维码阅读全文
20
2018/12

洛谷4036 [JSOI2008]火星人

Luogu

BZOJ

吐槽

同样的代码在Luogu上交了三次,第一次TLE on #7,第二次TLE on #8,第三次AC

在BZOJ上交了一次,A了。

分析

平衡树来维护字符串,对每个节点维护$\mathrm{hash}$值。

$hash[i]=hash[lson]+val\cdot base^{size[rson]}+hash[rson]\cdot base^{size[lson]+1}$

当然本题轻度卡常,不如用unsigned int自然溢出。

对于每个查询操作,二分长度,然后把区间$\mathrm{split}$出来比较$\mathrm{hash}$值即可。

对于替换操作,删掉原来的字符,再插入一个新的字符。

对于插入操作,直接插入就行。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXL=200000+10;
const int MAXN=200000+10;
const int BASE=27;
typedef unsigned int uint;

char s[MAXL];
int h[MAXN];

struct fhq_treap {
    int sz[MAXN],val[MAXN],rnd[MAXN];
    int ch[MAXN][2];
    uint hash[MAXN];
    int cnt,root;
    fhq_treap() { this->cnt=this->root=0; }
    inline int new_node(int v) { sz[++cnt]=1,val[cnt]=hash[cnt]=v,rnd[cnt]=rand(); return cnt; }
    inline void pushup(int x) {
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        hash[x]=hash[ch[x][0]]*h[sz[ch[x][1]]+1]+h[sz[ch[x][1]]]*val[x]+hash[ch[x][1]];
    }
    inline void split(int now,int k,int& x,int& y) { //排名分裂
        if (!now) { x=y=0; return; }
        if (k<=sz[ch[now][0]]) y=now,split(ch[now][0],k,x,ch[now][0]);
        else x=now,split(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);
        pushup(now);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    inline void insert(int p,char c) {
        int x,y; split(root,p,x,y);
        root=merge(merge(x,new_node(c-'a'+1)),y);
    }
    inline void del(int p) {
        int x,y,z;
        split(root,p,x,z),split(x,p-1,x,y);
        y=merge(ch[y][0],ch[y][1]),root=merge(merge(x,y),z);
    }
    inline uint query(int L,int R) {
        int x,y,z;
        split(root,R,y,z),split(y,L-1,x,y);
        uint rt=hash[y];
        root=merge(merge(x,y),z);
        return rt;
    }
    inline int check(int x,int y,int mid) {
        return query(x,x+mid-1)==query(y,y+mid-1);
    }
} T;

int main() {
    scanf("%s",s+1); int len=strlen(s+1);
    int m=read();
    h[0]=1; for (re int i=1;i<MAXN;++i) h[i]=h[i-1]*BASE;
    for (re int i=1;i<=len;++i) T.insert(i,s[i]);
    while (m--) {
        char op[2]; scanf("%s",op);
        if (op[0]=='Q') {
            int x=read(),y=read();
            int L=0,R=min(len-x,len-y)+1,ans;
            while (L<=R) {
                int mid=(L+R)>>1;
                if (T.check(x,y,mid)) ans=mid,L=mid+1;
                else R=mid-1;
            }
            printf("%d\n",ans);
        }
        else if (op[0]=='R') {
            int x=read(); char c=getchar();
            while (!isalpha(c)) c=getchar();
            T.del(x),T.insert(x-1,c);
        }
        else if (op[0]=='I') {
            int x=read(); char c=getchar(); ++len;
            while (!isalpha(c)) c=getchar();
            T.insert(x,c);
        }
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 43 PM

1 条评论

  1. Jayfeather

    %%%

发表评论