一行超人

回文自动机

搞清楚几个定义就很好搞了。

每个节点是一个回文串。

len[i]表示i所表示回文串的长度。

fail[i]表示i所表示的回文串的右部分最长的后缀满足这个后缀对称过来也是一个在原串中出现过的回文串的编号。

我是语文渣

go[x][i]表示在x两侧各添加一个i字符后所形成的在原串中出现过的回文串的编号。

为了处理奇数和偶数的情况，新建节点0和1.len分别为0和-1，然后fail[0]=1.

last表示当前串的最长回文后缀。

反正个人感觉比SAM简单到不知道哪里去了。

建的时候和AC自动机一个样。自己yy估计也不是很难。我比较懒就学习了别人的代码。

 

BZOJ3676: [Apio2014]回文串

裸题。贴一下模板把

struct huiwen
{
	int n,tot,last,len[maxn],fail[maxn],s[maxn],go[maxn][26],cnt[maxn];
	huiwen()
	{
		tot=-1;
		len[++tot]=0;
		len[++tot]=-1;
		fail[0]=1;
		s[n=0]=-1;
		last=0;
	}
	inline int find(int x)
	{
		while(s[n-len[x]-1]!=s[n])x=fail[x];
		return x;
	}
	inline void add(int x)
	{
		s[++n]=x;
		int now=find(last);
		if(!go[now][x])
	    {
	    	int t=++tot;
			len[t]=len[now]+2;
			fail[t]=go[find(fail[now])][x];
	    	go[now][x]=t;
	    }
	    last=go[now][x];
	    cnt[last]++;
	}
	inline void work()
	{
		for3(i,tot,0)cnt[fail[i]]+=cnt[i];
		ll ans=0;
		for0(i,tot)ans=max(ans,(ll)cnt[i]*len[i]);
		cout<<ans<<endl;
	}
}T;

BZOJ2565: 最长双回文串

每加入一个字符的时候len[last]就表示以该字符结尾的最长回文子串。所以我们正反各搞一边就好了。常熟略大没跑过我的manacher

哈哈我也会在blog里用捂脸熊啦

A1255. 拉拉队排练

继续模板走起。

A1393. Palisection

刚开始写了个暴力，直接查询相交的对数。每次加入一个字符就向上爬，顺便算ans。果断T了QAQ

然后看题解发现真是傻逼，我们先倒着插入一遍，然后令f[i]表示以>=i开头的回文子串的个数。

f[i]=f[i+1]+cnt[i] cnt[i]=cnt[fail[i]]+1 cnt[i]表示i向上跳多少次就没了

然后再顺着插入一遍，每次插入之后ans+=cnt[i]*f[i+1] 就完了。

但这样做在CF上过不了，卡内存。。。等我去学习manacher的姿势过掉这道题

这题写的我真是舒爽

先补集转化。考虑枚举右边的，那么左边的与他不相交的充要条件就是右端点<=它的左端点。

那么不妨设sum[i]表示右端点<=i的回文子串的个数，那么对于一个中心i来说，他对ans的贡献是

sum[i-p[i]]+sum[i-p[i]+1]+……+sum[i-1]。我们记录一下前缀和就好了。

然而sum[i]怎么求？

我们先考虑计算以i结尾的回文子串的个数cnt[i]。

对于一个回文中心i，他会让cnt[i]到cnt[i+p[i]-1]都++。

那我们就差分一下就好了。（所以说，离线做区间加一个等差数列要知道是可以二阶差分之后O（n）做掉的）

注意分隔符十分让人蛋疼，最好manacher之后将它转化为原串的回文子串再做。

于是代码写出来就这么丑了

int n,m,a[maxn],p[maxn],b[maxn];
char s[maxn];
struct rec{int l,r,f;}c[maxn];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    n=read();scanf("%s",s);m=0;
    for0(i,n-1)b[++m]=s[i],++m;
    int mx=0,id=0;
    for0(i,m)
    {
    	if(mx>i)p[i]=min(p[2*id-i],mx-i);else p[i]=1;
    	while(i-p[i]>=0&&i+p[i]<=m&&b[i-p[i]]==b[i+p[i]])p[i]++;
    	if(i+p[i]>mx)mx=i+p[i],id=i;
    }
    for0(i,m)c[i]=(rec){(i>>1)+1,(i+p[i]-1)>>1,i&1};
    int k=-1;
    for0(i,m)
    {
    	if(c[i].l>c[i].r)continue;
    	swap(c[i],c[++k]);
    }
    for0(i,k)a[c[i].l]++,a[c[i].r+1]--;
    for1(i,n)(a[i]+=a[i-1])%=mod;
    for1(i,n)(a[i]+=a[i-1])%=mod;
    for1(i,n)(a[i]+=a[i-1])%=mod;
    int ans=0;
    for0(i,k)if(c[i].f)(ans+=a[c[i].l-1]-a[c[i].l-(c[i].r-c[i].l+1)-1])%=mod;
    else (ans+=a[c[i].l-2]-a[c[i].l-(c[i].r-c[i].l+1)-1-1])%=mod;
    cout<<(((ll)(a[n]-a[n-1])*(a[n]-a[n-1]-1)/2%mod-ans+mod)%mod+mod)%mod<<endl;
    return 0;
}

codeforces 某gym G题

题目就是求两个串的公共回文子串的数量。（本质相同位置不同算不同）

类似于后缀自动机，我们可以插入一个串之后last归0.然后插入另一个串。然后乘一下就可以了。

