Remake_ @ 2020-12-04 10:58:24
Rt,我用分块写的,吸完氧之后拿到了
有没有好心人帮蒟蒻看看RE的原因啊QAQ,看了好久都没看出来哪里能导致RE QAQ:
#include<bits/stdc++.h>
using namespace std;
int n,m,opt,x,y,L[1005],R[1005],sum[1005],maxx[1005],zj[1005],yj[1005],a[600005],bel[600005],siz;
int sum1,sum2,ans;
inline int mymax(int qaq,int qwq) {
return qaq>qwq?qaq:qwq;
}
int main() {
fill(maxx+1,maxx+1001,-0x7fffffff);
fill(zj+1,zj+1001,-0x7fffffff);
fill(yj+1,yj+1001,-0x7fffffff);
scanf("%d%d",&n,&m);
siz=sqrt(ceil(n));
for(int i=1; i<=n; i++) scanf("%d",a+i);
for(int i=1; i<=siz; i++) {
L[i]=(i-1)*siz+1;
R[i]=i*siz;
sum1=sum2=0;
for(int j=L[i]; j<=R[i]; j++) {
maxx[i]=mymax(maxx[i],a[j]);
sum[i]+=a[j];
bel[j]=i;
sum1+=a[j];
zj[i]=mymax(zj[i],sum1);
if(sum2+a[j]>0) {
sum2+=a[j];
maxx[i]=mymax(maxx[i],sum2);
} else sum2=mymax(0,a[j]);
}
sum1=0;
for(int j=R[i]; j>=L[i]; j--) {
sum1+=a[j];
yj[i]=mymax(yj[i],sum1);
}
}
while(m--) {
scanf("%d",&opt);
if(opt==1) {
ans=-0x7fffffff;
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
if(bel[x]==bel[y]){
sum1=0;
for(int i=x;i<=y;i++){
ans=mymax(ans,a[i]);
if(sum1+a[i]>=0){
sum1+=a[i];
ans=mymax(ans,sum1);
}
else sum1=mymax(0,a[i]);
}
}
else{
int tmpx=x,tmpy=y,now=0;
for(;tmpx!=L[bel[tmpx]];++tmpx);
for(;tmpy!=R[bel[tmpy]];--tmpy);
tmpx=bel[tmpx];
tmpy=bel[tmpy];
for(;x!=L[bel[x]];++x){
ans=mymax(ans,a[x]);
if(now+a[x]>=0){
now+=a[x];
ans=mymax(ans,now);
}
else now=mymax(0,a[x]);
}
for(int i=tmpx;i<=tmpy;i++){
ans=mymax(maxx[i],ans);
ans=mymax(now+zj[i],ans);
now=mymax(0,mymax(yj[i],now+sum[i]));
}
for(int i=R[tmpy]+1;i<=y;i++){
ans=mymax(ans,a[i]);
if(now+a[i]>=0){
now+=a[i];
ans=mymax(ans,now);
}
else now=mymax(0,a[i]);
}
}
printf("%d\n",ans);
} else {
scanf("%d%d",&x,&y);
a[x]=y;
sum[bel[x]]=sum1=sum2=0;
maxx[bel[x]]=zj[bel[x]]=yj[bel[x]]=-0x7fffffff;
for(int j=L[bel[x]]; j<=R[bel[x]]; j++) {
maxx[bel[x]]=mymax(maxx[bel[x]],a[j]);
sum[bel[x]]+=a[j];
sum1+=a[j];
zj[bel[x]]=mymax(zj[bel[x]],sum1);
if(sum2+a[j]>=0) {
sum2+=a[j];
maxx[bel[x]]=mymax(maxx[bel[x]],sum2);
} else sum2=0;
}
sum1=0;
for(int j=R[bel[x]]; j>=L[bel[x]]; j--) {
sum1+=a[j];
yj[bel[x]]=mymax(yj[bel[x]],sum1);
}
}
}
}
by Remake_ @ 2020-12-04 11:25:46
问题找出来了,我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼我是傻逼
by FTR_CLCX @ 2021-07-06 17:37:56
so?
by FTR_CLCX @ 2021-07-06 17:38:14
什么问题