题解：P12448

#include <bits/stdc++.h>
using namespace std;
#define int long long
int rd(){
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	int ret = 0;
	while('0' <= c && c <= '9') ret = (ret << 3) + (ret << 1) + c - '0', c = getchar();
	return ret;
}

int n, m, ID;
long long a[500002];

struct Segment_Tree{
	#define l(pos) pos << 1
	#define r(pos) (pos << 1) | 1
	struct Node {
		int num;
		int tagl, tags;
		bool havetag;
	}t[4000002];
	void pushdown(int pos,int l,int r){
		int mid = (l + r) >> 1;
		if(t[pos].havetag){
			t[pos].num += (2*t[pos].tagl + (r-l)*t[pos].tags) * (r-l+1) / 2;
			t[l(pos)].havetag = 1, t[l(pos)].tagl += t[pos].tagl, t[l(pos)].tags += t[pos].tags;
			t[r(pos)].havetag = 1, t[r(pos)].tagl += t[pos].tagl + (mid+1-l)*t[pos].tags, t[r(pos)].tags += t[pos].tags;
			t[pos].tagl = 0, t[pos].tags = 0, t[pos].havetag = 0;
		}
	}
	void Add(int pos,int l,int r,int tarl,int tarr,int x,int y){
		if(tarl > tarr) return;
		pushdown(pos, l, r);
		if(tarl <= l && r <= tarr){
			t[pos].havetag = 1;
			t[pos].tagl = x, t[pos].tags = y;
			pushdown(pos, l, r);
			return;
		}
		int mid = (l + r) >> 1;
		if(tarl <= mid) Add(l(pos), l, mid, tarl, tarr, x, y);
		if(mid+1 <= tarr) {
			if(tarl <= mid+1) Add(r(pos), mid+1, r, mid+1, tarr, x+(mid+1-tarl)*y, y);
			else Add(r(pos), mid+1, r, tarl, tarr, x, y);
		}
		pushdown(l(pos), l, mid), pushdown(r(pos), mid+1, r);
		t[pos].num = t[l(pos)].num + t[r(pos)].num;
	}
	int Query(int pos,int l,int r,int tarl,int tarr){
		pushdown(pos, l, r);
		if(tarl <= l && r <= tarr) return t[pos].num;
		int mid = (l + r) >> 1, ret = 0;
		if(tarl <= mid) ret += Query(l(pos), l, mid, tarl, tarr);
		if(mid+1 <= tarr) ret += Query(r(pos), mid+1, r, tarl, tarr);
		return ret;
	}
};
Segment_Tree T;
struct Line_Tree{
	#define l(pos) pos << 1
	#define r(pos) (pos << 1) | 1
	int Max[4000002];
	void Add(int pos,int l,int r,int tar,int s){
		if(l == r) {
			Max[pos] += s;
			return;
		}
		int mid = (l + r) >> 1;
		if(tar <= mid) Add(l(pos), l, mid, tar, s);
		else Add(r(pos), mid+1, r, tar, s);
		Max[pos] = max(Max[l(pos)], Max[r(pos)]);
	}
	int Finderl(int pos,int l,int r,int tar,int tars){
		if(l == r){
			if(Max[pos] < tars) return -1;
			return l;
		}
		int mid = (l + r) >> 1;
		if(tar <= mid) return Finderl(l(pos), l, mid, tar, tars);
		if(mid < tar && tar < r){
			int R = Finderl(r(pos), mid+1, r, tar, tars);
			if(R != -1) return R;
			return Finderl(l(pos), l, mid, tar, tars);
		}
		if(Max[r(pos)] >= tars) return Finderl(r(pos), mid+1, r, tar, tars);
		return Finderl(l(pos), l, mid, tar, tars);
	}
	int Finderr(int pos,int l,int r,int tar,int tars){
		if(l == r){
			if(Max[pos] < tars) return -1;
			return l;
		}
		int mid = (l + r) >> 1;
		if(tar >= mid+1) return Finderr(r(pos), mid+1, r, tar, tars);
		if(l < tar && tar < mid+1){
			int R = Finderr(l(pos), l, mid, tar, tars);
			if(R != -1) return R;
			return Finderr(r(pos), mid+1, r, tar, tars);
		}
		if(Max[l(pos)] >= tars) return Finderr(l(pos), l, mid, tar, tars);
		return Finderr(r(pos), mid+1, r, tar, tars);
	}
};
Line_Tree L;

signed main(){
	//freopen("data.in","r",stdin);
	//freopen("my.out","w",stdout);
	
	n = rd(), m = rd(), ID = rd();
	L.Add(1, -1, n+2, 0, 1e18);
	L.Add(1, -1, n+2, n+1, 1e18);
	L.Add(1, -1, n+2, -1, 1e18);
	L.Add(1, -1, n+2, n+2, 1e18);
	for(int i=1;i<=n;i++) {
		a[i] = rd();
		L.Add(1, -1, n+2, i, a[i]);
	}
	
	for(int i=1;i<=n;i++){
		int l = L.Finderl(1, -1, n+2, i-1, a[i]+1) + 1, r = L.Finderr(1, -1, n+2, i+1, a[i]) - 1;
		
		int s = min(r - i + 1, i - l + 1);
		T.Add(1, 1, n, 1, s-1, a[i], a[i]);
		T.Add(1, 1, n, s, r-l+1-s, s*a[i], 0);
		T.Add(1, 1, n, r-l+2-s, r-l+1, s*a[i], -a[i]);
	}
	
	for(int i=1;i<=m;i++){
		int opt;
		int x;
		opt = rd(), x = rd();
		if(opt == 1){
			printf("%lld\n",T.Query(1, 1, n, x, x));
		}
		else {
			a[x]++;
			int l = L.Finderl(1, -1, n+2, x-1, a[x]) + 1, r = L.Finderr(1, -1, n+2, x+1, a[x]) - 1;
			//cout << l << ' ' << r << endl;
			
			int MIN = min(x-l+1, r-x+1), MAX = max(x-l+1, r-x+1);
			T.Add(1, 1, n, 1, MIN-1, 1, 1);
			T.Add(1, 1, n, MIN, MAX - 1, MIN, 0);
			T.Add(1, 1, n, MAX, r-l+1, MIN, -1);
			
			L.Add(1, -1, n+2, x, 1);
		}
	}
	
	return 0;
}