标签：yam   include   tac   getchar   printf   tin   space   ||   mis   

CF802I Fake News (hard)

这个题和 CF123D 很像，代码只有一点点不同。

首先看到子串的问题容易想到后缀数组，所以我们可以先对字符串求一遍后缀数组以及 height 数组。

接下来怎么做？我们其实可以想得到单调栈。我们可以考虑对于 height 数组维护一个单调递增的栈。一旦我们要弹出栈顶元素时，我们就知道他一定会对答案做出新贡献，即 \(cnt(s,p)>1\)。我们只需要把这些有新贡献的串的个数算出来，然后把其他只出现过一次的串的数量统计出来，答案就算出来了。

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

//Don‘t act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you‘ll be punished by Sakyamuni!!!
#include
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch‘9‘) {
		if(ch==‘-‘)
			f=-1;
		ch=getchar();
	}
	while(ch>=‘0‘&&ch stk;
	for(int i=2;iheight[i]) {
			int y=height[stk.top()];
			int x=height[i];
			stk.pop();
			int z=(stk.empty()? 0:height[stk.top()]);
			int len=i-(stk.empty()? 1:stk.top());
			ans+=(y-max(x,z))*(len*len-len);
		}
		stk.push(i);
	}
	return ans;
}

signed main() {
	int t=read();
	
	while(t--) {
		scanf("%s",s+1);
		n=strlen(s+1);
		
		get_sa();
		get_height();
		
		printf("%lld\n",solve());
	} 
	return 0;
}

对于单调栈的思考，我有一个小技巧，可以通过画柱形图来帮助思考，这样会很直观

CF802I Fake News (hard) （后缀数组+单调栈）

标签：yam   include   tac   getchar   printf   tin   space   ||   mis   

原文地址：https://www.cnblogs.com/huayucaiji/p/CF802I.html