P4248 [AHOI2013]差异(后缀数组+单调栈)

题意：

给定一个长度为(n)的字符串(S),令(T_i)表示它从第(i)个字符开始的后缀。求

[sum_{1≤i＜j≤n}len(T_i)+len(T_j)-2×lcp(T_i,T_j) ]

其中,len(a)表示字符串(a)的长度,lcp(a,b)表示字符串(a)和字符串(b)的最长公共前缀。

分析：

看成两部分的贡献，前面的(len(T_i)+len(T_j))可以(O(n))时间内处理出。

后面部分本质是计算height所有区间最小值的和，可以利用一个单调递增的栈模拟，每次维护矩形的高度，贡献为矩形的面积。

struct node{int x, y;};
stack<node> st;

void run() {
  scanf("%s",s);
  int n = strlen(s);
  for (int i = 0; i < n; i++) r[i] = s[i];
  dc3(r,sa,n+1,300);
  calheight(r,sa,n);
  int s = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    if (st.empty()) {
      st.push({1,height[i]});
      s += height[i];
      ans += s;
    } else {
      int tmp = 1;
      while (!st.empty()&& st.top().y > height[i]) tmp += st.top().x,s -= st.top().x * st.top().y, st.pop();
      st.push({tmp,height[i]});
      s += tmp*height[i];
      ans += s;
    }
  }
  int res = 0;
  for (int i = n; i >= 2; i--) res += i*(i-1);
  for (int j = n-1; j >= 1; j--) res += j*(n-j); 
  cout << res - 2*ans << '
';
}