所以说也可以拓展到树上？诸神眷顾的幻想乡#2

 

可持久化treap

看了Memphis 大爷的代码讲解，感觉不旋转的treap的很优越的样子。于是又去把序列终结者A了一遍。

int n,tot,mx[maxn],rt,v[maxn],h[maxn],s[maxn],l[maxn],r[maxn],tag[maxn];
bool rev[maxn];
pa t1,t2;
inline void pushup(int x)
{
    mx[x]=max(v[x],max(l[x]?mx[l[x]]:-inf,r[x]?mx[r[x]]:-inf));
    s[x]=s[l[x]]+s[r[x]]+1;
}
inline void add(int x,int z)
{
    v[x]+=z;mx[x]+=z;tag[x]+=z;
}
inline void rever(int x)
{
    rev[x]^=1;
    swap(l[x],r[x]);
}
inline void pushdown(int x)
{
    if(rev[x])
    {
        rever(l[x]);rever(r[x]);
        rev[x]=0;
    }
    if(tag[x])
    {
        add(l[x],tag[x]);add(r[x],tag[x]);
        tag[x]=0;
    }
}
inline int getnew(int x)
{
    ++tot;mx[tot]=v[tot]=x;h[tot]=rand();l[tot]=r[tot]=rev[tot]=tag[tot]=0;s[tot]=1;
    return tot;
}
void build(int n)
{
    static int sta[maxn];
    int top=0;
    for1(i,n)
    {
        int x=getnew(0),last=0;
        while(top&&h[sta[top]]>h[x])pushup(last=sta[top--]);
        if(top)r[sta[top]]=x;
        l[x]=last;
        sta[++top]=x;
    }
    while(top)pushup(sta[top--]);
    rt=sta[1];
}
inline int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(h[x]<h[y])
    {
        pushdown(x);
        r[x]=merge(r[x],y);
        pushup(x);
        return x;
    }else
    {
        pushdown(y);
        l[y]=merge(x,l[y]);
        pushup(y);
        return y;
    }
}
inline pa split(int x,int k)
{
    if(!x)return pa(0,0);
    pushdown(x);pa t;
    if(s[l[x]]>=k)
    {
        t=split(l[x],k);
        l[x]=t.second;
        pushup(x);
        t.second=x;
    }else
    {
        t=split(r[x],k-s[l[x]]-1);
        r[x]=t.first;
        pushup(x);
        t.first=x;
    }
    return t;
}
inline int takeout(int l,int r)
{
    t1=split(rt,l-1);
    t2=split(t1.second,r-l+1);
    return t2.first;
}
int main()
{
    n=read();int T=read();
    build(n);
    while(T--)
    {
        int ch=read();
        if(ch==1)
        {
            int x=read(),y=read(),w=read(),z=takeout(x,y);
            add(z,w);
            rt=merge(merge(t1.first,z),t2.second);
        }else
        {
            int x=read(),y=read(),z=takeout(x,y);
            if(ch==2)rever(z);
            else printf("%d\n",mx[z]);
            rt=merge(merge(t1.first,z),t2.second);
        }
    }
    return 0;
}

 

K-D tree 的应用

发现我原来只会用K-Dtree来查询高维空间的最远点和最近点，于是来补一下K-D tree的其他姿势啦

BZOJ4066: 简单题

mikia强制在线。刚开始想分块，后来发现分块技巧太捉急，想不出来。然后去搜题解。

发现是n+e出的题，K-Dtree一语惊醒梦中人。

学习了K-Dtree的rebuild（）姿势，维基百科上说测了几发发现阈值设为0.7比较好

再大一点还没有不重构快。

重构函数大致长这样：

inline bool cmp(int x,int y){return t[x][cur]<t[y][cur];}
inline int build(int l,int r,int dir)
{
	cur=dir;
	nth_element(p+l,p+mid,p+r+1,cmp);int k=p[mid];
	t[k].dir=dir;
	t[k].l=l<mid?build(l,mid-1,dir^1):0;
	t[k].r=mid<r?build(mid+1,r,dir^1):0;
	pushup(k);
	return k;
}	
inline void dfs(int k)
{
	if(!k)return;
	dfs(t[k].l);
	p[++cnt]=k;
	dfs(t[k].r);
}
inline void rebuild(int &k)
{
	cnt=0;
	dfs(k);
	k=build(1,cnt,t[k].dir);
}

所以也就是说K-D tree可以查询高维空间中给定区域的权值和，最大值，最小值等等。尽管复杂度并不是那么靠谱，但实际运行效果还是不错

注意query函数的格式：

if（该区域完全被查询区域覆盖）返回该区域的记录信息。

else {判断该点是否在区域内，在的话用他的信息更新ans。然后判断是否需要进入左右子树，递归下去即可。}

BZOJ2850: 巧克力王国

给出n个点（xi，yi）以及它们的权值，每次查询在直线Ax+By+C==0直线下方的点的权值和。

显然这也是个平面区域求点权和的问题，所以我们可以K-D tree刚正面了。

实现的时候不用分情况，有技巧。具体可以参见HZWER的代码。

BZOJ3489: A simple rmq problem

据说此题出题人是树套树套树？领悟了高维空间区域查询之后来用K-Dtree水过！爽！

 

既然K-D tree支持高维空间区域查询，那么我们就可以把一下题目抽象到一个高维空间上转化成一个区间最值/和的查询问题。

就可以用K-Dtree来水了！