BOJ 16027: Global warming

Link

• https://www.acmicpc.net/problem/16027

• CEOI 2018 2번

Tag

• dp

• Segment Tree

Time Complexity

• $O(NlgN)$

 수열과 정수 X가 주어진다. 수열의 연속된 구간의 수에 -X ~ X 만큼 더하는 연산을 단 한번 해서, 이 수열의 LIS 길이를 최대화해야한다.

 구간 [l. r]에 k를 빼는게 최적이라고 하자. 그럼 구간 [1, r]에 k를 빼도 결과는 같다. 그럼 구간 [r+1, N]에 k를 더해도 결과는 같다. k가 아니라 X를 더해도 결과는 같다. 따라서 모든 i에 대해 구간 [i,N]에 X만큼 더하면서 최대를 찾으면 된다.

 dp1[i]: i번째 수를 마지막으로 하는 최대 LIS 길이. dp2[i]: i번째 수를 시작으로 하는 최대 LIS 길이로 정의해서 잘 구한 다음, 세그먼트 트리를 잘 써서 답을 찾아주면 된다.

Code

 

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef pair<ll,ll> pll;
	typedef pair<int,int> pii;
	#define fi first
	#define se second
	#define endl '\n'
	#define y1 holyshit
	#define all(x) x.begin(),x.end()
	const int inf=0x3f3f3f3f;
	int N,X,d[200010],d2[200010],dp[200010],len1[200010],len2[200010];
	vector<int> comp;
	int base=1<<19,tree[1<<20];
	void update(int p,int v){
	for(p+=base;p;p>>=1) tree[p]=max(tree[p],v);
	}
	int query(int l,int r){
	l+=base; r+=base;
	int ret=0;
	while(l<=r){
	if(l&1) ret=max(ret,tree[l]);
	if(~r&1) ret=max(ret,tree[r]);
	l=(l+1)>>1; r=(r-1)>>1;
	}
	return ret;
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>X;
	for(int i=0;i<N;i++){
	cin>>d[i];
	d2[i]=d[i]+X;
	comp.push_back(d[i]);
	comp.push_back(d2[i]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	for(int i=0;i<N;i++){
	d[i]=lower_bound(all(comp),d[i])-comp.begin();
	d2[i]=lower_bound(all(comp),d2[i])-comp.begin();
	}
	memset(dp,inf,sizeof(dp));
	dp[0]=INT_MIN;
	for(int i=0;i<N;i++){
	int x=lower_bound(dp,dp+N,d[i])-dp;
	len1[i]=x;
	dp[x]=min(dp[x],d[i]);
	}
	reverse(d2,d2+N);
	memset(dp,inf,sizeof(dp));
	dp[0]=INT_MIN;
	for(int i=0;i<N;i++){
	int x=lower_bound(dp,dp+N,-d2[i])-dp;
	len2[i]=x;
	dp[x]=min(dp[x],-d2[i]);
	}
	reverse(len2,len2+N);
	reverse(d2,d2+N);
	int ans=len1[N-1];
	update(d2[N-1],len2[N-1]);
	for(int i=N-2;i>=0;i--){
	ans=max(ans,len1[i]+query(d[i]+1,500000));
	update(d2[i],len2[i]);
	}
	cout<<ans;
	return 0;
	}

view raw 16027.cpp hosted with ❤ by GitHub