查最大前驱，也就是小于等于它的最小的值。
跟分块入门2的做法相似。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 1e5 + 7; int N, Q, len, s; struct node { ll val; int id; node(ll a=0, int b=0) : val(a), id(b) {} friend bool operator < (node e1, node e2) { return e1.val < e2.val; } }a[maxN]; struct K { int l, r; ll lazy; K() { l = r = lazy = 0; } }t[325]; inline void update(int ql, int qr, ll w) { int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; } sort(a + t[st].l, a + t[st].r + 1); return; } for(int i=t[st].l; i<=t[st].r; i++) if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; sort(a + t[st].l, a + t[st].r + 1); for(int i=t[ed].l; i<=t[ed].r; i++) if(a[i].id >= ql && a[i].id <= qr) a[i].val += w; sort(a + t[ed].l, a + t[ed].r + 1); for(int i=st + 1; i <= ed - 1; i++) t[i].lazy += w; } inline ll query(int ql, int qr, ll w) { ll ans = -1, tmp; int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { tmp = w - t[st].lazy; for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans = a[i].val + t[st].lazy; } return ans; } tmp = w - t[st].lazy; for(int i=t[st].l; i<=t[st].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans = a[i].val + t[st].lazy; } tmp = w - t[ed].lazy; for(int i=t[ed].l; i<=t[ed].r; i++) { if(a[i].val >= tmp) break; if(a[i].id >= ql && a[i].id <= qr) ans = max(ans, a[i].val + t[ed].lazy); } node now = node(); int id; for(int i = st + 1; i <= ed - 1; i++) { tmp = w - t[i].lazy; now = node(tmp, 0); id = (int)(lower_bound(a + t[i].l, a + t[i].r + 1, now) - a - t[i].l); if(id) ans = max(ans, a[id + t[i].l - 1].val + t[i].lazy); } return ans; } int main() { scanf("%d", &N); Q = N; len = sqrt(N); s = N / len + (N % len == 0 ? 0 : 1); for(int i=1; i<=s; i++) { t[i].l = (i - 1) * len + 1; t[i].r = i * len; } t[s].r = N; for(int i=1; i<=N; i++) { scanf("%lld", &a[i].val); a[i].id = i; } for(int i=1; i<=s; i++) sort(a + t[i].l, a + t[i].r + 1); int op, l, r; ll c; while(Q--) { scanf("%d%d%d%lld", &op, &l, &r, &c); if(op) //query { printf("%lld\n", query(l, r, c)); } else //update { update(l, r, c); } } return 0; }
