HDU – 6230 Palindrome （Manacher+主席树/树状数组）

题意
- 给一个字符串，问满足S[i]=S[2n−i]=S[2n+i−2](1≤i≤n)的子串有多少个
  - For example, $a b c b a b c$

题解

分析一下会发现，这个字符串的形式其实就是两个回文串互相刚好覆盖对称中心
求回文串的算法，我们呢不难想到Manacher，它可以O(n)求出以每个位置为对称中心的回文串
此时我们发现，最长的回文串好像与题中要求的不太一样
但其实对于某两个确定对称中心位置的最长回文串，不难发现，即使覆盖范围超出了另一回文串的中心，也一定会有子回文串满足条件
而只要满足每两个位置只统计一次，就能保证答案不重复
所以在用manacher求出对称半径数组p[]之后，问题转化为了i<j && i+p[i]+1>=j && j-p[j]+1<=i即可

我们有两种方法来统计答案

主席树（静态）

这个问题我们可以转化为求在[i+1,i+p[i]+1]区间内，回文串左端的值<=i的对称中心个数即可
即问题转化为了主席树的模板题，求[L,R]区间内<=k的数的个数
值域离散化建树，权值为i-p[i]+1(左端点值)
每次查询ask(i+p[i]+1,i)-ask(i,i)即可
记得查询前需要判断取出的值是否合法

用我的模板的TLE代码

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const ll INF = 1e18;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B); //if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);
	//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0;
	//EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(ll x) { if(x>9) outt(x/10);
	putchar(x%10+'0');
}

const int N = 500010;

int cnt, len;
char s[N*2], ss[N*4];
int p[N*4];

void init() { //将每两个字符中插入一个字符
	len = strlen(s), cnt = 1;
	ss[0] = '!';
	ss[cnt] = '#';
	for(int i=0; i<len; i++)
		ss[++cnt] = s[i], ss[++cnt] = '#';
}

void manacher() {
	int pos = 0, mx = 0;
	for(int i=1; i<=cnt; i++) {
		if(i < mx) p[i] = min(p[pos*2-i],mx-i);
		else p[i] = 1;
		while(ss[i+p[i]] == ss[i-p[i]]) p[i]++;
		if(mx < i+p[i]) mx = i+p[i], pos = i; } } struct SegmentTree { int lc, rc; // 左右子节点编号 int sum; } tree[N * 30]; int n, t, tot, a[N], b[N], root[N]; int build(int l, int r) { int p = ++tot; // 新建一个节点，编号为p，代表当前区间[l,r] tree[p].sum = 0; if (l == r) return p; int mid = (l + r) >> 1;
	tree[p].lc = build(l, mid);
	tree[p].rc = build(mid + 1, r);
	return p;
}

int insert(int now, int l, int r, int x, int delta) {
	int p = ++tot;
	tree[p] = tree[now]; // 新建一个副本
	if (l == r) {
		tree[p].sum += delta; // 在副本上修改
		return p;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta); else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta); tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum; return p; } //int ask(int p,int q,int l,int r,int L,int R) { // if(l>=L&&r<=R)return tree[p].sum - tree[q].sum; // int mid = (l+r)>>1;
//	int sum=0;
//	if(R<=mid)sum += ask(tree[p].lc,tree[q].lc,l,mid,L,R); // else if(L>mid)sum += ask(tree[p].rc,tree[q].rc,mid+1,r,L,R);
//	else sum+= ask(tree[p].rc,tree[q].rc,mid+1,r,L,R) + ask(tree[p].lc,tree[q].lc,l,mid,L,R);
//	//L R
//	return sum;
//}

int ask(int p,int q,int l,int r,int L,int k)
{
    int ans,mid=((l+r)>>1);
    if (r<=k) return tree[p].sum-tree[q].sum; if (l>k) return 0;
    ans=ask(tree[p].lc,tree[q].lc,l,mid,L,k);
    if (mid<k) ans=ans+ask(tree[p].rc,tree[q].rc,mid+1,r,1,k);
    return ans;
}


int main() {
	int Case;
	scanf("%d", &Case);
	for(int ccc=1; ccc<=Case; ++ccc) {
		ll OUT = 0;
		scanf("%s", s);
		t=0;
		tot = 0;
		n = strlen(s);
		init();
		manacher();

		for (int i = 1; i <= n; i++) {
			a[i] = i-p[i*2]/2+1;
			b[++t] = a[i];
		}
		sort(b + 1, b + t + 1); // 离散化
		t = unique(b + 1, b + t + 1) - (b + 1);
		root[0] = build(1, t); // 关于离散化后的值域建树
		for (int i = 1; i <= n; i++) {
			int x = lower_bound(b + 1, b + t + 1, a[i]) - b; // 离散化后的值
			root[i] = insert(root[i - 1], 1, t, x, 1); // 值为x的数增加1个
		}
		for (int i = 1; i <= n; i++) { int l, r; l = i; r = i+p[i*2]/2-1; int x = lower_bound(b + 1, b + t + 1, i) - b; if(b[x]>i)--x;
			if (x==t+1)--x;
			r = min(r,n);
			if(!x)continue;
			if(r<i+1) continue;
			int ans = ask(root[r], root[l], 1, t, 1,x);
			OUT += ans;
		}
		printf("%lld\n", OUT);
	}
	return 0;
}

在网上找的模板的AC代码

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const ll INF = 1e18;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B); //if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);
	//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0;
	//EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(ll x) { if(x>9) outt(x/10);
	putchar(x%10+'0');
}

