广州外贸网站建设公司,深圳福田园岭网站建设,珠海做网站的网络公司,中国企业500强2022正题
题目链接:https://www.luogu.com.cn/problem/CF1286E 题目大意
定义一个字符串sss的权值为对于每个sL∼Rs1∼R−L1s_{L\sim R}s_{1\sim R-L1}sL∼Rs1∼R−L1的区间#xff0c;会产生miniLRwi\min_{iL}^Rw_iminiLRwi的贡献。
现在开始时sss为空串#xff0c…正题
题目链接:https://www.luogu.com.cn/problem/CF1286E 题目大意
定义一个字符串sss的权值为对于每个sL∼Rs1∼R−L1s_{L\sim R}s_{1\sim R-L1}sL∼Rs1∼R−L1的区间会产生miniLRwi\min_{iL}^Rw_iminiLRwi的贡献。
现在开始时sss为空串nnn次往sss后加入一个字符和往www序列加入一个数字然后求这个串的贡献。
强制在线
1≤n≤6×105,1≤wi2301\leq n\leq 6\times 10^5,1\leq w_i2^{30}1≤n≤6×105,1≤wi230 解题思路
我们在每次加入字符后考虑所有后缀的贡献然后考虑加入一个字符后后缀产生贡献的变化。
一个想法是对于原来的后缀[n−len,n−1][n-len,n-1][n−len,n−1]如果slen1sns_{len1}s_nslen1sn那么新的后缀[n−len,n][n-len,n][n−len,n]就会产生贡献否则就不会。除了这些以外还有如果s1sns_1s_ns1sn那么后缀[n,n][n,n][n,n]也会产生贡献。
也就是一次操作最多增加一个会产生后缀的贡献我们取考虑怎么维护其他以前的后缀。
权值方面比较简单[n−len,n−1][n-len,n-1][n−len,n−1]的贡献转到[n−len,n][n-len,n][n−len,n]的贡献无非就是对wiw_iwi取min\minmin也就是我们要一个能支持加入删除全部取minminmin的数据结构。其实暴力维护都行我们用map记录贡献为kkk的后缀有多少个然后每次暴力把大于wiw_iwi的都修改掉即可这样势能分析一下就知道是对的。
现在第二个问题是我们怎么知道每次要删除的后缀是哪些。我们建立出KMP的failfailfail树那么原本产生贡献的后缀肯定都在n−1n-1n−1点到根节点的路径上我们维护一个lasi,clas_{i,c}lasi,c表示节点iii往祖先走的路上遇到的第一个xxx满足sx1cs_{x1}csx1c的xxx然后我们就可以一直往上走找到要删除的后缀了。
用RMQRMQRMQ维护一下后缀的贡献即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includemap
#define ll long long
using namespace std;
const ll N6e510,mod1e18;
ll n,lg[N],nxt[N],las[N][26],ans;
char s[N];mapll,ll mp;int f[N][20];
pairll,ll sum;
pairll,ll operator(const pairll,ll x,const ll y)
{return make_pair((x.firsty)%mod,x.second(x.firsty)/mod);}
ll operator%(const pairll,ll x,const ll p)
{return (x.first%p(x.second%p)*(mod%p)%p)%p;}
void print(pairll,ll x)
{if(x.second) printf(%lld%018lld\n,x.second,x.first);else printf(%lld\n,x.first);
}
ll Ask(ll l,ll r){ll zlg[r-l1];return min(f[r][z],f[l(1z)-1][z]);
}
signed main()
{scanf(%lld,n);for(ll i2;in;i)lg[i]lg[i1]1;ll mask(1ll30),z0;char op[2];ll w0;scanf(%s%lld,op,w);mp[w];anssum.firstw;s[1]op[0];f[1][0]w;printf(%lld\n,ans);for(ll p2;pn;p){scanf(%s%lld,op,w);char cop[0];c(c-97sum%26)%2697;s[p]c;ww^(sum%mask);f[p][0]w;for(ll i1;(1i)p;i)f[p][i]min(f[p][i-1],f[p-(1i-1)][i-1]);while(zs[z1]!s[p])znxt[z];nxt[p](z(s[z1]s[p]));for(ll j0;j26;j)las[p][j]las[nxt[p]][j];las[p][s[nxt[p]1]-a]nxt[p];for(ll j0;j26;j){if(jac)continue;for(ll xlas[p-1][j];x;xlas[x][j]){ll valAsk(p-x,p-1);mp[val]--;ansans(-val);}}while(mp.size()){mapll,ll::iterator itmp.end();it--;pairll,ll x*it;if(x.firstw){ansans(-(x.first-w)*x.second);mp[w]x.second;mp.erase(it);}else break;}if(s[p]s[1])mp[w],ansansw;sumsumans;print(sum);}return 0;
}
