[Str记录]CF1286E Fedya the Potter Strikes Back

· · 个人记录

题意 ： 给定一个字符串 S 和一个序列 W，初始时它们都为空。

你需要完成 n 次操作。第 i 次操作在 S 后面添加一个字符 S_i，在序列 W 后面添加一个数字 W_i。

定义一个子区间 [L,R] 的可疑度为： 若子串 [L,R] 和前缀 [1,R-L+1] 相同，则其可疑度为 min_{i=L}^{R} W_i。否则其可疑度为0。

每次操作后，你都要求出当前的串的所有子区间的可疑度之和。

强制在线，n\leq 6\times 10^5 ，时限\texttt{4s}。

鸽了大半年的题 /cy

不难发现题意等价于动态 push_back 并维护 \rm Border 权值和。

考虑动态维护 \rm KMP 自动机。

当加入字符 S_i 时， \rm Bd 集合会有如下变化。

（由于加入 \rm Bd 的次数是 O(n) 的，删除的次数也自然是 O(n) 的）

如何快速找到该删除那些 \rm Bd 呢？

原串的 \rm Bd 对应 \rm KMP 自动机上的终止链。（即位置 |S| 向上跳形成的链）

记节点 u 对应前缀的下一个字符为 {\rm nxt}(u)。

记节点 u 最近的，\rm nxt 不同的祖先为 {\rm difpre}(u)。

需要删除的节点即为终止链上 {\rm nxt}(u)\neq c 的点。可以从位置 |S| 向上一路跳跃，若 {\rm nxt}(u)\neq c 则删除该点对应 \rm Bd，否则跳至 {\rm difpre}(u)。

找到未被删除的最长 \rm Bd ，即为 \rm KMP 树上位置 |S| 的祖先。

当加入 S_{i+1} 时才维护位置 i （记对应节点为 t_i）的 {\rm difpre}。

若 {\rm nxt}(t_i)\neq {\rm nxt}\big(fa(t_i)\big) ，则 {\rm difpre}(t_i)=fa(t_i) ，否则 {\rm difpre}(t_i)={\rm difpre}\big(fa(t_i)\big)。

接下来需要维护权值总和。

对于剩下未删除的 \rm Bd ，权值都需要对 W_i 取 \min。

需要我们维护这样的一个数据结构 ： 支持删除，插入，全体取\min ,求和。

用 std::map 维护每个权值及其出现次数，暴力取 \min ，复杂度是均摊正确的。

删除某个 \rm Bd 时需要获知其权值，这可以使用单调栈 + 二分来得到。

时间复杂度 O(n\log n) ,空间复杂度 O(n)。

答案可能爆 long long ，需要 __int128。

#include<algorithm>
#include<cstdio>
#include<map>
#define lll __int128
#define MaxN 600500
using namespace std;
const lll mask=(1<<30)-1;
struct MinDS
{
  struct Data{int x,p;}stk[MaxN];
  int top,n;
  void pb(int x){
    while(top&&stk[top].x>=x)top--;
    stk[++top]=(Data){x,++n};
  }
  int qry(int tl)
  {
    int l=1,r=top,mid;
    while(l<r){
      mid=(l+r)>>1;
      if (stk[mid].p<tl)l=mid+1;
      else r=mid;
    }return stk[r].x;
  }
}T;
map<int,int> o;
lll ans,now;
void del(int tl){
  int w=T.qry(tl);
  now-=w;o[w]--;
}
#define fir first
#define sec second
void tmin(int w)
{
  if (o.empty())return ;
  map<int,int>::iterator it,it2=o.end();it2--;
  int cnt=0;
  while(1){
    it=it2;
    if (it->fir<=w)break;
    cnt+=it->sec;
    now-=1ll*it->sec*it->fir;
    if (it==o.begin())
      {o.erase(it);break;}
    else {
      it2=it;it2--;
      o.erase(it);
    }
  }o[w]+=cnt;
  now+=1ll*w*cnt;
}
int n,fa[MaxN],dif[MaxN];
char s[MaxN];
void print(lll n)
{
  if (n==0){puts("0");return ;}
  int s[105],tot=0;
  while(n){s[++tot]=n%10;n/=10;}
  for (int i=tot;i;i--)printf("%d",s[i]);
  puts("");
}
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    int w;
    scanf("%s%d",&s[i],&w);
    s[i]=(s[i]-'a'+ans)%26+'a';
    w^=(ans&mask);
    if (i>1)
      dif[i-1]=(s[i]==s[fa[i-1]+1]) ? dif[fa[i-1]] : fa[i-1];
    int u=fa[i-1];
    while(u){
      if (s[u+1]!=s[i]){del(i-u);u=fa[u];}
      else {
        if (!fa[i])fa[i]=u+1;
        u=dif[u];
      }
    }
    if (i>1&&s[1]==s[i]){
      o[w]++;now+=w;
      if (!fa[i])fa[i]=1;
    }
    T.pb(w);tmin(w);
    ans+=(now+T.stk[1].x);
    print(ans);
  }return 0;
}