【bzoj2388】旅行规划

2015.04.28 09:22 Tue | 7次阅读 | 旧日oi | 固定链接 | 源码

Description

OIVillage是一个风景秀美的乡村,为了更好的利用当地的旅游资源,吸引游客,推动经济发展,xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来,让游客可以通过火车从铁路起点(1号景点)出发,依次游览每个景区。为了更好的评价这条铁路,xkszltl为每一个景区都哦赋予了一个美观度,而一条旅行路径的价值就是它所经过的景区的美观度之和。不过,随着天气与季节的变化,某些景点的美观度也会发生变化。
xkszltl希望为每位旅客提供最佳的旅行指导,但是由于游客的时间有限,不一定能游览全部景区,然而他们也不希望旅途过于短暂,所以每个游客都希望能在某一个区间内的车站结束旅程,而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了,xkszltl无法及时完成任务,于是找到了准备虐杀NOI2011的你,希望你能帮助他完成这个艰巨的任务。

Input

第一行给出一个整数n,接下来一行给出n的景区的初始美观度。
第三行给出一个整数m,接下来m行每行为一条指令:
1.         0 x y k:表示将x到y这段铁路边上的景区的美观度加上k;
2.         1 x y:表示有一名旅客想要在x到y这段(含x与y)中的某一站下车,你需要告诉他最大的旅行价值。

Output

对于每个询问,输出一个整数表示最大的旅行价值。

Sample Input

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

Sample Output

9
22

HINT

Data Limit:
对于20%的数据,n,m≤3000;
对于40%的数据,n,m≤30000;
对于50%的数据,n,m≤50000;
另外20%的数据,n,m≤100000,修改操作≤20;
对于100%的数据,n,m≤100000。

题解

这道分块道还挺恶心,前几道实在有点水,hzwer的程序没咋看懂,于是自己写了一份……调了好久……
这道题要维护一个动态的前缀和,这个涉及到各个块内的互相影响,比较难搞。但是考虑到对整个块的修改会使各项间的公差加大,所以我们考虑维护一个等差数列,记录首项和公差,同时在块内还要维护一个凸包……证明可以用v[i]+t*i<v[j]+t*j(t是公差)自己推导一下,发现如果斜率是凹的那么中间点一定不会最优,查询的时候可以用下二分。
程序挺繁琐的,写份注释吧。

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 101000
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,q,w,x,y,block,m;
ll sum[maxn],a[maxn],add[maxn],dif[maxn],st[maxn],fir[maxn],z;
int pos[maxn],con[505][505],num[maxn];
double slop(int x,int y)
{
    return (sum[y]-sum[x])/(y-x);
}
void reset(int x)
{
    int l=(x-1)*block+1,r=min(n,x*block);
    int top=0;st[++top]=l;
    for(int i=l+1;i<=r;i++)
    {
        while(top>=2&&slop(st[top-1],st[top])<slop(st[top-1],i)) top--;
        //维护一个凸包,使得满足答案的单调性 
        st[++top]=i;
    }
    st[0]=0;st[top+1]=n+1;num[x]=top;//首尾设成极小值 
    for(int i=0;i<=top+1;i++) con[x][i]=st[i];
}
void pushdown(int x)//暴力重构块 
{
    ll tmp=fir[x];
    for(int i=(x-1)*block+1;i<=min(x*block,n);i++)
        tmp+=dif[x],sum[i]+=tmp,sum[i]+=add[x];
    add[x]=fir[x]=dif[x]=0;
}
ll calc(int x)//计算某一点的具体值 
{
    return sum[x]+fir[pos[x]]+add[pos[x]]+dif[pos[x]]*(x-(pos[x]-1)*block);
}
ll find(int x)//二分查找块内最值 
{
    int l=1,r=num[x],mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        ll t1=calc(con[x][mid-1]),t2=calc(con[x][mid]),t3=calc(con[x][mid+1]);
        if(t1<t2&&t2<t3) l=mid+1;
        else if(t1>t2&&t2>t3) r=mid-1;
        else return t2;
    }
}
void update(int l,int r,ll x)
{
    ll tmp=0;
    if(pos[l]==pos[r])
    {
        pushdown(pos[l]);
        for(int i=l;i<=r;i++) tmp+=x,sum[i]+=tmp;//暴力修改 
        for(int i=r+1;i<=pos[l]*block;i++) sum[i]+=tmp;//暴力修改 
        for(int i=pos[l]+1;i<=m;i++) add[i]+=tmp;//对之后的块打标记 
        reset(pos[l]);return;
    }
    pushdown(pos[l]);//重构 
    for(int i=l;i<=pos[l]*block;i++) tmp+=x,sum[i]+=tmp;//暴力修改 
    reset(pos[l]);
    for(int i=pos[l]+1;i<pos[r];i++)//打标记,这里的fir[i],tmp的关系需要注意一下,有点乱 
    {
        fir[i]+=tmp;
        dif[i]+=x;
        tmp+=block*x;
    }
    pushdown(pos[r]);
    for(int i=(pos[r]-1)*block+1;i<=r;i++)
        tmp+=x,sum[i]+=tmp;
    for(int i=r+1;i<=pos[r]*block;i++) sum[i]+=tmp;
    reset(pos[r]);
    for(int i=pos[r]+1;i<=m;i++) add[i]+=(r-l+1)*x;
}
ll query(int l,int r)
{
    ll ans=-inf;
    if(pos[l]==pos[r])
    {
        for(int i=l;i<=r;i++) ans=max(ans,calc(i));
        return ans;
    }
    for(int i=l;i<=pos[l]*block;i++) ans=max(ans,calc(i));
    for(int i=(pos[r]-1)*block+1;i<=r;i++) ans=max(ans,calc(i));
    for(int i=pos[l]+1;i<pos[r];i++) ans=max(ans,find(i));
    return ans;
}
int main()
{
    n=read();block=int(sqrt(n));
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        pos[i]=(i-1)/block+1;
        sum[i]=sum[i-1]+a[i];
    }
    sum[0]=sum[n+1]=-inf;
    if(n%block) m=n/block+1;
    else m=n/block;
    for(int i=1;i<=m;i++) reset(i);
    q=read();
    while(q--)
    {
        w=read(),x=read(),y=read();if(x>y) swap(x,y);
        if(w) printf("%lld\n",query(x,y));
        else z=read(),update(x,y,z);
    }
}```