BOJ 25081 Cocktail Party

문제 링크입니다.

문제 요약

길이 $N$의 문자열이 주어집니다. 두 문자 $p$와 $q$에서 각각 시작하는 길이 $l$의 부분 문자열이 서로 같다면 두 문자를 $l$-닮음이라 합니다. 각 문자에는 정수 가중치 $w$가 할당되어 있습니다. $w$는 음수일 수 있습니다.

$0$ 이상 $N$ 미만의 모든 $l$에 대해, $l$-닮음인 두 문자의 최대 가중치 곱을 구하세요.

풀이

두 문자가 닮음이 되는 최대 $l$은 LCP 배열 상에서의 구간 최솟값으로 구할 수 있습니다. $l$이 감소함에 따라 함께 고를 수 있는 문자들의 집합이 합쳐지기만 하기 때문에, $l$이 클 때부터 역으로 처리하면서 Union-Find로 큰 $l$부터 합쳐주면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

struct Node{
	int nxt[27];
	int slink;
	int len; int rpos;
	Node(int a, int b, int c) : slink(a), len(b), rpos(c){for(int i = 0; i < 27; i++) nxt[i] = -1;}
};

struct SuffixAutomata{
	vector<Node> v;
	vector<array<int, 27>> e;
	vector<int> SA, LCP;
	vector<int> s;
	int tot, last_depth = 0;
	SuffixAutomata(){
		v.push_back(Node(-1, 0, -1));
		tot = 0;
	}
	void add(int c, int idx){
		int now = tot;
		v.push_back(Node(0, v[tot].len+1, idx));
		tot = v.size()-1;
		while(now >= 0 && v[now].nxt[c] == -1){
			v[now].nxt[c] = tot;
			now = v[now].slink;
		}
		if(now < 0) return;
		int prv = v[now].nxt[c];
		if(v[now].len+1 == v[prv].len){
			v[tot].slink = prv; return;
		}
		int upd = v.size();
		v.push_back(Node(v[prv].slink, v[now].len+1, idx));
		v[prv].slink = upd; for(int i = 0; i < 27; i++) v[upd].nxt[i] = v[prv].nxt[i];
		for(int j = now; j >= 0 && v[j].nxt[c] == prv; j = v[j].slink) v[j].nxt[c] = upd;
		v[tot].slink = upd;
	}
	void get_tree(){
		e.resize(v.size());
		for(auto& i : e) i.fill(-1);
		for(int i = 1; i < v.size(); i++) e[v[i].slink][s[v[i].rpos-v[v[i].slink].len]] = i;
	}
	void get_array(int now = 0, int depth = 0){
		bool isLeaf = true;
		for(int i = 0; i < 27; i++){
			if(e[now][i] >= 0){
				isLeaf = false;
				get_array(e[now][i], v[e[now][i]].len);
				if(last_depth > depth) last_depth = depth;
			}
		}
		if(isLeaf){
			SA.push_back(s.size()-depth+1);
			LCP.push_back(min(last_depth, depth));
			last_depth = depth;
		}
	}
	void solve(string S){
		reverse(S.begin(), S.end()); s.push_back(0);
		for(auto& c : S) s.push_back(c-'a'+1);
		for(int i = 0; i < s.size(); i++) add(s[i], i);
		get_tree();
		get_array();
	}
} sfx;

array<int, 7> a[303030], na[303030];
ll ans, mx = -LONG_LONG_MAX;
int par[303030];
vector<int> e[303030];

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	ans -= (ll)par[x]*(par[x]-1)/2;
	ans -= (ll)par[y]*(par[y]-1)/2;
	par[x] += par[y]; par[y] = x;
	ans += (ll)par[x]*(par[x]-1)/2;
	
	if(a[x][1] > a[y][1]) a[x][2] = max(a[y][1], a[x][2]);
	else a[x][2] = max(a[y][2], a[x][1]), a[x][1] = a[y][1];
	a[x][3] = min(a[x][3], a[y][3]);
	if(a[x][4] < a[y][4]) a[x][5] = min(a[y][4], a[x][5]);
	else a[x][5] = min(a[y][5], a[x][4]), a[x][4] = a[y][4];
	a[x][6] = max(a[x][6], a[y][6]);
	if(a[x][2] >= 0) mx = max(mx, (ll)a[x][1]*a[x][2]);
	if(a[x][5] <= 0) mx = max(mx, (ll)a[x][4]*a[x][5]);
	mx = max(mx, (ll)a[x][3]*a[x][6]);
}

vector<pll> ret;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	int n; string s; cin >> n >> s; sfx.solve(s);
	for(int i = 1; i <= n; i++){
		cin >> a[i][0];
		a[i][1] = a[i][2] = -1; a[i][3] = 1234567890;
		a[i][4] = a[i][5] = 1; a[i][6] = -1234567890;
		if(a[i][0] >= 0) a[i][1] = a[i][3] = a[i][0];
		if(a[i][0] <= 0) a[i][4] = a[i][6] = a[i][0];
	}
	for(int i = 1; i <= n; i++) na[i] = a[sfx.SA[i]]; swap(a, na);
	for(int i = 2; i <= n; i++) e[sfx.LCP[i]].push_back(i);
	for(int i = n-1; i >= 0; i--){
		for(auto& t : e[i]) u(t-1, t);
		if(!ans) ret.emplace_back(0, 0);
		else ret.emplace_back(ans, mx);
	}
	for(int i = n-1; i >= 0; i--) cout << ret[i].first << ' ' << ret[i].second << '\n';
}