BOJ 28020 | Attention

길이가 3인 LCS의 개수를 구하는 문제다. 이 문제는 길이가 3인 LIS를 구하는 문제로 치환할 수 있다.

그러므로 길이가 3인 LIS를 구하는 방법을 생각해보자.

길이가 3인 부분수열의 중앙값을 고정하고, [front, middle, back] 형태로 생각하자.

front는 middle보다 작고, middle 앞의 값이어야 한다.
back은 middle보다 크고, middle 뒤의 값이어야 한다.

front[i] 가 middle이 i일 때 front 값이 될 수 있는 수들의 개수라고 하면, front 배열은 스위핑을 통해 구할 수 있다. 이는 back 배열도 마찬가지다.

관련 설명은 (#5419) 에서 볼 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

class SegTree{
private:
	vector<ll> tree;
public:
	SegTree(int N){
		tree.resize(4*N);
	}
	
	void clear(){
		for (int i = 0; i < tree.size(); i++) tree[i] = 0;
	}
	
	ll init(vector<ll> &nums, ll node, int s, int e){
		if (s == e) return tree[node] = nums[s];
		return tree[node] = init(nums, node*2, s, (s+e)/2) + init(nums, node*2+1, (s+e)/2+1, e);
	}
	
	ll update(ll node, int s, int e, int idx, int add){
		if (idx < s || e < idx) return tree[node];
		if (s == e) return tree[node] += add;
		
		return tree[node] = update(node*2,s,(s+e)/2,idx,add)+update(node*2+1,(s+e)/2+1,e,idx,add);
	}
	
	ll query(ll node, int s, int e, int l, int r){
		if (e < l || r < s) return 0;
		if (l <= s && e <= r) return tree[node];
		
		return query(node*2,s,(s+e)/2,l,r) + query(node*2+1,(s+e)/2+1,e,l,r);
	}
};

int main(){
	FASTIO;
	int N; cin >> N;
	SegTree SG(N);
	vector<int> a, b;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		a.push_back(t);
	}
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		b.push_back(t);
	}
	
	vector<int> aidx(N);
	for (int i = 0; i < N; i++){
		aidx[a[i]] = i;
	}
	vector<int> lis(N);
	for (int i = 0; i < N; i++){
		lis[i] = aidx[b[i]]+1;
	}
	
	vector<int> smaller(N);
	vector<int> larger(N);
	for (int i = 0; i < N; i++){
		smaller[i] = SG.query(1, 1, N, 1, lis[i]-1);
		SG.update(1, 1, N, lis[i], 1);
	}
	SG.clear();
	
	for (int i = N-1; i >= 0; i--){
		larger[i] = SG.query(1, 1, N, lis[i]+1, N);
		SG.update(1, 1, N, lis[i], 1);
		
		//debug << lis[i] << ' ' << larger[i] << endl;
	}
	
	ll sum = 0;
	for (int i = 0; i < N; i++){
		sum += smaller[i] * larger[i];
	}
	
	if (sum == 0) cout << "Attention is what I want";
	else cout << "My heart has gone to paradise\n" << sum;
	
}