今天决定把分块三写掉, 结果 。。。没了 求助!
#include<stdio.h>
#include<math.h>
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
const int N = 1e5, M = 500, inf = 0x7fffffff;
using namespace std;
int n, bl[N + 5], L, v[N + 5], sum[N + 5];
vector<int > a[M + 5];
void read(int &x) {
x = 0;char c = getchar();int w = 1;
for(;c < '0' || c > '9'; c = getchar())
if (c == '-') w = -1;
for(; c <= '9' && c >= '0'; c = getchar())
x = x * 10 + c - '0';
x *= w;
}
int max(int x, int y) {return x > y ? x : y;}
int min(int x, int y) {return x < y ? x : y ;}
void Reset(int x) {
a[x].clear();
for(int i = (x - 1) * L + 1; i <= min(n, x * L); ++i)
a[x].push_back(v[i] + sum[x]);
sort(a[x].begin(), a[x].end());
}
void add(int l, int r, int c) {
if (bl[l] == bl[r]) {
for(int i = l; i <= r; ++i)
v[i] += c;
Reset(bl[l]);
}
for(int i = l; i <= bl[l] * L; ++i)
v[i] += c;
Reset(bl[l]);
for(int i = bl[l] + 1; i < bl[r]; ++i)
sum[i] += c;
for(int i = (bl[r] - 1) * L + 1; i <= r; ++i)
v[i] += c;
Reset(bl[r]);
}
int query(int l, int r, int c) {
int ans = -inf;
for(int i = l; i <= bl[l] * L; ++i)
if (v[i] + sum[bl[l]] <= c)
ans = max(ans, v[i] + sum[bl[l]]);
for(int i = bl[l] + 1; i < bl[r]; ++i) {
int k = upper_bound(a[i].begin(), a[i].end(), c - sum[i]) - a[i].begin();--k;
if (a[i][k] + sum[i] <= c)
ans = max(ans, a[i][k] + sum[i]);
}
for(int i = (bl[r] - 1) * L + 1; i <= r; ++i)
if (v[i] + sum[bl[l]] <= c)
ans = max(ans, v[i] + sum[bl[l]]);
return ans == -inf ? -1 : ans;
}
int main() {
read(n);
L = sqrt(n * 1.0) + .5;
for(int i = 1; i <= n; ++i) {
read(v[i]);
bl[i] = (i - 1) / L + 1;
a[bl[i]].push_back(v[i]);
}
for(int i = 1; i <= bl[n]; ++i)
sort(a[i].begin(), a[i].end());
for(int Q = 1; Q <= n; ++Q) {
int opt, l, r, c;
read(opt);read(l);read(r);read(c);
if (opt == 0) add(l, r, c);
else printf("%d\n", query(l, r, c));
}
return 0;
}