「BZOJ2388」旅行规划

2014年5月29日5,3344

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。

题解

桌神：论n*sqrtn*logn大法。

此题可以分块。。。

对于一块内维护一个凸壳

查询每一块内可以二分

修改头尾暴力重构，如果将一整块加上一个值，那么最优的点是不会变的，因为相当于将每两点间的斜率加上一个定值

然后就是分块写起来比较烦，不过我有善良的学长。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define N 100010
#define M 350
#define ll long long
#define linf 1LL<<50 
using namespace std;
inline int read()
{
    int 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,m,block,cnt;
int belong[N];
int st[M],ed[M],num[M];
int stack[M],top,con[M][M];//凸包 
ll h[N],fir[M],dif[M],add[M];//首项、公差 
inline double slop(int x,int y)
{return (double)(h[y]-h[x])/(y-x);}
inline ll cal(int x)
{
    if(x==0||x==n+1)return -linf;
    int t=belong[x];
    return h[x]+fir[t]+dif[t]*(x-st[t])+add[t];
}
void build(int x)
{
     top=0;stack[++top]=st[x];
     for(int i=st[x]+1;i<=ed[x];i++)
     {
         while(top>=2&&slop(stack[top-1],stack[top])<slop(stack[top-1],i))
             top--;
         stack[++top]=i; 
     }
     stack[0]=0;stack[top+1]=n+1;
     num[x]=top;
     for(int i=0;i<=top+1;i++)con[x][i]=stack[i];
}
void init()
{
     n=read();
     for(int i=1;i<=n;i++)
     {
         int x=read();
         h[i]=h[i-1]+x;
     }
     h[0]=h[n+1]=-linf;
     block=(int)sqrt(n);
     if(n%block)cnt=n/block+1;
     else cnt=n/block;
     for(int i=1;i<=n;i++)
         belong[i]=(i-1)/block+1;
     for(int i=1;i<=cnt;i++)
     {
         st[i]=(i-1)*block+1;
         ed[i]=min(n,i*block);
     }
     for(int i=1;i<=cnt;i++)
         build(i);
}
void pushdown(int x)
{
     ll tmp=fir[x];
     for(int i=st[x];i<=ed[x];i++)
     {
         h[i]+=tmp;tmp+=dif[x];h[i]+=add[x]; 
     }
     fir[x]=dif[x]=add[x]=0;
}
ll ask(int x)
{
     int l=1,r=num[x];
     ll h1,h2,h3;
     while(l<=r)
     {
         int mid=(l+r)>>1;
         h1=cal(con[x][mid-1]),h2=cal(con[x][mid]),h3=cal(con[x][mid+1]);
         if(h1<h2&&h2<h3)l=mid+1; 
         else if(h1>h2&&h2>h3)r=mid-1; 
         else return h2;
     }
}
void solve()
{
     int f,x,y,l,r;
     ll k,tmp,ans;
     m=read();
     while(m--)
     {
          f=read();x=read();y=read();
          if(!f)
          {
              k=read();
              l=belong[x];r=belong[y];
              tmp=k*(st[l+1]-x+1);
              for(int i=l+1;i<=r-1;i++)
              {
                  fir[i]+=tmp;dif[i]+=k;
                  tmp+=block*k;
              }
              pushdown(l);
              tmp=k;
              for(int i=x;i<=min(y,ed[l]);i++)
                  h[i]+=tmp,tmp+=k;
              build(l);
              pushdown(r);
              if(l!=r)
              {
                  tmp=k*(st[r]-x+1);
                  for(int i=st[r];i<=y;i++)
                      h[i]+=tmp,tmp+=k;
              }
              tmp=k*(y-x+1);
              for(int i=y+1;i<=ed[r];i++)h[i]+=tmp;
              build(r);
              for(int i=r+1;i<=cnt;i++)add[i]+=tmp;
          }
          else
          {
              l=belong[x];r=belong[y];ans=-linf;
              for(int i=l+1;i<r;i++)
                  ans=max(ans,ask(i));
              for(int i=x;i<=min(y,ed[l]);i++)
                  ans=max(ans,cal(i));
              if(l!=r)
              {
                  for(int i=st[r];i<=y;i++)
                      ans=max(ans,cal(i));
              }
              printf("%lld\n",ans);
          }
     }
}
int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#define N 100010

#define M 350

#define ll long long

#define linf 1LL<<50

using namespace std;

inline int read()

{

int 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,m,block,cnt;

int belong[N];

int st[M],ed[M],num[M];

int stack[M],top,con[M][M];//凸包

ll h[N],fir[M],dif[M],add[M];//首项、公差

inline double slop(int x,int y)

{return (double)(h[y]-h[x])/(y-x);}

inline ll cal(int x)

{

if(x==0||x==n+1)return -linf;

int t=belong[x];

return h[x]+fir[t]+dif[t]*(x-st[t])+add[t];

}

void build(int x)

{

top=0;stack[++top]=st[x];

for(int i=st[x]+1;i<=ed[x];i++)

{

while(top>=2&&slop(stack[top-1],stack[top])<slop(stack[top-1],i))

top--;

stack[++top]=i;

}

stack[0]=0;stack[top+1]=n+1;

num[x]=top;

for(int i=0;i<=top+1;i++)con[x][i]=stack[i];

}

void init()

{

n=read();

for(int i=1;i<=n;i++)

{

int x=read();

h[i]=h[i-1]+x;

}

h[0]=h[n+1]=-linf;

block=(int)sqrt(n);

if(n%block)cnt=n/block+1;

else cnt=n/block;

for(int i=1;i<=n;i++)

belong[i]=(i-1)/block+1;

for(int i=1;i<=cnt;i++)

{

st[i]=(i-1)*block+1;

ed[i]=min(n,i*block);

}

for(int i=1;i<=cnt;i++)

build(i);

}

void pushdown(int x)

{

ll tmp=fir[x];

for(int i=st[x];i<=ed[x];i++)

{

h[i]+=tmp;tmp+=dif[x];h[i]+=add[x];

}

fir[x]=dif[x]=add[x]=0;

}

ll ask(int x)

{

int l=1,r=num[x];

ll h1,h2,h3;

while(l<=r)

{

int mid=(l+r)>>1;

h1=cal(con[x][mid-1]),h2=cal(con[x][mid]),h3=cal(con[x][mid+1]);

if(h1<h2&&h2<h3)l=mid+1;

else if(h1>h2&&h2>h3)r=mid-1;

else return h2;

}

void solve()

{

int f,x,y,l,r;

ll k,tmp,ans;

m=read();

while(m--)

{

f=read();x=read();y=read();

if(!f)

{

k=read();

l=belong[x];r=belong[y];

tmp=k*(st[l+1]-x+1);

for(int i=l+1;i<=r-1;i++)

{

fir[i]+=tmp;dif[i]+=k;

tmp+=block*k;

}

pushdown(l);

tmp=k;

for(int i=x;i<=min(y,ed[l]);i++)

h[i]+=tmp,tmp+=k;

build(l);

pushdown(r);

if(l!=r)

{

tmp=k*(st[r]-x+1);

for(int i=st[r];i<=y;i++)

h[i]+=tmp,tmp+=k;

}

tmp=k*(y-x+1);

for(int i=y+1;i<=ed[r];i++)h[i]+=tmp;

build(r);

for(int i=r+1;i<=cnt;i++)add[i]+=tmp;

}

else

{

l=belong[x];r=belong[y];ans=-linf;

for(int i=l+1;i<r;i++)

ans=max(ans,ask(i));

for(int i=x;i<=min(y,ed[l]);i++)

ans=max(ans,cal(i));

if(l!=r)

{

for(int i=st[r];i<=y;i++)

ans=max(ans,cal(i));

}

printf("%lld\n",ans);

}

int main()

{

init();

solve();

return 0;

}

« 「BZOJ1196」[HNOI2006] 公路修建问题「BZOJ1146」[CTSC2008] 网络管理Network »

Mektpoy

话说神犇们为何不顺便写一下BZOJ3005呢明明是一样的水题呀。。

黑暗世界

给副队跪了，全部都是“水题”

Mektpoy

orz各位学长

黑暗世界

那个也得是三分啊T_T

hzwer.com _ Home | http://hzwer.com

「BZOJ2388」旅行规划

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论