高位前缀和解决这样的问题：
给定 \(f_i\)，其中 \(i\in[0,2^n-1]\)，求解 \(\sum\limits_{j\in i}f_j\)。
考虑一维前缀和：
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
二位前缀和：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]+=sum[i-1][j];
}
}
三维前缀和：
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]=sum[i][j][k-1]+a[i][j][k];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[i][j-1][k];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[i-1][j][k];
}
}
}
可以发现上面那个问题就是每一维大小都为2的 \(n\) 维前缀和。
因此可以考虑枚举每一维，然后再加上这一维的贡献就好了。
for(int i=1;i<=n;i++){
for(int S=0;S<1<<n;S++){
if(S>>(i-1)&1){
continue;
}
f[S|1<<(i-1)]+=f[S];
}
}
Yet Another Substring Reverse
因为字符不重复，因此不用考虑它们的排列顺序，即翻转子串就是将两个不交的子串连到一块。这里不交既指位置不交又指字符集不交。但显然字符集不交则一定位置不交。因此只用考虑对每一个字符集处理最大长度。高位前缀最大值即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,maxm=(1<<20)+5;
int n,dp[maxm];
char s[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
scanf(" %s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
for(int j=i,S=0;j;j--){
if(S>>(s[j]-'a')&1){
break;
}
S|=1<<(s[j]-'a');
dp[S]=i-j+1;
}
}
for(int i=1;i<=20;i++){
for(int S=0;S<1<<20;S++){
if(S>>(i-1)&1){
continue;
}
dp[S|1<<(i-1)]=max(dp[S|1<<(i-1)],dp[S]);
}
}
int ans=0;
for(int S=1;S<=(1<<20)-2;S++){
ans=max(ans,dp[S]+dp[((1<<20)-1)^S]);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}