const int N = 500010;

int cnt, len;
char s[N], ss[N*2];
int P[N*2];

void init() { //将每两个字符中插入一个字符
	len = strlen(s), cnt = 1;
	ss[0] = '!';
	ss[cnt] = '#';
	for(int i=0; i<len; i++)
		ss[++cnt] = s[i], ss[++cnt] = '#';
}

void manacher() {
	int pos = 0, mx = 0;
	for(int i=1; i<=cnt; i++) {
		if(i < mx) P[i] = min(P[pos*2-i],mx-i);
		else P[i] = 1;
		while(ss[i+P[i]] == ss[i-P[i]]) P[i]++;
		if(mx < i+P[i]) mx = i+P[i], pos = i; } } int sum[N*25],rt[N*25],lc[N*25],rc[N*25]; int a[N],b[N],p,node_cnt,value[N]; void build(int &t,int l, int r) { t=++node_cnt; sum[t]=0; if (l==r) return; int mid=(l+r)>>1;
	build(lc[t],l,mid);
	build(rc[t],mid+1,r);
}
int modify(int o,int l,int r) {
	int oo = ++node_cnt;
	lc[oo]=lc[o];
	rc[oo]=rc[o];
	sum[oo]=sum[o]+1;
	if (l==r) return oo;
	int mid=(l+r)>>1;
	if (p<=mid) lc[oo]=modify(lc[oo],l,mid); else rc[oo]=modify(rc[oo],mid+1,r); return oo; } int query(int u,int v,int l,int r,int k) { int ans,mid=((l+r)>>1);
	if (r<=k) return sum[v]-sum[u]; if (l>k) return 0;
	ans=query(lc[u],lc[v],l,mid,k);
	if (mid<k) ans=ans+query(rc[u],rc[v],mid+1,r,k);
	return ans;
}

int main() {
	int Case;
	scanf("%d", &Case);
	for(int ccc=1; ccc<=Case; ++ccc) {
		scanf("%s", s);
		int n = strlen(s);
		init();
		manacher();
		cnt = n;
		for(int i=1; i<=cnt; i++) {
			a[i]=i-P[i*2]/2+1;
			b[i]=a[i];
		}
		sort(b+1,b+1+cnt);
		int nn=unique(b+1,b+cnt+1)-b-1;
		node_cnt=0;
		build(rt[0],1,nn);
		for (int i=1; i<=cnt; i++) {
			p=lower_bound(b+1,b+nn+1,a[i])-b;
			rt[i]=modify(rt[i-1],1,nn);
		}
		long long ans=0;
		for (int i=1; i<=cnt; i++) { int x=lower_bound(b+1,b+nn+1,i)-b; if (x==nn+1) x--; if (b[x]>i) x--;
			if(x==0) continue;
			if(min(P[i*2]/2+i-1,cnt)<i+1) continue;
			ans=ans+query(rt[i],rt[min(P[i*2]/2+i-1,cnt)],1,nn,x);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

树状数组（动态）

将每个回文串的最左端点，以最左端点的值当作vector的索引记录下来
从1开始遍历vector，将vector[i]中的所有值拿出，在值域树状数组该值的位置上+1
统计ask(i+1i+p[i]-1) (1=<i<=len)的和即可
为什么可以这样做？是因为每个i仅仅对应一个左端点，这使得修改次数为n次，又因为i的单调能保证答案不重复（但关键还是在于点少范围大（大指的是相对于每次修改的点的个数，但是能使用树状数组的另一个原因恰恰是值域合理），契合了树状数组的使用中单点修改次数少O(n)，查询区间和操作复杂度低O(n^long)的特点）

代码

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const ll INF = 1e18;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);
	//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);
	//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0;
	//EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(ll x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}

const int N = 500010;

int cnt, len;
char s[N*2], ss[N*4];
int p[N*4];

void init() { //将每两个字符中插入一个字符
	len = strlen(s), cnt = 1;
	ss[0] = '!';
	ss[cnt] = '#';
	for(int i=0; i<len; i++)
		ss[++cnt] = s[i], ss[++cnt] = '#';
}

void manacher() {
	int pos = 0, mx = 0;
	for(int i=1; i<=cnt; i++) {
		if(i < mx) p[i] = min(p[pos*2-i],mx-i);
		else p[i] = 1;
		while(ss[i+p[i]] == ss[i-p[i]]) p[i]++;
		if(mx < i+p[i]) mx = i+p[i], pos = i;
	}
}


vector<int>v[N];
int c[N];
int ask(int x){
	int ans = 0;
	for( ; x; x-=x&-x)ans+=c[x];
	return ans;
}
void add(int x,int y){
	for(; x<=N-10;x+=x&-x)c[x]+=y;
}


int main() {
	int Case;
	scanf("%d", &Case);
	for(int ccc=1; ccc<=Case; ++ccc) {
		ll OUT = 0;
		scanf("%s", s);
		int n = strlen(s);
		init();
		CLR(c);
		manacher();
		rep(i,1,n) v[i].clear();
		rep(i,1,n) v[i-p[i*2]/2+1].push_back(i);
		rep(i,1,n){
			for(int j=0;j<v[i].size();++j) add(v[i][j],1);
			OUT+=ask(i+p[i*2]/2-1)-ask(i);
		}
		printf("%lld\n", OUT);
	}
	return 0;
}

发表评论 取消回复

发表评论取消回复