#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define V vector
#define Int long long
#define rep(i,a,b) for(Int i=(Int)(a); i<(Int)(b); i++)
#define all(x) (x).begin(), (x).end()
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define int long long
#define pii pair<int,int>
const int N = 1e5+5;
const int MOD = 1e9+7;
int SEED, SINV[N];
int bpow(int a,int b){
int ret = 1;
while(b){
if(b&1) ret = ret*a%MOD;
a = a*a%MOD; b /= 2;
}
return ret;
}
int inv(int a){
return bpow(a, MOD-2);
}
int n;
string s;
// hash of ori string and reversed string
int h[N], rh[N];
int qry(int l,int r){
int ret = h[r];
if(l) ret -= h[l-1];
(ret *= SINV[l] )%=MOD;
if(ret<0) ret+=MOD;
return ret;
}
int rqry(int l,int r){
int ret = rh[l];
if(r+1<n) ret -= rh[r+1];
(ret *= SINV[n-1-r] )%=MOD;
if(ret<0) ret+=MOD;
return ret;
}
// add arithmetic sequence to range
// point query
int loss[N];
#define mid ((tl+tr)/2)
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
int lzl[2*N], lzr[2*N];
void upd(int l,int r,int addl,int addr,int v=0,int tl=0,int tr=n-1){
int a = addl, b = (r-l==0 ? 0:(addr-addl)/(r-l));
rep(i,l,r+1){
loss[i] += a + (i-l)*b;
}
return;
if(r<tl || tr<l) return;
if(l<=tl && tr<=r){
int a = addl, b = (r-l==0 ? 0:(addr-addl)/(r-l));
addl = a + (tl-l)*b;
addr = a + (tr-l)*b;
lzl[v] += addl; lzr[v] += addr;
return;
}
upd(l,r,addl,addr, lc,tl,mid);
upd(l,r,addl,addr, rc,mid+1,tr);
}
void build_loss(int v=0,int tl=0,int tr=n-1){
return;
if(tl==tr){
// dbg(st[v]);
loss[tl] = lzl[v];
return;
}
if(lzl[v] || lzr[v]){
upd(tl,tr,lzl[v],lzr[v], lc,tl,mid);
upd(tl,tr,lzl[v],lzr[v], rc,mid+1,tr);
lzl[v] = lzr[v] = 0;
}
build_loss(lc,tl,mid);
build_loss(rc,mid+1,tr);
}
} segtree;
// find longest [tl..l] == rev([r..tr]);
int f(int l,int r){
int i=l, j=r;
while(0<=i && j<n && s[i]==s[j]) i--,j++;
return l-i;
int len = 0;
for(int J=1<<20; J; J/=2)
if(len+J<=n && l-len-J+1>=0 && r+len+J-1<n &&
rqry(l-len-J+1,l)==qry(r,r+len+J-1)) len+=J;
return len;
}
signed main(){
srand(time(0));
SEED = rand()%MOD;
// SEED = 3;
SINV[0] = 1; SINV[1] = inv(SEED);
rep(i,2,N){
(SINV[i] = SINV[i-1]*SINV[1] )%=MOD;
}
assert(SEED*SINV[1]%MOD==1);
// n = 5;
// segtree.upd(1,3, 1,5);
// segtree.upd(2,4, 1,5);
// segtree.build_loss();
// cout << "LOSS[]" << nl;
// rep(i,1,5) cout << i << " " << loss[i] << nl;
// return 0;
cin >> s;
n = s.size();
int mul = 1;
rep(i,0,n){
if(i) h[i] = h[i-1];
(h[i] += mul*s[i] )%=MOD;
(mul *= SEED )%=MOD;
}
mul = 1;
for(int i=n-1; i>=0; i--){
if(i+1<n) rh[i] = rh[i+1];
(rh[i] += mul*s[i] )%=MOD;
(mul *= SEED )%=MOD;
}
// dbg(qry(1,1)); dbg(rqry(1,1));
// return 0;
// initial form
int ans = 0;
// segtree.qry(idx) = loss
// mp[{idx,char}] = profit
map<pii,int> mp;
// even length palindrome
rep(i,1,n){
// [l..i-1] == rev([i..r])
int len = f(i-1,i);
int l = i-len, r = i+len-1;
// dbg(i); dbg(len);
// dbg(l); dbg(r);
// cout << nl;
ans += len;
if(l<=i-1) segtree.upd(l,i-1, 1,len);
if(i<=r) segtree.upd(i,r, len,1);
// if char were changed
if(0<=l-1 && r+1<n){
int tlen = f(l-2,r+2)+1;
// dbg(tlen);
mp[{l-1,s[r+1]}] += tlen;
mp[{r+1,s[l-1]}] += tlen;
}
// cout << nl;
}
// cout << "##########" << nl;
// odd length palindrome
rep(i,0,n){
// [l..i] == rev([i..r])
int len = f(i,i);
int l = i-len+1, r = i+len-1;
// dbg(i); dbg(len);
// dbg(l); dbg(r);
// cout << nl;
ans += len;
segtree.upd(i,i, len-1,len-1);
if(l<=i-1) segtree.upd(l,i-1, 1,len-1);
if(i+1<r) segtree.upd(i+1,r, len-1,1);
// if char were changed
if(0<=l-1 && r+1<n){
int tlen = f(l-2,r+2)+1;
// dbg(tlen);
mp[{l-1,s[r+1]}] += tlen;
mp[{r+1,s[l-1]}] += tlen;
}
}
// dbg(ans);
// get answer
segtree.build_loss();
int maxdelta = 0;
for(auto[pr,cnt] : mp){
auto[i,c] = pr;
int delta = cnt - loss[i];
// if(delta>maxdelta){
// dbg(cnt); dbg(loss[i]);
// dbg(i); dbg((char)(c));
// }
maxdelta = max(maxdelta, delta);
}
ans += maxdelta;
cout << ans << nl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
1496 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1520 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
1608 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
9868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
