#13536 괄호 부분 문자열 쿼리 , #24915 센터가 돋보여야 해

13536을 풀며 머리를 탁 치고 짠 후 24915를 풀었다.

 

 

문제 풀이에 비하인드가 있는데, 24915는 한 이틀정도 고민한 문제였다.

고민했는데 모르겠어서 풀이를 찾아보려 해도 최근 문제라서 풀이가 없다;;;

 

그래서 포기했었다.

 

오늘 학회 채점현황에서 20052 가 풀렸는데, 나는 아직 안 풀려 있길래 풀었다.

그래서 세트로 13536을 풀어보려 갔는데, 이것도 안풀림;;

 

한 1시간 정도 고민하다가 설마 금광 세그? 라는 생각으로 들어갔는데 바로바로 풀려버린다.

 

13536은 struct로 3개를 관리해주면 된다.

이건 설명이 어려워서 생략하고 24915 중심으로 설명을 해보자면,

어떤 구간 [l , r]을 나타내는 노드에 대해서 

1. l<=a<b<=r인 index에 대해 A[b]-A[a]의 최댓값

2. l<=c<d<=r인 index에 대해 A[c]-A[d]의 최댓값

3. [l , r] 구간의 최솟값

4. [l , r] 구간의 최댓값

5. 구간에서의 a<b<c 인 A[b]-A[a]-A[c]의 최댓값

이렇게 5개를 관리할 것이다.

 

그렇다면 두 노드 A와 B를 합칠 때,

1번은 max(A.1 , B.1 , B.4-A.3)

2번은 max(A.2 , B.2 , A.4-B.3) 

3번은 max(A.3 , B.3)

4번은 max(A.4 , B.4)

 

5번은 독자에게 맡긴다.

 

그리고 금광 세그 바텀업으로 짜면서 옜날에는 개고생해서 짰는데, 지금은 더 쉬운 구현을 깨달아버렸다.

바로 merge하는 함수를 그냥 하나 만들고, 쿼리 날릴때 순서를 적당히 조정해주면, 훨씬 깨끗해진다.

24915 코드를 올리고 마무리 한다.

 

#include<bits/stdc++.h>
//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 4e5 + 100, inf = (ll)1e9*(ll)1e9 + 7, mod = 1e9 + 7, sqrtN = 320;

ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
struct node {
	ll l, r, val, max_, min_;
	//max_ 원소,min_ 원소
};
ll A[n_];
node tree[n_ * 4];
node merge(node x, node y) {
	//node x와 node y를 merge
	node ret;
	ret.l = max(x.l, y.l);
	ret.r = max(x.r, y.r);
	ret.max_ = max(x.max_, y.max_);
	ret.min_ = min(x.min_, y.min_);
	ret.val = max(x.val, y.val);
	
	ret.val = max(ret.val, -x.min_ + y.r);
	ret.val = max(ret.val, x.l - y.min_);
	ret.r = max(ret.r, x.max_ - y.min_);
	ret.l = max(ret.l, y.max_ - x.min_);
	return ret;
}
ll f(ll l, ll r) {
	l += base, r += base;
	vector<node>A, B;
	while (l <= r) {
		if (l % 2)A.push_back(tree[l++]);
		if (!(r % 2))B.push_back(tree[r--]);
		l /= 2, r /= 2;
	}
	reverse(all(B));
	for (auto nxt : B)A.push_back(nxt);
	node now = A[0];
	for (int i = 1; i < A.size(); i++)now = merge(now, A[i]);
	return now.val;
}
void update(ll idx, ll val) {
	idx += base;
	node t = { -inf,-inf,-inf,val,val };
	tree[idx] = t;
	idx /= 2;
	while (idx) {
		tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
		idx /= 2;
	}
}
void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> A[i];
	for (base = 1; base < n; base *= 2);
	for (int i = 0; i < n; i++) {
		node t = { -inf,-inf,-inf,A[i],A[i] };
		tree[base + i] = t;
	}
	for (int i = base - 1; i; i--)tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
	while (m--) {
		cin >> a >> b >> c;
		if (a == 1)update(b - 1, c);
		else cout << f(b - 1, c - 1) << '\n';
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}