Pizzeriat

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
const int M = 131072;

int table[N];
int beginning[N];
int ending[N];

int treeB[2*M];
int treeE[2*M];

int n, q;


void prep() {
	for(int i = M; i < M + n; ++i) {
		treeB[i] = beginning[i - M + 1];
		treeE[i] = ending[i - M + 1];
	}

	for(int i = M + n; i < 2*M; ++i) {
		treeB[i] = 1e9;
		treeE[i] = 1e9;
	}

	for(int i = M - 1; i >= 1; --i) {
		treeB[i] = min(treeB[2*i], treeB[2*i + 1]);
		treeE[i] = min(treeE[2*i], treeE[2*i + 1]);
	}

}


void update(int i, int x) {
	i += M - 1;
	treeB[i] = beginning[i - (M-1)];
	treeE[i] = ending[i - (M-1)];
	i/=2;
	while(i > 0) {
		treeB[i] = min(treeB[2*i], treeB[2*i + 1]);
		treeE[i] = min(treeE[2*i], treeE[2*i + 1]);
		i/=2;
	}

}


pair<int, int> find(int a, int b) {
	a+= M-1; b+= M-1;
	int ansB = 1e9;
	int ansE = 1e9;
	while(a <= b) {
		if(a%2 == 1) {
			ansB = min(ansB, treeB[a]);
			ansE = min(ansE, treeE[a]);
			++a;
		}
		if(b%2 == 0) {
			ansB = min(ansB, treeB[b]);
			ansE = min(ansE, treeE[b]);
			--b;
		}
		a/=2; b/=2;
	}
	return make_pair(ansB, ansE);
	//return ansB;
}

int findIndexbeginning(int a, int b) {
	if(a == b) {
		return a;
	}
	int middle = (a+b)/2;
	if(find(a, middle).first == find(a, b).first) {
		return findIndexbeginning(a, middle);
	}
	return findIndexbeginning(middle + 1, b);
}

int findIndexending(int a, int b) {
	if(a == b) {
		return a;
	}
	int middle = (a+b)/2;
	if(find(a, middle).second == find(a, b).second) {
		return findIndexending(a, middle);
	}
	return findIndexending(middle + 1, b);
}


int main() {
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) {
		int a;
		cin >> a;
		table[i] = a;
		beginning[i] = a + n - i;
		ending[i] = a + i - 1;
	}

	prep();

	for(int i = 0; i < q; ++i) {
		int type;
		cin >> type;
		/*for(int j = 1; j <= n; ++j) {
			cout << table[j] << " ";
		}
		cout << "\n";
		for(int j = 1; j <= n; ++j) {
			cout << beginning[j] << " ";
		}
		cout << "\n";
		for(int j = 1; j <= n; ++j) {
			cout << ending[j] << " ";
		}
		cout << "\n";
		*/		
		if(type == 2) {
			int spot;
			cin >> spot;
			int ans = findIndexbeginning(1, spot);
			int second = findIndexending(spot, n);
		//	cout << ans << " " << second << " ";
			cout << min(table[ans] + spot - ans, table[second] + second - spot) << "\n";
		} else {
			int k, x;
			cin >> k >> x;
			table[k] = x;
			ending[k] = x + k - 1;
			beginning[k] = x + n - k;
			update(k, x);
		}
	}


}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED