NC14594. 珂朵莉的序列
描述
输入描述
第一行两个数n,m
之后一行n个数表示这个序列
之后m行，每行一个操作
1 x : 所有数都加上x
2 l r : 查询区间[l,r]内的最大子段和（可以不选数）
输出描述
对于每个2种类操作，输出一行一个数表示答案
示例1
输入:
5 7 -10 -3 -2 -4 -5 2 2 4 1 5 2 2 4 1 3 2 1 5 1 2 2 3 5
输出:
0 6 18 19
C++14(g++5.4) 解法, 执行用时: 3861ms, 内存消耗: 291800K, 提交时间: 2019-02-02 23:41:31
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
struct qq
{
long long vl[4];
};
long long nowx;
const long long inf=(1LL<<62)-1+(1LL<<62);
struct query
{
int flag,l,r,id;
long long x;
bool operator <(const query &temp)const
{
if(x==temp.x)
return id<temp.id;
return x<temp.x;
}
};
query qy[660000];
int n,m;
long long a[330000];
long long ans[660000];
struct pp
{
int cnt;
long long sum;
};
pp now;
struct segment_tree
{
int l,r,cnt;
long long sum;
long long delta,x;
vector<pp>ll,rr,mm;
int head[3];
};
segment_tree tree[1<<20];
void add(vector<pp>&ret,pp now)
{
pp nw;
while(ret.size()>=1)
{
nw=ret.back();
if(nw.sum>=now.sum&&nw.cnt==now.cnt)
return;
if(nw.sum<=now.sum)
ret.pop_back();
else
break;
}
while(ret.size()>=2)
{
pp a,b,c;
a=ret[ret.size()-2];
b=ret[ret.size()-1];
c=now;
double k1,k2;
k1=(double)(a.sum-b.sum)/(double)(b.cnt-a.cnt);
k2=(double)(b.sum-c.sum)/(double)(c.cnt-b.cnt);
if(k1>=k2)
ret.pop_back();
else
break;
}
ret.push_back(now);
}
void merge1(vector<pp>&ret,vector<pp>&a,vector<pp>&b)
{
ret.clear();
int i=0,j=0;
while(i<a.size()&&j<b.size())
{
if(a[i].cnt<b[j].cnt)
{
add(ret,a[i]);
i++;
}
else
{
add(ret,b[j]);
j++;
}
}
while(i<a.size())
{
add(ret,a[i]);
i++;
}
while(j<b.size())
{
add(ret,b[j]);
j++;
}
}
void merge3(vector<pp>&ret,vector<pp>&a,vector<pp>&b)
{
ret.clear();
int i=0,j=0;
double k1,k2;
while(i<a.size()&&j<b.size())
{
if(i+1>=a.size())
k1=inf;
else
k1=(double)(a[i].sum-a[i+1].sum)/(double)(a[i+1].cnt-a[i].cnt);
if(j+1>=b.size())
k2=inf;
else
k2=(double)(b[j].sum-b[j+1].sum)/(double)(b[j+1].cnt-b[j].cnt);
now.cnt=a[i].cnt+b[j].cnt;
now.sum=a[i].sum+b[j].sum;
add(ret,now);
if(k1<k2)
i++;
else
j++;
}
}
void merge(segment_tree &ret,segment_tree ll,segment_tree rr)
{
int i,j,s,p,q;
vector<pp>vec;
vec.clear();
ret.sum=ll.sum+rr.sum;
ret.cnt=ll.cnt+rr.cnt;
for(i=0;i<rr.ll.size();i++)
{
now.sum=rr.ll[i].sum+ll.sum;
now.cnt=rr.ll[i].cnt+ll.cnt;
vec.push_back(now);
}
merge1(ret.ll,vec,ll.ll);
vec.clear();
for(i=0;i<ll.rr.size();i++)
{
now.sum=ll.rr[i].sum+rr.sum;
now.cnt=ll.rr[i].cnt+rr.cnt;
vec.push_back(now);
}
merge1(ret.rr,vec,rr.rr);
vec.clear();
merge3(vec,rr.ll,ll.rr);
merge1(ret.mm,vec,rr.mm);
vec.clear();
for(i=0;i<ret.mm.size();i++)
vec.push_back(ret.mm[i]);
merge1(ret.mm,vec,ll.mm);
}
void build(int left,int right,int id)
{
int l=2*id+1,r=2*id+2,mid=(left+right)>>1;
tree[id].l=left;
tree[id].r=right;
tree[id].delta=0;
tree[id].ll.clear();
tree[id].rr.clear();
tree[id].mm.clear();
memset(tree[id].head,0,sizeof(tree[id].head));
if(left==right)
{
tree[id].sum=a[left];
tree[id].cnt=1;
now.cnt=now.sum=0;
add(tree[id].ll,now);
add(tree[id].rr,now);
add(tree[id].mm,now);
now.cnt=1;
now.sum=a[left];
add(tree[id].ll,now);
add(tree[id].rr,now);
add(tree[id].mm,now);
return;
}
build(left,mid,l);
build(mid+1,right,r);
merge(tree[id],tree[l],tree[r]);
}
void reconstruct(int &head,vector<pp>&awp,long long delta)
{
while(head+1<awp.size())
{
double k=(double)(awp[head].sum-awp[head+1].sum)/(double)(awp[head+1].cnt-awp[head].cnt);
if(k<=delta)
head++;
else
break;
}
}
void zz(int id)
{
reconstruct(tree[id].head[0],tree[id].ll,nowx);
reconstruct(tree[id].head[1],tree[id].rr,nowx);
reconstruct(tree[id].head[2],tree[id].mm,nowx);
}
qq qw(int left,int right,int id)
{
int l=2*id+1,r=2*id+2;
qq ret;
memset(ret.vl,0,sizeof(ret.vl));
if(tree[id].r<left||tree[id].l>right)
return ret;
if(tree[id].l>=left&&tree[id].r<=right)
{
zz(id);
ret.vl[0]=tree[id].mm[tree[id].head[2]].sum+1LL*nowx*tree[id].mm[tree[id].head[2]].cnt;
ret.vl[1]=tree[id].ll[tree[id].head[0]].sum+1LL*nowx*tree[id].ll[tree[id].head[0]].cnt;
ret.vl[2]=tree[id].rr[tree[id].head[1]].sum+1LL*nowx*tree[id].rr[tree[id].head[1]].cnt;
ret.vl[3]=tree[id].sum+1LL*tree[id].cnt*nowx;
return ret;
}
qq lp,rp;
lp=qw(left,right,l);
rp=qw(left,right,r);
ret.vl[0]=max(lp.vl[0],rp.vl[0]);
ret.vl[0]=max(ret.vl[0],lp.vl[2]+rp.vl[1]);
ret.vl[1]=max(lp.vl[1],lp.vl[3]+rp.vl[1]);
ret.vl[2]=max(rp.vl[2],rp.vl[3]+lp.vl[2]);
ret.vl[3]=lp.vl[3]+rp.vl[3];
return ret;
}
int main()
{
int i,j,s,p,q,cmft=0;
scanf("%d%d",&n,&m);
int x;
for(i=0;i<n;i++)
{
scanf("%d",&x);
a[i]=x;
}
long long delta=0;
for(i=0;i<m;i++)
{
scanf("%d",&qy[i].flag);
if(qy[i].flag==1)
{
scanf("%d",&x);
qy[i].x=x;
if(i)
qy[i].x+=qy[i-1].x;
}
else
{
qy[i].id=cmft++;
scanf("%d%d",&qy[i].l,&qy[i].r);
qy[i].l--;
qy[i].r--;
if(i)
qy[i].x=qy[i-1].x;
else
qy[i].x=0;
}
}
sort(qy,qy+m);
for(i=1;i<m;i++)
qy[i].x-=qy[0].x;
for(i=0;i<n;i++)
a[i]+=qy[0].x;
qy[0].x=0;
for(i=m-1;i>0;i--)
qy[i].x-=qy[i-1].x;
build(0,n-1,0);
nowx=0;
for(i=0;i<m;i++)
{
nowx+=qy[i].x;
if(qy[i].flag==2)
{
qq awp=qw(qy[i].l,qy[i].r,0);
ans[qy[i].id]=awp.vl[0];
}
}
for(i=0;i<cmft;i++)
printf("%lld\n",ans[i]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 2749ms, 内存消耗: 291896K, 提交时间: 2018-01-06 17:23:06
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
struct qq
{
long long vl[4];
};
long long nowx;
const long long inf=(1LL<<62)-1+(1LL<<62);
struct query
{
int flag,l,r,id;
long long x;
bool operator <(const query &temp)const
{
if(x==temp.x)
return id<temp.id;
return x<temp.x;
}
};
query qy[660000];
int n,m;
long long a[330000];
long long ans[660000];
struct pp
{
int cnt;
long long sum;
};
pp now;
struct segment_tree
{
int l,r,cnt;
long long sum;
long long delta,x;
vector<pp>ll,rr,mm;
int head[3];
};
segment_tree tree[1<<20];
void add(vector<pp>&ret,pp now)
{
pp nw;
while(ret.size()>=1)
{
nw=ret.back();
if(nw.sum>=now.sum&&nw.cnt==now.cnt)
return;
if(nw.sum<=now.sum)
ret.pop_back();
else
break;
}
while(ret.size()>=2)
{
pp a,b,c;
a=ret[ret.size()-2];
b=ret[ret.size()-1];
c=now;
double k1,k2;
k1=(double)(a.sum-b.sum)/(double)(b.cnt-a.cnt);
k2=(double)(b.sum-c.sum)/(double)(c.cnt-b.cnt);
if(k1>=k2)
ret.pop_back();
else
break;
}
ret.push_back(now);
}
void merge1(vector<pp>&ret,vector<pp>&a,vector<pp>&b)
{
ret.clear();
int i=0,j=0;
while(i<a.size()&&j<b.size())
{
if(a[i].cnt<b[j].cnt)
{
add(ret,a[i]);
i++;
}
else
{
add(ret,b[j]);
j++;
}
}
while(i<a.size())
{
add(ret,a[i]);
i++;
}
while(j<b.size())
{
add(ret,b[j]);
j++;
}
}
void merge3(vector<pp>&ret,vector<pp>&a,vector<pp>&b)
{
ret.clear();
int i=0,j=0;
double k1,k2;
while(i<a.size()&&j<b.size())
{
if(i+1>=a.size())
k1=inf;
else
k1=(double)(a[i].sum-a[i+1].sum)/(double)(a[i+1].cnt-a[i].cnt);
if(j+1>=b.size())
k2=inf;
else
k2=(double)(b[j].sum-b[j+1].sum)/(double)(b[j+1].cnt-b[j].cnt);
now.cnt=a[i].cnt+b[j].cnt;
now.sum=a[i].sum+b[j].sum;
add(ret,now);
if(k1<k2)
i++;
else
j++;
}
}
void merge(segment_tree &ret,segment_tree ll,segment_tree rr)
{
int i,j,s,p,q;
vector<pp>vec;
vec.clear();
ret.sum=ll.sum+rr.sum;
ret.cnt=ll.cnt+rr.cnt;
for(i=0;i<rr.ll.size();i++)
{
now.sum=rr.ll[i].sum+ll.sum;
now.cnt=rr.ll[i].cnt+ll.cnt;
vec.push_back(now);
}
merge1(ret.ll,vec,ll.ll);
vec.clear();
for(i=0;i<ll.rr.size();i++)
{
now.sum=ll.rr[i].sum+rr.sum;
now.cnt=ll.rr[i].cnt+rr.cnt;
vec.push_back(now);
}
merge1(ret.rr,vec,rr.rr);
vec.clear();
merge3(vec,rr.ll,ll.rr);
merge1(ret.mm,vec,rr.mm);
vec.clear();
for(i=0;i<ret.mm.size();i++)
vec.push_back(ret.mm[i]);
merge1(ret.mm,vec,ll.mm);
}
void build(int left,int right,int id)
{
int l=2*id+1,r=2*id+2,mid=(left+right)>>1;
tree[id].l=left;
tree[id].r=right;
tree[id].delta=0;
tree[id].ll.clear();
tree[id].rr.clear();
tree[id].mm.clear();
memset(tree[id].head,0,sizeof(tree[id].head));
if(left==right)
{
tree[id].sum=a[left];
tree[id].cnt=1;
now.cnt=now.sum=0;
add(tree[id].ll,now);
add(tree[id].rr,now);
add(tree[id].mm,now);
now.cnt=1;
now.sum=a[left];
add(tree[id].ll,now);
add(tree[id].rr,now);
add(tree[id].mm,now);
return;
}
build(left,mid,l);
build(mid+1,right,r);
merge(tree[id],tree[l],tree[r]);
}
void reconstruct(int &head,vector<pp>&awp,long long delta)
{
while(head+1<awp.size())
{
double k=(double)(awp[head].sum-awp[head+1].sum)/(double)(awp[head+1].cnt-awp[head].cnt);
if(k<=delta)
head++;
else
break;
}
}
void zz(int id)
{
reconstruct(tree[id].head[0],tree[id].ll,nowx);
reconstruct(tree[id].head[1],tree[id].rr,nowx);
reconstruct(tree[id].head[2],tree[id].mm,nowx);
}
qq qw(int left,int right,int id)
{
int l=2*id+1,r=2*id+2;
qq ret;
memset(ret.vl,0,sizeof(ret.vl));
if(tree[id].r<left||tree[id].l>right)
return ret;
if(tree[id].l>=left&&tree[id].r<=right)
{
zz(id);
ret.vl[0]=tree[id].mm[tree[id].head[2]].sum+1LL*nowx*tree[id].mm[tree[id].head[2]].cnt;
ret.vl[1]=tree[id].ll[tree[id].head[0]].sum+1LL*nowx*tree[id].ll[tree[id].head[0]].cnt;
ret.vl[2]=tree[id].rr[tree[id].head[1]].sum+1LL*nowx*tree[id].rr[tree[id].head[1]].cnt;
ret.vl[3]=tree[id].sum+1LL*tree[id].cnt*nowx;
return ret;
}
qq lp,rp;
lp=qw(left,right,l);
rp=qw(left,right,r);
ret.vl[0]=max(lp.vl[0],rp.vl[0]);
ret.vl[0]=max(ret.vl[0],lp.vl[2]+rp.vl[1]);
ret.vl[1]=max(lp.vl[1],lp.vl[3]+rp.vl[1]);
ret.vl[2]=max(rp.vl[2],rp.vl[3]+lp.vl[2]);
ret.vl[3]=lp.vl[3]+rp.vl[3];
return ret;
}
int main()
{
int i,j,s,p,q,cmft=0;
scanf("%d%d",&n,&m);
int x;
for(i=0;i<n;i++)
{
scanf("%d",&x);
a[i]=x;
}
long long delta=0;
for(i=0;i<m;i++)
{
scanf("%d",&qy[i].flag);
if(qy[i].flag==1)
{
scanf("%d",&x);
qy[i].x=x;
if(i)
qy[i].x+=qy[i-1].x;
}
else
{
qy[i].id=cmft++;
scanf("%d%d",&qy[i].l,&qy[i].r);
qy[i].l--;
qy[i].r--;
if(i)
qy[i].x=qy[i-1].x;
else
qy[i].x=0;
}
}
sort(qy,qy+m);
for(i=1;i<m;i++)
qy[i].x-=qy[0].x;
for(i=0;i<n;i++)
a[i]+=qy[0].x;
qy[0].x=0;
for(i=m-1;i>0;i--)
qy[i].x-=qy[i-1].x;
build(0,n-1,0);
nowx=0;
for(i=0;i<m;i++)
{
nowx+=qy[i].x;
if(qy[i].flag==2)
{
qq awp=qw(qy[i].l,qy[i].r,0);
ans[qy[i].id]=awp.vl[0];
}
}
for(i=0;i<cmft;i++)
printf("%lld\n",ans[i]);
return 0;
}