主席树做法
刚开始是听说了要用manacher采取写的，但是不难看出要使用manacher，因为题目要求的1个半回文串，其实就是两个回文中心的交集，你要找两个回文中心，让它们的回文半径可以互相覆盖即可。问题转化成了对于一个回文中心，它覆盖的左侧的所有回文中心中（ 向右覆盖的范围超过i ）这样的点的数量。这样就变成了求区间中大于x的数的个数，可以用主席树解决。
#include<iostream> #include<cstring> #include <string> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e6+20; const int maxm=2e7+20; char s[maxn],s_new[maxn]; int p[maxn]; int init() { int len=(int)strlen(s); s_new[0]='$'; s_new[1]='#'; int j=2; for(int i=0;i<len;i++) { s_new[j++]=s[i]; s_new[j++]='#'; } s_new[j]=0; return j; } int manacher() { int len=init(); int id=0,mx=0; for(int i=1;i<len;i++) { if(i<mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1; while(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++; if(mx<i+p[i]) { id=i; mx=i+p[i]; } } return len; } int n,m,cnt; int tree[maxn],ls[maxm],rs[maxm],sum[maxm]; void update(int k,int pre,int &now,int l,int r){ now=++cnt; ls[now]=ls[pre]; rs[now]=rs[pre]; sum[now]=sum[pre]+1; if(l==r){ return; } int m=(l+r)>>1; if(k<=m) update(k,ls[pre],ls[now],l,m); else update(k,rs[pre],rs[now],m+1,r); } int query(int a,int b,int l,int r,int L,int R){ if(L<=l&&r<=R){ return sum[b]-sum[a]; } int ans=0; int mid=(l+r)>>1; if(mid>=L) ans+=query(ls[a], ls[b], l, mid, L, R); if(mid<R) ans+=query(rs[a], rs[b], mid+1, r, L, R); return ans; } int main() { int T; cin>>T; while(T--){ cnt=0; tree[0]=ls[0]=rs[0]=sum[0]=0; scanf("%s",s); int len=manacher(); m=len/2; ll ans=0; for(int i=1;i<m;i++) { int L=i-p[i*2]/2+1; if(L!=i) update(L,tree[i-1],tree[i],1,m); else tree[i]=tree[i-1]; } for(int i=1;i<m;i++){ int R=i+p[i*2]/2-1; int t=query(tree[i], tree[R], 1, m, 1, i); ans+=t; } printf("%lld ",ans); } }
但是我的板子一直过不了，一直TLE，借用了以为其他人的主席树板子才能过，好迷啊。
借用模版：https://blog.csdn.net/know_heng/article/details/78590061
树状数组离线做法
我觉得是主席树好想一点，因为很容易就可以转化到主席树经典模型上，这个离线树状数组好处就是非常的短，但是不容易想。
考虑你要求的东西，在一个区间中小于x的数的个数，也就是说，你大于x的数字都没有作用对这个查询，所以我们在考虑这个查询的时候，把小于x的加入就行了。所以可以把所有离线查询按x排序，逐步按从小到大的顺序加入所有元素，并按前缀和计算答案就行了。
#include<iostream> #include<cstring> #include <string> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e6+20; char s[maxn],s_new[maxn]; int p[maxn]; int init() { int len=(int)strlen(s); s_new[0]='$'; s_new[1]='#'; int j=2; for(int i=0;i<len;i++) { s_new[j++]=s[i]; s_new[j++]='#'; } s_new[j]=0; return j; } int manacher() { int len=init(); int id=0,mx=0; for(int i=1;i<len;i++) { if(i<mx) p[i]=min(p[2*id-i],mx-i); else p[i]=1; while(s_new[i-p[i]]==s_new[i+p[i]]) p[i]++; if(mx<i+p[i]) { id=i; mx=i+p[i]; } } return len; } int n; int a[maxn],c[maxn]; //对应原数组和树状数组 int lowbit(int x){ return x&(-x); } void updata(int i,int k){ //在i位置加上k while(i <= n){ c[i] += k; i += lowbit(i); } } int getsum(int i){ //求A[1 - i]的和 int res = 0; while(i > 0){ res += c[i]; i -= lowbit(i); } return res; } typedef pair<int, int> P; P t[maxn]; int main() { int T; cin>>T; while(T--){ int m; scanf("%s",s); int len=manacher(); m=len/2; n=m; ll ans=0; for(int i=1;i<m;i++) t[i]=make_pair(i-p[i*2]/2+1, i); sort(t+1, t+m); for(int i=0;i<m;i++) c[i]=0; int cnt=1; for(int i=1;i<m;i++) { while(cnt<m&&t[cnt].first<=i){ // cout<<t[cnt].second<<endl; updata(t[cnt].second, 1); cnt++; } int R=i+p[i*2]/2-1; // cout<<R<<" "<<getsum(R)<<endl; ans+=getsum(R)-getsum(i); } printf("%lld ",ans); } }