题目链接：#6279. 数列分块入门 3
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int blo, n, opt, l, r, c, a[maxn], pos[maxn], atag[maxn];
set<int>st[maxn];
int add(int l, int r, int c)
{for (int i = l ; i <= min(pos[l]*blo, r); i++){st[pos[l]].erase(a[i]);a[i] += c;st[pos[l]].insert(a[i]);}if(pos[l] != pos[r]){for (int i = (pos[r]-1)*blo+1; i <= r; i++){st[pos[r]].erase(a[i]);a[i] += c;st[pos[r]].insert(a[i]);}}for (int i = pos[l]+1; i <= pos[r]-1; i++) atag[i] += c;
}
int query(int l , int r, int c)
{int ans = -1;for (int i = l ; i <= min(pos[l]*blo, r); i++){int val = a[i] + atag[pos[l]];if(val < c) ans = max(ans, val);}if(pos[l] != pos[r])for(int i = (pos[r]-1)*blo+1; i <= r; i++){int val = a[i] + atag[pos[r]];if(val < c) ans = max(ans, val);}for (int i = pos[l] + 1; i <= pos[r]-1; i++) {int x = c - atag[i];set<int>::iterator it = st[i].lower_bound(x);if(it == st[i].begin()) continue;--it;ans = max(ans, *it+atag[i]);}return ans;
}
int main()
{scanf("%d", &n);blo = sqrt(n);for (int i = 1; i <= n; i++) scanf("%d",&a[i]), pos[i] = (i - 1) / blo + 1, st[pos[i]].insert(a[i]);for (int i = 0; i < n; i++){scanf("%d%d%d%d", &opt, &l, &r, &c);if(opt == 0){add(l, r, c);}else{printf("%d\n", query(l, r, c));}}return 0;
}