Water Problem
#include <bits/stdc++.h>
const int maxn = 1e5 + 7;
using namespace std;
int n, m, a[maxn], l, r;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 2; i <= n; ++i) a[i] += a[i-1];
for(int i = 1; i <= m; ++i) {
scanf("%d%d",&l,&r);
printf("%d
", a[r]-a[l-1]);
}
}
单点修改
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int n, m, x, y, opt;
struct seg{int l, r, sum;} tree[maxn<<2];
void build(int p, int l, int r) {
tree[p].l = l; tree[p].r = r; tree[p].sum = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
}
void add(int p, int x, int y) {
if(tree[p].l == tree[p].r) {
tree[p].sum += y; return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if(x<=mid) add(p<<1, x, y);
else add(p<<1|1, x, y);
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
int ask(int p, int l, int r) {
if(l == tree[p].l && tree[p].r == r) return tree[p].sum;
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask(p<<1, l, r);
else if(l > mid) return ask(p<<1|1, l, r);
else return ask(p<<1, l, mid) + ask(p<<1|1, mid+1, r);
}
int main() {
scanf("%d %d", &n, &m);
build(1, 1, n);
for(int i = 1; i <= n; ++i) scanf("%d",&x), add(1,i,x);
for(int i = 1; i <= m; ++i) {
scanf("%d %d %d", &opt, &x, &y);
if(opt) add(1, x, y);
else printf("%d
", ask(1, x, y));
}
}
区间修改
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 7;
using namespace std;
int n, m, opt, l, r;
ll a[maxn], x;
struct seg{int l,r; ll sum,mx,tag;} tree[maxn<<2];
void push_up(int p) {
tree[p].mx = max(tree[p<<1].mx, tree[p<<1|1].mx);
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void push_down(int p) {
if(tree[p].tag) {
tree[p<<1].sum += 1LL*(tree[p<<1].r - tree[p<<1].l + 1)*tree[p].tag;
tree[p<<1|1].sum += 1LL*(tree[p<<1|1].r - tree[p<<1|1].l + 1)*tree[p].tag;
tree[p<<1].mx += tree[p].tag;
tree[p<<1|1].mx += tree[p].tag;
tree[p<<1].tag += tree[p].tag;
tree[p<<1|1].tag += tree[p].tag;
tree[p].tag = 0;
}
}
void build(int p, int l, int r) {
tree[p].l = l; tree[p].r = r;
tree[p].sum = tree[p].tag = tree[p].mx = 0;
if(l == r) {
tree[p].mx = tree[p].sum = a[l]; return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
push_up(p);
}
void add(int p, int l, int r, ll x) {
if(tree[p].l == l && tree[p].r ==r) {
tree[p].sum += 1LL*(r-l+1)*x;
tree[p].mx += x;
tree[p].tag += x;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
push_down(p);
if(r <= mid) add(p<<1, l, r, x);
else if(l > mid) add(p<<1|1, l, r, x);
else add(p<<1, l, mid, x), add(p<<1|1, mid+1, r, x);
push_up(p);
}
ll ask_mx(int p, int l, int r) {
if(l == tree[p].l && tree[p].r == r) return tree[p].mx;
push_down(p);
ll ans = 0;
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) ans = ask_mx(p<<1, l, r);
else if(l > mid) ans = ask_mx(p<<1|1, l, r);
else ans = max(ask_mx(p<<1, l, mid), ask_mx(p<<1|1, mid+1, r));
push_up(p);
return ans;
}
ll ask_sum(int p, int l, int r) {
if(tree[p].l == l && tree[p].r == r) return tree[p].sum;
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask_sum(p<<1, l, r);
else if(l > mid) return ask_sum(p<<1|1, l, r);
else return ask_sum(p<<1, l, mid) + ask_sum(p<<1|1, mid+1, r);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
build(1, 1, n);
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &opt, &l, &r);
if(opt == 1) {//max
printf("%lld
", ask_mx(1, l, r));
}
else if(opt == 2) {//sum
printf("%lld
", ask_sum(1, l, r));
}
else {// add
scanf("%lld", &x);
add(1, l, r, x);
}
}
}
差分
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 5e7 + 7;
using namespace std;
int n, m, l, r;
ll a[maxn], x;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for(int i = n; i >= 2; --i) a[i] -= a[i-1];
for(int i = 1; i <= m; ++i) {
scanf("%d%d%lld", &l, &r, &x);
a[l]+=x, a[r+1]-=x;
}
for(int i = 2; i <= n; ++i) a[i] += a[i-1];
for(int i = 1; i <= n; ++i) printf("%lld ",a[i]);puts("");
}
BZOJ1798区间加乘
#include <bits/stdc++.h>
typedef unsigned long long ll;
const int maxn = 1e5 + 7;
using namespace std;
int n, m, opt, l, r;
ll a[maxn], x, P;
struct seg{int l,r; ll sum,taga,tagm;} tree[maxn<<2];
void push_up(int p) {
tree[p].sum = (tree[p<<1].sum%P + tree[p<<1|1].sum%P)%P;
}
void push_down(int p) {
tree[p<<1].tagm = ((tree[p<<1].tagm%P) * tree[p].tagm%P)%P;
tree[p<<1].taga = ((tree[p<<1].taga%P) * tree[p].tagm%P)%P;
tree[p<<1].taga = (tree[p<<1].taga%P + tree[p].taga%P)%P;
tree[p<<1].sum = (((tree[p<<1].sum%P)*tree[p].tagm%P)%P + (tree[p].taga%P*(tree[p<<1].r-tree[p<<1].l+1LL))%P)%P;
tree[p<<1|1].tagm = ((tree[p<<1|1].tagm%P) * tree[p].tagm%P)%P;
tree[p<<1|1].taga = ((tree[p<<1|1].taga%P) * tree[p].tagm%P)%P;
tree[p<<1|1].taga = (tree[p<<1|1].taga%P + tree[p].taga%P)%P;
tree[p<<1|1].sum = (((tree[p<<1|1].sum%P)*tree[p].tagm%P)%P + (tree[p].taga%P*(tree[p<<1|1].r-tree[p<<1|1].l+1LL)%P)%P)%P;
tree[p].taga = 0, tree[p].tagm = 1;
}
void build(int p, int l, int r) {
tree[p].l = l; tree[p].r = r;
tree[p].sum = tree[p].taga = 0; tree[p].tagm = 1;
if(l == r) {
tree[p].sum = a[l]; return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
push_up(p);
}
void add(int p, int l, int r, ll x) {
if(tree[p].l == l && tree[p].r ==r) {
tree[p].taga = (tree[p].taga + x%P)%P;
tree[p].sum = (tree[p].sum + ((x%P)*(r-l+1LL))%P)%P;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
push_down(p);
if(r <= mid) add(p<<1, l, r, x);
else if(l > mid) add(p<<1|1, l, r, x);
else add(p<<1, l, mid, x), add(p<<1|1, mid+1, r, x);
push_up(p);
}
void mul(int p, int l, int r, ll x) {
if(tree[p].l == l && tree[p].r ==r) {
tree[p].taga = ((tree[p].taga%P)*x%P)%P;
tree[p].tagm = ((tree[p].tagm%P)*x%P)%P;
tree[p].sum = ((tree[p].sum%P)*x%P)%P;
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
push_down(p);
if(r <= mid) mul(p<<1, l, r, x);
else if(l > mid) mul(p<<1|1, l, r, x);
else mul(p<<1, l, mid, x), mul(p<<1|1, mid+1, r, x);
push_up(p);
}
ll ask(int p, int l, int r) {
if(tree[p].l == l && tree[p].r == r) return tree[p].sum%P;
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask(p<<1, l, r)%P;
else if(l > mid) return ask(p<<1|1, l, r)%P;
else return ((ask(p<<1, l, mid)%P + ask(p<<1|1, mid+1, r))%P)%P;
}
int main() {
scanf("%d%lld", &n, &P);
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
build(1, 1, n);
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &opt, &l, &r);
if(opt == 1) {
scanf("%lld", &x);
mul(1, l, r, x);
}
else if(opt == 2) {
scanf("%lld", &x);
add(1, l, r, x);
}
else if(opt == 3)
printf("%lld
", ask(1, l, r));
}
}
//10 1000000000
//1 1 1 1 1
//1 1 1 1 1
//20
//2 5 10 478
//1 3 5 705
//3 2 8
//340543
HDU4027
#include <cstdio>
#include <cmath>
#include <algorithm>
typedef unsigned long long ll;
const int maxn = 1e6 + 7;
using namespace std;
int K, n, m, opt, l, r;
ll a[maxn], s[maxn];
struct seg{int l,r; ll sum;} tree[maxn<<2];
void push_up(int p) {
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void build(int p, int l, int r) {
tree[p].l = l; tree[p].r = r;
if(l == r) {
tree[p].sum = a[l]; return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
push_up(p);
}
ll ask(int p, int l, int r) {
if(tree[p].l == l && tree[p].r == r) return tree[p].sum;
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask(p<<1, l, r);
else if(l > mid) return ask(p<<1|1, l, r);
else return ask(p<<1, l, mid) + ask(p<<1|1, mid+1, r);
}
void sq(ll &x) {
ll t = sqrt(x);
while(t*t<=x)++t;
x = t-1;
}
void decr(int p, int l, int r) {
if(ask(1,l,r)<=(r-l+1))return;
if(tree[p].l == tree[p].r) {
sq(tree[p].sum);
return;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) decr(p<<1, l, r);
else if(l > mid) decr(p<<1|1, l, r);
else decr(p<<1,l,mid),decr(p<<1|1,mid+1,r);
push_up(p);
}
int main() {
while(scanf("%d", &n)!=EOF) {
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
build(1, 1, n);
scanf("%d", &m);
printf("Case #%d:
",++K);
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &opt, &l, &r); if(l > r) swap(l, r);
if(opt) printf("%lld
", ask(1, l, r));
else decr(1, l, r);
}
puts("");
}
return 0;
}
区间加等差数列区间求和
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 7;
using namespace std;
int n, m, opt, l, r;
ll a[maxn], x, P, a0, d;
struct seg{int l,r; ll sum,taga,tagd;} tree[maxn<<2];
void push_up(int p) {
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void push_down(int p) {
ll tn = (tree[p<<1].r - tree[p<<1].l + 1), a0 = tree[p].taga, d = tree[p].tagd;
tree[p<<1].taga += a0;
tree[p<<1].tagd += d;
tree[p<<1].sum += 1LL*(a0*tn + tn*(tn-1LL)/2LL*d);
a0 = a0 + d*tn;
tn = (tree[p<<1|1].r - tree[p<<1|1].l + 1);
tree[p<<1|1].taga += a0;
tree[p<<1|1].tagd += d;
tree[p<<1|1].sum += 1LL*(a0*tn + tn*(tn-1LL)/2LL*d);
tree[p].taga = tree[p].tagd = 0;
}
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].taga = tree[p].tagd = 0;
if(l == r) {
tree[p].sum = a[l]; return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
push_up(p);
}
void add(int p, int l, int r, ll a0, ll d) {
if(tree[p].l == l && tree[p].r == r) {
tree[p].taga += a0;
tree[p].tagd += d;
ll tn = (r - l + 1);
tree[p].sum += 1LL*(a0*tn + tn*(tn-1)/2LL*d);
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) add(p<<1, l, r, a0, d);
else if(l > mid) add(p<<1|1, l, r, a0, d);
else {
add(p<<1, l, mid, a0, d);
ll a1 = a0 + 1LL*(mid-l+1LL)*d;
add(p<<1|1, mid+1, r, a1, d);
}
push_up(p);
}
ll ask(int p, int l, int r) {
if(tree[p].l == l && tree[p].r == r){
return tree[p].sum;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask(p<<1, l, r);
else if(l > mid) return ask(p<<1|1, l, r);
else return ask(p<<1, l, mid) + ask(p<<1|1, mid+1, r);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]);
build(1, 1, n);
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &opt, &l, &r);
if(opt) {
scanf("%lld%lld", &a0,&d);
add(1, l, r, a0, d);
}
else
printf("%lld
", ask(1, l, r));
}
}
//5
//0 0 0 0 0
//555
//1 2 4 2 2
//0 2 2
//0 3 3
//0 4 4
//1 1 3 1 1
//0 1 1
//0 2 2
//0 3 3
区间加等比数列区间求和
#include <bits/stdc++.h>
typedef unsigned long long ll;
const int maxn = 1e5 + 7;
using namespace std;
int n, m, opt, l, r;
ll a[maxn], x, P, a0, q0, q[maxn], sq[maxn];
struct seg{int l,r; ll sum,tag;} tree[maxn<<2];
void push_up(int p) {
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void push_down(int p) {
ll tn = (tree[p<<1].r - tree[p<<1].l + 1), a0 = tree[p].tag;
tree[p<<1].tag += a0;
tree[p<<1].sum += a0*sq[tn-1];
a0 = a0*q[tn]; tn = (tree[p<<1|1].r - tree[p<<1|1].l + 1);
tree[p<<1|1].tag += a0;
tree[p<<1|1].sum += a0*sq[tn-1];
tree[p].tag = 0;
}
void build(int p, int l, int r) {
tree[p].l = l;tree[p].r = r;
tree[p].tag = 0;
if(l == r) {
tree[p].sum = a[l]; return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid), build(p<<1|1, mid+1, r);
push_up(p);
}
void add(int p, int l, int r, ll a0) {
if(tree[p].l == l && tree[p].r == r) {
tree[p].tag += a0;
ll tn = (r-l+1);
tree[p].sum += a0*sq[tn-1];
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) add(p<<1, l, r, a0);
else if(l > mid) add(p<<1|1, l, r, a0);
else {
add(p<<1, l, mid, a0);
ll a1 = a0*q[mid-l+1];
add(p<<1|1, mid+1, r, a1);
}
push_up(p);
}
ll ask(int p, int l, int r) {
if(tree[p].l == l && tree[p].r == r){
return tree[p].sum;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid) return ask(p<<1, l, r);
else if(l > mid) return ask(p<<1|1, l, r);
else return ask(p<<1, l, mid) + ask(p<<1|1, mid+1, r);
}
int main() {
scanf("%d%lld", &n,&q0); q[0]=1;
for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]),q[i]=q[i-1]*q0;
sq[0]=q[0]; for(int i = 1; i <= n; ++i) sq[i] = sq[i-1] + q[i];
build(1, 1, n);
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &opt, &l, &r);
if(opt) {
scanf("%lld", &a0);
add(1, l, r, a0);
}
else
printf("%lld
", ask(1, l, r));
}
}
BZOJ2241
#include <bits/stdc++.h>
using namespace std;
int ans=1e9+7;
int n,m,mp[407][407],a[407][407],sum;
int solve(int x,int y){
if(sum%(x*y))return 0;
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)a[i][j]=mp[i][j];
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]<0)return 0;
if(i+x-1<=n&&j+y-1<=m){
int num=a[i][j];
a[i][j]-=num;
a[i+x][j]+=num;
a[i][j+y]+=num;
a[i+x][j+y]-=num;
}
if(a[i][j]>0)return 0;
}
}
ans=min(ans,sum/x/y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)scanf("%d",&mp[i][j]),sum+=mp[i][j];
for(int i=n;i;--i)
for(int j=m;j;--j)
mp[i][j]-=mp[i-1][j];
for(int i=n;i;--i)
for(int j=m;j;--j)
mp[i][j]-=mp[i][j-1];
for(int C=1;C<=n;++C)
for(int L=1;L<=m;++L){
solve(C,L);
}
printf("%d
",ans);
return 0;
}
EOJ3536
#include <cstdio>
#include <cstring>
#define add(l,r,x)(sc[l]+=x,sc[r+1]-=x)
typedef long long ll;
inline ll read(){
char c=getchar();ll x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
using namespace std;
ll n;
ll sc[200003];
int main()
{
n=read();
if(n==1){
puts("1");
}
else if(n==2){
puts("3");
puts("7");
}
else {
if(n%2){
ll l=n/2+1,r=n/2+1;
add(l,r,1LL);
while(1){
ll x=r-l+1+2;
ll tmp;
tmp = 4LL*(x-1)*(x-1)+x+1LL;
add(l,r,tmp);
--l;++r;
add(l,l,x*(x+1)/2LL);
add(r,r,(5LL*x-3)*x/2LL);
if(l==1)break;
}
}
else{
ll l=n/2,r=n/2+1;
add(l,l,3LL);
add(r,r,7LL);
while(1){
ll x=r-l+1+2,tmp;
tmp = 4LL*(x-1)*(x-1)+x+1LL;
add(l,r,tmp);
--l;++r;
add(l,l,x*(x+1LL)/2);
add(r,r,(5LL*x-3)*x/2LL);
if(l==1)break;
}
}
ll tmp=0;
for(int i=1;i<=n;++i){
tmp+=sc[i];
printf("%lld
",tmp);
}
}
return 0;
}
区间加等差数列维护最大值(BZOJ 2388: 旅行规划 [分块 凸包 等差数列])
发现上课的时候，说的那个证明太假了。。。于是这里稍微严谨点，下面证明：上凸包加等差数列，不改变原凸包上的点这一结论。
我们考虑一种特殊的情况，三个相邻的点，即相邻两点x坐标差为1，且左右两个点在上凸包上，中间的点不在凸包上。设他们的y坐标分别为y1, y2, y3，那么根据凸包的性质有：(y2-y1)/1 < (y3-y1)/2, 即1，2两点的斜率小于1，3两点的斜率，现在给整个序列从左到右加上，a0，a0+d，a0+2*d，现在只需证：((y2+a0+d)-(y1+a0))/1 < ((y3+a0+2*d)-(y1+a0))/2，化简一下得到：(y2-y1)/1 < (y3-y1)/2，这个就是已知，于是得证。
考虑左右两个点之间有n个点不在上凸包上，那么枚举中间的点，用同上的方法，可以分别证明，所有中间的点都不在凸包上。
现在如果凸包上有多个点，我们就枚举相邻的凸包上的点，可以分别证明，所有两点之间的点都不在凸包上。
现在，只需证明，原先凸包上的点都在新凸包上就行了，跟上面一样，我们，考虑，凸包上相邻的三个点，设他们的y坐标为z1, z2, z3, 那么根据凸包的性质，有：(z2-z1) > (z3-z2)，给序列加上等差数列，易证((z2+a0+d)-(z1+a0)) > ((z3+a0+2*d)-(z2+a0+d))，于是得证。枚举中间的点，可以得到凸包上，任意相邻的3个点依然在凸包上，那么可以得到，原凸包上所有点在加了等差数列后，依然在新凸包上，得证。
#include <bits/stdc++.h>
#define pb(x) push_back(x)
typedef long long ll;
const int maxn = 1e5 + 7;
using namespace std;
struct point{
ll x,y;
point(){} point(ll a, ll b) {x=a,y=b;}
}b[maxn], p[maxn];
int cc;
ll xmul(point A,point B,point C) {
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
vector<point> v[maxn];
int n, m, x, y, tp;
ll a[maxn], a0, d;
int l[maxn], r[maxn], belong[maxn], num, B;
ll taga[maxn], tagd[maxn];
void makpt(int L, int R) {
cc = 0; for(int i = L; i <= R; ++i) b[cc] = point(cc, a[i]), ++cc;
}
void adw() {
tp=0;
for(int i=0;i<cc;i++) {
while(tp > 1 && xmul(p[tp-2], p[tp-1], b[i]) > 0) --tp;
p[tp++] = b[i];
}
}
void tuk(int L, int R, vector<point> &v) {
makpt(L, R), adw();
v.clear(); for(int i = 0; i < tp; ++i) v.pb(p[i]);
}
void build() {
B = sqrt(n);
num = n/B; if(n%B) ++num;
for(int i = 1; i <= n; ++i) belong[i] = (i-1)/B+1;
for(int i = 1; i <= num; ++i) l[i] = (i-1)*B+1, r[i] = i*B, taga[i]=tagd[i]=0;
r[num] = n;
for(int i = 1; i <= num; ++i) tuk(l[i], r[i], v[i]);
}
void push_down(int x) {
for(int i = l[x]; i <= r[x]; ++i, taga[x]+=tagd[x]) a[i]+=taga[x];
taga[x] = tagd[x] = 0;
}
void add(int L, int R, ll a0, ll d) {
if(R-L+1 <= B) {
push_down(belong[L]);push_down(belong[R]);
for(int i = L; i <= R; ++i, a0+=d) a[i]+=a0;
tuk(l[belong[L]], r[belong[L]], v[belong[L]]);
tuk(l[belong[R]], r[belong[R]], v[belong[R]]);
return;
}
push_down(belong[L]);
for(int i = L; i <= r[belong[L]]; ++i, a0+=d) a[i]+=a0;
tuk(l[belong[L]], r[belong[L]], v[belong[L]]);
for(int i = belong[L]+1; i <= belong[R]-1; ++i) tagd[i]+=d, taga[i]+=a0, a0+=(r[i]-l[i]+1)*d;
push_down(belong[R]);
for(int i = l[belong[R]]; i <= R; ++i, a0+=d) a[i]+=a0;
tuk(l[belong[R]], r[belong[R]], v[belong[R]]);
}
ll solve(int x, ll a0, ll d) {
int l = 0, r = v[x].size() - 1, mid, midmid;
while(l + 3 < r) {
mid = (l + r) >> 1; midmid = (mid + r) >> 1;
ll H1 = v[x][mid].y + a0 + v[x][mid].x*d;
ll H2 = v[x][midmid].y + a0 + v[x][midmid].x*d;
if(H1 <= H2) l = mid;
else r = midmid;
}
ll ans = 0;
for(int i = l; i <= r; ++i) ans = max(ans, v[x][i].y + a0 + v[x][i].x*d);
return ans;
}
ll ask(int L, int R) {
ll ans = 0;
if(R-L+1 <= B) {
push_down(belong[L]);push_down(belong[R]);
for(int i = L; i <= R; ++i) ans = max(ans, a[i]);
tuk(l[belong[L]], r[belong[L]], v[belong[L]]);
tuk(l[belong[R]], r[belong[R]], v[belong[R]]);
return ans;
}
push_down(belong[L]);
for(int i = L; i <= r[belong[L]] && i <= R; ++i) ans = max(ans, a[i]);
tuk(l[belong[L]], r[belong[L]], v[belong[L]]);
for(int i = belong[L]+1; i <= belong[R]-1; ++i) ans = max(ans, solve(i, taga[i], tagd[i]));
push_down(belong[R]);
for(int i = max(l[belong[R]],L); i <= R; ++i) ans = max(ans, a[i]);
tuk(l[belong[R]], r[belong[R]], v[belong[R]]);
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
build();
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {int opt, L, R;
scanf("%d%d%d", &opt, &L, &R);
if(opt) {
scanf("%lld%lld", &a0, &d);
add(L, R, a0, d);
}
else
printf("%lld
", ask(L, R));
}
}
//5
//2 1 3 2 5
//555
//1 1 4 2 2
//1 1 2 3 3
//0 1 2
找到题了，不过是权限题。。。