NC52957. 最大子段和
描述
输入描述
第一行两个数n,m
第二行n个数表示这个序列
之后m行，每行四个数l r L R表示一次查询操作
n,m<=1e5,序列中所有数的绝对值<=1e9
输出描述
输出m行，每行一个数表示答案
示例1
输入:
6 5 -1 1 -4 5 -1 4 1 1 4 5 1 1 4 514 2 3 3 3 1 6 -1 5 2 5 2 5
输出:
0 0 0 9 5
说明:
第四组查询中，值域限制是[-1,5]，序列为-1 1 0 5 -1 4，区间[1,6]的最大子段为[2,6]，和为9C++14(g++5.4) 解法, 执行用时: 1369ms, 内存消耗: 17324K, 提交时间: 2020-10-11 21:29:27
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int gi() {
int res = 0, w = 1;
char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
return res * w;
}
typedef long long LL;
const LL INF = 1e18;
const int MAX_N = 1e5 + 5;
//const int LEN = 300;
int LEN;
struct data { LL lmx, rmx, mx, sum; } ;
data operator + (const data &x, const data &y) {
data res;
res.sum = x.sum + y.sum;
res.lmx = max(x.lmx, x.sum + y.lmx);
res.rmx = max(y.rmx, y.sum + x.rmx);
res.mx = max(x.rmx + y.lmx, max(x.mx, y.mx));
return res;
}
int N, Q, a[MAX_N];
vector<int> arr;
vector<vector<data> > vec;
void Div(int l, int r, vector<int> &arr, vector<vector<data> > &vec) {
int n = r - l + 1;
arr.resize(n), vec.resize(n);
for (int i = 0; i < n; i++) vec[i].resize(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) vec[i][j] = (data){0, 0, -INF, 0};
if (l == r) return (void)(arr[0] = a[l], vec[0][0] = (data){a[l], a[l], a[l], a[l]});
vector<int> al, ar, idl, idr;
vector<vector<data> > vl, vr;
int mid = (l + r) >> 1;
Div(l, mid, al, vl);
Div(mid + 1, r, ar, vr);
idl.resize(al.size()), idr.resize(ar.size());
int cnt = 0, pl = 0, pr = 0, nl = al.size(), nr = ar.size();
while (pl != nl || pr != nr) {
if (pl < nl && (pr == nr || al[pl] < ar[pr])) {
idl[pl] = cnt, arr[cnt++] = al[pl++];
} else {
idr[pr] = cnt, arr[cnt++] = ar[pr++];
}
}
for (int i = 0; i < nl; i++)
for (int j = i; j < nl; j++)
for (int k = idl[i]; k > (i ? idl[i - 1] : -1); k--)
for (int l = idl[j]; l < (j < nl - 1 ? idl[j + 1] : n); l++)
vec[k][l] = vl[i][j];
for (int i = 0; i < nr; i++)
for (int j = i; j < nr; j++)
for (int k = idr[i]; k > (i ? idr[i - 1] : -1); k--)
for (int l = idr[j]; l < (j < nr - 1 ? idr[j + 1] : n); l++)
vec[k][l] = vec[k][l] + vr[i][j];
}
struct Query { int v, id; } ql[MAX_N], qr[MAX_N];
bool operator < (const Query &l, const Query &r) { return l.v < r.v; }
int M, lq[MAX_N], rq[MAX_N], L[MAX_N], R[MAX_N];
data ans[MAX_N];
void solve(int l, int r) {
Div(l, r, arr, vec);
int n = r - l + 1;
static int pl[MAX_N], pr[MAX_N];
for (int i = 1, p = 0; i <= Q; i++) {
while (p < n && arr[p] < ql[i].v) ++p;
pl[ql[i].id] = p;
}
for (int i = 1, p = 0; i <= Q; i++) {
while (p < n && arr[p] < qr[i].v) ++p;
pr[qr[i].id] = p;
}
for (int i = 1; i <= Q; i++) {
if (lq[i] <= l && r <= rq[i]) {
int x = pl[i], y = pr[i] - 1;
if (x <= y) ans[i] = ans[i] + vec[x][y];
} else {
for (int j = max(lq[i], l); j <= min(rq[i], r); j++)
if (L[i] <= a[j] && a[j] <= R[i]) ans[i] = ans[i] + (data){a[j], a[j], a[j], a[j]};
}
}
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
N = gi(), Q = gi();
LEN = sqrt(1.0 * N);
for (int i = 1; i <= N; i++) a[i] = gi();
for (int i = 1; i <= Q; i++) {
lq[i] = gi(), rq[i] = gi(), L[i] = gi(), R[i] = gi();
ql[i] = (Query){L[i], i}, qr[i] = (Query){R[i] + 1, i};
}
sort(&ql[1], &ql[Q + 1]);
sort(&qr[1], &qr[Q + 1]);
for (int i = 1; i <= N; i += LEN) solve(i, min(N, i + LEN - 1));
for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i].mx);
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 1586ms, 内存消耗: 56848K, 提交时间: 2022-09-23 21:39:59
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int f=1, r=0; char c=getchar();
while (!isdigit(c)) f^=c=='-', c=getchar();
while (isdigit(c)) r=r*10+(c&15), c=getchar();
return f?r:-r;
}
template<class T> inline void ckmin(T &x, T y) {if (y<x) x=y;}
template<class T> inline void ckmax(T &x, T y) {if (x<y) x=y;}
const int N=1e5+7, M=277;
struct node {
ll l, r, s, v;
node(ll _v=0) {s=_v, v=l=r=max(_v, 0ll);}
node(ll _l, ll _r, ll _s, ll _v) :l(_l), r(_r), s(_s), v(_v) {}
friend node operator +(const node &a, const node &b) {
return node(max(a.l, a.s+b.l), max(a.r+b.s, b.r), a.s+b.s, max({a.v, b.v, a.r+b.l}));
}
node& operator +=(const node &a) {return *this=*this+a;}
};
struct Query {int l, r, L, R;} q[N];
int n, Q, tot, blk, a[N], bel[N], L[1007], R[1007];
int id1[N], id2[N];
node ans[N];
int lv[10][M], v[10][M];
node lval[10][M][M], val[10][M][M];
void solve(int l, int r, int d) {
if (l==r) {
v[d][0]=l, val[d][0][0]=node(a[l]);
return;
}
int mid=(l+r)>>1, lsz=mid-l+1, rsz=r-mid, sz=r-l+1, i=0, j=0, k=0;
solve(l, mid, d+1);
for (i=0; i<lsz; i++) {
lv[d][i]=v[d+1][i];
for (j=i; j<lsz; j++) lval[d][i][j]=val[d+1][i][j];
}
solve(mid+1, r, d+1), i=0, j=0;
while (i<lsz || j<rsz) {
if (j==rsz || (i<lsz && a[lv[d][i]]<=a[v[d+1][j]]))
v[d][k++]=lv[d][i++];
else v[d][k++]=v[d+1][j++];
}
for (k=0, i=0, j=0; k<sz; k++) {
int I=i-1, J=j-1;
for (int o=k; o<sz; o++) {
v[d][o]<=mid?I++:J++; val[d][k][o]=node();
if (i<=I) val[d][k][o]=lval[d][i][I];
if (j<=J) val[d][k][o]+=val[d+1][j][J];
}
v[d][k]<=mid?i++:j++;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
n=read(), Q=read(), blk=max(1., sqrt(n/1.35));
for (int i=1; i<=n; i++) a[i]=read();
for (int i=1; i<=n; i++) bel[i]=(i-1)/blk+1;
tot=bel[n];
for (int i=1; i<=tot; i++) L[i]=(i-1)*blk+1, R[i]=min(n, i*blk);
for (int i=1; i<=Q; i++) q[i].l=read(), q[i].r=read(), q[i].L=read(), q[i].R=read(), id1[i]=id2[i]=i;
sort (id1+1, id1+Q+1, [&](const int &x, const int &y) {return q[x].L<q[y].L;});
sort (id2+1, id2+Q+1, [&](const int &x, const int &y) {return q[x].R<q[y].R;});
for (int i=2; i<tot; i++) {
int l=L[i], r=R[i];
solve(l, r, 0);
static int L[N], R[N];
int sz=r-l+1, p=0;
for (int j=1; j<=Q; j++) {
int x=id1[j];
if (bel[q[x].l]<i && i<bel[q[x].r]) {
while (p<sz && a[v[0][p]]<q[x].L) p++;
L[x]=p;
} else L[x]=sz;
}
p=0;
for (int j=1; j<=Q; j++) {
int x=id2[j];
if (bel[q[x].l]<i && i<bel[q[x].r]) {
while (p<sz && a[v[0][p]]<=q[x].R) p++;
R[x]=p-1;
}
}
for (int j=1; j<=Q; j++)
if (L[j]<=R[j])
ans[j]+=val[0][L[j]][R[j]];
}
for (int i=1; i<=Q; i++) {
int l=q[i].l, r=q[i].r, vl=q[i].L, vr=q[i].R;
if (bel[l]==bel[r]) {
for (int j=l; j<=r; j++) if (vl<=a[j] && a[j]<=vr) ans[i]+=node(a[j]);
} else {
for (int j=L[bel[r]]; j<=r; j++) if (vl<=a[j] && a[j]<=vr) ans[i]+=node(a[j]);
for (int j=R[bel[l]]; j>=l; j--) if (vl<=a[j] && a[j]<=vr) ans[i]=node(a[j])+ans[i];
}
}
for (int i=1; i<=Q; i++) printf("%lld\n", ans[i].v);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1617ms, 内存消耗: 12132K, 提交时间: 2019-09-22 08:48:43
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
#define max(a,b)(a>b?a:b)
#define pb push_back
using namespace std;
const int N=1e5+5,B=200;
int n,m,a[N],le[N],ri[N],Q;
ll ans[N],pre[N];
struct nod{int a,i;}s[N],s2[N],c[N];
bool is[N];
void R(int &n){
char c;int fh=1;for(n=0;(c=getchar())<'0'||c>'9';)if(c=='-')fh=-1;
for(;c<='9'&&c>='0';c=getchar())n=n*10+c-48;n*=fh;
}
struct qu{
int l,r,x,y;
void Re(){R(x);R(y);R(l);R(r);}
}b[N];
struct tr{ll tl,tr,su,mx;}t[(B+5)*4],aa[N],q[B+5][B+5];
inline void plu(tr &z,const tr x,const tr y){
z.mx=max(x.mx,y.mx);
z.mx=max(z.mx,x.tr+y.tl);
z.tl=max(x.tl,x.su+y.tl);
z.tr=max(y.tr,y.su+x.tr);
z.su=x.su+y.su;
}
inline void plus2(ll &ans,ll &pre,const tr x){
ans=max(ans,x.mx);
ans=max(ans,pre+x.tl);
pre=max(pre+x.su,x.tr);
}
bool cmp(nod x,nod y){return x.a<y.a;}
inline void ch(int x,int l){
t[Q+x-l]=(is[x]^=1)?aa[x]:(tr){0,0,0,0};
for(x+=Q-l;x>>=1;)plu(t[x],t[x*2],t[x*2+1]);
}
void solve(int l,int r){
fo(i,l,r)c[i-l]=(nod){a[i],i};
int sz=r-l+1,p=0;
sort(c,c+sz,cmp);
fo(i,1,m){
for(;p<sz&&c[p].a<s[i].a;)++p;
le[s[i].i]=p;
}
p=0;
fo(i,1,m){
for(;p<sz&&c[p].a<=s2[i].a;)++p;
ri[s2[i].i]=p-1;
}
fo(i,1,Q*2-1)t[i]=(tr){0,0,0,0};
fo(i,0,sz-1)if(i&1){
ch(c[i-1].i,l);
fd(j,i,sz-1){
q[i][j]=t[1];
ch(c[j].i,l);
}
}else{
fo(j,i,sz-1){
ch(c[j].i,l);
q[i][j]=t[1];
}
}
fo(i,1,m)if(l<=b[i].y&&b[i].x<=r){
if(b[i].x<=l&&r<=b[i].y){
if(le[i]<=ri[i])plus2(ans[i],pre[i],q[le[i]][ri[i]]);
}else
fo(j,l,r)if(b[i].x<=j&&j<=b[i].y&&b[i].l<=a[j]&&a[j]<=b[i].r)
plus2(ans[i],pre[i],aa[j]);
}
}
int main(){
R(n);R(m);
fo(i,1,n){
R(a[i]);int s=max(0,a[i]);
aa[i]=(tr){s,s,a[i],s};
}
fo(i,1,m)b[i].Re(),s[i]=(nod){b[i].l,i},s2[i]=(nod){b[i].r,i};
sort(s+1,s+m+1,cmp);
sort(s2+1,s2+m+1,cmp);
for(Q=1;Q<B;Q<<=1);
fo(i,1,n/B+(n%B!=0))
solve((i-1)*B+1,min(n,i*B));
fo(i,1,m)printf("%lld\n",ans[i]);
}