BZOJ5089: 最大连续子段和

BZOJ5089: 最大连续子段和

维护一个序列支持以下操作：区间加，区间求最大子段和。n<=50000，m<=50000。

我TM再也不写分块了。。。

先分块，对于块整体加的操作，假设块里面有若干二元组(x,y)，表示一个大小x的区间的和为y，那实际就是求kx+y=z的最大值，而y=-kx+z，所以即求经过这些点、斜率不定的直线的最大纵截距。而稍微画个图可知只有经过一个下凸包上的点的直线可能得到最大纵截距，故每个块维护之。由于区间加的数都是正数，所以查询均摊是O(size)的，而找出所有二元组的(x,y)需要O(size^2)，均摊一下就size=n的立方根 即可。

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 #include<stdlib.h>
  5 #include<math.h>
  6 //#include<iostream>
  7 using namespace std;
  8 
  9 int n,m,q;
 10 #define maxn 50011
 11 #define maxm 55
 12 #define maxt 5011
 13 #define LL long long
 14 LL max(LL a,LL b) {return a>b?a:b;}
 15 LL a[maxn];
 16 struct Block
 17 {
 18     int l,r;
 19     LL add,tot;
 20     int num[maxm],lnum[maxm],rnum[maxm];
 21     LL Max[maxm],lmax[maxm],rmax[maxm];
 22     void down()
 23     {
 24         if (add) for (int i=l;i<=r;i++) a[i]+=add;
 25         add=0;
 26     }
 27     double calc(int i,int j) {return 1.0*(Max[i]-Max[j])/(i-j);}
 28     double lcalc(int i,int j) {return 1.0*(lmax[i]-lmax[j])/(i-j);}
 29     double rcalc(int i,int j) {return 1.0*(rmax[i]-rmax[j])/(i-j);}
 30     void build()
 31     {
 32         int len=r-l+1;
 33         
 34         for (int i=1;i<=len;i++) Max[i]=-1e18;
 35         for (int i=l;i<=r;i++)
 36         {
 37             LL now=0;
 38             for (int j=i;j<=r;j++)
 39             {
 40                 now+=a[j];
 41                 Max[j-i+1]=max(Max[j-i+1],now);
 42             }
 43         }
 44         num[0]=0;
 45         for (int i=1;i<=len;i++)
 46         {
 47             while (num[0]>1 && (calc(num[num[0]],num[num[0]-1])<calc(i,num[num[0]]))) num[0]--;
 48             num[++num[0]]=i;
 49         }
 50         num[num[0]+1]=1;
 51         
 52         lnum[0]=0;
 53         lmax[0]=0;
 54         for (int i=1;i<=len;i++) lmax[i]=lmax[i-1]+a[l+i-1];
 55         for (int i=1;i<=len;i++)
 56         {
 57             while (lnum[0]>1 && (lcalc(lnum[lnum[0]],lnum[lnum[0]-1])<lcalc(i,lnum[lnum[0]]))) lnum[0]--;
 58             lnum[++lnum[0]]=i;
 59         }
 60         lnum[lnum[0]+1]=1;
 61         
 62         rnum[0]=0;
 63         rmax[0]=0;
 64         for (int i=1;i<=len;i++) rmax[i]=rmax[i-1]+a[r-i+1];
 65         for (int i=1;i<=len;i++)
 66         {
 67             while (rnum[0]>1 && (rcalc(rnum[rnum[0]],rnum[rnum[0]-1])<rcalc(i,rnum[rnum[0]]))) rnum[0]--;
 68             rnum[++rnum[0]]=i;
 69         }
 70         rnum[rnum[0]+1]=1;
 71         
 72         tot=0;
 73         for (int i=l;i<=r;i++) tot+=a[i];
 74     }
 75     LL getans()
 76     {
 77         while (num[num[0]+1]<num[0] && calc(num[num[num[0]+1]+1],num[num[num[0]+1]])>-add)
 78             num[num[0]+1]++;
 79         return max(num[num[num[0]+1]]*add+Max[num[num[num[0]+1]]],0ll);
 80     }
 81     LL getlans()
 82     {
 83         while (lnum[lnum[0]+1]<lnum[0] && lcalc(lnum[lnum[lnum[0]+1]+1],lnum[lnum[lnum[0]+1]])>-add)
 84             lnum[lnum[0]+1]++;
 85         return max(lnum[lnum[lnum[0]+1]]*add+lmax[lnum[lnum[lnum[0]+1]]],0ll);
 86     }
 87     LL getrans()
 88     {
 89         while (rnum[rnum[0]+1]<rnum[0] && rcalc(rnum[rnum[rnum[0]+1]+1],rnum[rnum[rnum[0]+1]])>-add)
 90             rnum[rnum[0]+1]++;
 91         return max(rnum[rnum[rnum[0]+1]]*add+rmax[rnum[rnum[rnum[0]+1]]],0ll);
 92     }
 93 }b[maxt];
 94 
 95 int bel[maxn],tot;
 96 void modify(int x,int y,int v)
 97 {
 98     if (bel[x]==bel[y])
 99     {
100         b[bel[x]].down();
101         for (int i=x;i<=y;i++) a[i]+=v;
102         b[bel[x]].build();
103     }
104     else
105     {
106         int z=b[bel[x]].r;
107         b[bel[x]].down();
108         for (int i=x;i<=z;i++) a[i]+=v;
109         b[bel[x]].build();
110         z=b[bel[y]].l;
111         b[bel[y]].down();
112         for (int i=y;i>=z;i--) a[i]+=v;
113         b[bel[y]].build();
114         for (int i=bel[x]+1;i<bel[y];i++) b[i].add+=v;
115     }
116 }
117 LL query(int x,int y)
118 {
119     if (bel[x]==bel[y])
120     {
121         b[bel[x]].down();
122         b[bel[x]].build();
123         LL ans=0,now=0;
124         for (int i=x;i<=y;i++)
125         {
126             now+=a[i];
127             if (now<0) now=0;
128             ans=max(ans,now);
129         }
130         return ans;
131     }
132     else
133     {
134         b[bel[x]].down();
135         b[bel[x]].build();
136         b[bel[y]].down();
137         b[bel[y]].build();
138         int z=b[bel[x]].r;
139         LL ans=0,rans=0,now=0;
140         for (int i=x;i<=z;i++)
141         {
142             now+=a[i];
143             if (now<0) now=0;
144             ans=max(ans,now);
145         }
146         LL tot=0;
147         for (int i=z;i>=x;i--)
148         {
149             tot+=a[i];
150             rans=max(rans,tot);
151         }
152         for (int i=bel[x]+1;i<bel[y];i++)
153         {
154             LL ll=b[i].getlans(),rr=b[i].getrans(),tt=b[i].tot+(b[i].r-b[i].l+1)*b[i].add;
155             ans=max(ans,max(b[i].getans(),ll+rans));
156             rans=max(0,max(rr,rans+tt));
157         }
158         z=b[bel[y]].l;
159         for (int i=z;i<=y;i++)
160         {
161             rans+=a[i];
162             if (rans<0) rans=0;
163             ans=max(ans,rans);
164         }
165         return ans;
166     }
167 }
168 int main()
169 {
170     scanf("%d%d",&n,&q);
171     m=40;
172     for (int i=1;i<=n;i++) bel[i]=(i-1)/m+1;
173     tot=bel[n];
174     for (int i=1;i<tot;i++) b[i].l=(i-1)*m+1,b[i].r=i*m;
175     b[tot].l=(tot-1)*m+1,b[tot].r=n;
176     
177     for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
178     for (int i=1;i<=tot;i++) b[i].build();
179     
180     char id[5];int x,y,z;
181     while (q--)
182     {
183         scanf("%s",id);
184         if (id[0]=='A')
185         {
186             scanf("%d%d%d",&x,&y,&z);
187             modify(x,y,z);
188         }
189         else
190         {
191             scanf("%d%d",&x,&y);
192             printf("%lldn",query(x,y));
193         }
194     }
195     return 0;
196 }

我就是死外边，从这里跳下去，我也不再写分块！

转载于:.html