(225,221,44));bTrue[(nNum 3)%7]=

来源：蜘蛛抓取(WebSpider) 时间：2011-12-14 21:19 标签： 221.204.225.38
inti,m,j,k,bTrue[(nNum 4)%7];k[q->link[0]==nil];Huge*multiply
k[q->link[0]==nil];_DX=比较Huge*multiplybTrue[(nNum 4)%7];
为您推荐：
其他类似问题
扫描下载二维码计算几何（42）
分块（14）
2388: 旅行规划
Time Limit:&50 Sec&&Memory Limit:&128 MB
Submit:&281&&Solved:&78
Description
xkszltl希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl无法及时完成任务，于是找到了准备虐杀NOI2011的你，希望你能帮助他完成这个艰巨的任务。
第三行给出一个整数m，接下来m行每行为一条指令：
1.0 x y k：表示将x到y这段铁路边上的景区的美观度加上k；
2.1 x y：表示有一名旅客想要在x到y这段（含x与y）中的某一站下车，你需要告诉他最大的旅行价值。
Sample Input
Sample Output
题解：分块+凸包+三分
因为是前缀和，所以我们不好直接用数据结构维护。所以我们将序列分块，然后对于块内维护delta,k,s[x]，delta表示是该块中所有的位置共同的累加量，k表示的是每个位置都要增加(x-l+1)*K(l表示该块第一个元素的位置)，s[x]表示的是x位置的前缀和。
对于一个块内的最大值，我们相当于查询delta+max(s[x]+k*(x-l+1))。设yi=s[i],xi=i，那么我们要求的其实就是z=yi+k*(xi-l+1)，看做是一条过(xi,yi)斜率为-k的直线与y轴截距的最大值。我们可以发现取最大值的点一定在该区域点的上凸壳上，所以我们对于每个块维护凸壳，然后查找的时候在凸包上三分即可。
对于修改，我们暴力修改不完整的块，然后重建凸壳，对于完整的块，我们直接修改delta,k.
对于查询，我们暴力不完整块的最大值，对于完整的块，我们在凸壳上三分。
#include&iostream&
#include&cstdio&
#include&algorithm&
#include&cstring&
#include&cmath&
#define N 100003
#define LL long long
const LL inf=1e18;
int belong[N],block,l[N],r[N],n,m;
LL delta[N],k[N],s[N];
struct point{
point (LL X=0,LL Y=0){
}a[N],ch[N];
point operator -(point a,point b)
return point (a.x-b.x,a.y-b.y);
struct data{
point x[400];
int cmp(point a,point b)
return a.x&b.x||a.x==b.x&&a.y&b.y;
LL cross(point a,point b)
return a.x*b.y-a.y*b.x;
void build(int num)
sort(a+l[num],a+r[num]+1,cmp);
if (r[num]-l[num]+1&=2) {
c[num].size=r[num]-l[num]+1;
for (int i=1;i&=c[num].i++) c[num].x[i]=a[i+l[num]-1];
int pos=m;
for (int i=r[num];i&=l[num];i--){
while (m&1&&cross(ch[m-1]-ch[m-2],a[i]-ch[m-2])&=0) m--;
ch[m++]=a[i];
c[num].size=m-pos+1;
for (int i=m;i&=0;i--)
c[num].x[++t]=ch[i];
bool check(int x1,int x2,int num)
LL t1=(LL)(c[num].x[x1].x-l[num]+1)*k[num]+c[num].x[x1].y;
LL t2=(LL)(c[num].x[x2].x-l[num]+1)*k[num]+c[num].x[x2].y;
return t1&t2;
LL solve(int num)
int ls=1; int rs=c[num].
int ans=0;
while (ls&=rs) {
int mid=(ls+rs)/2;
int mid1=(mid+rs+1)/2;
if (check(mid1,mid,num)) ls=mid+1;
else rs=mid1-1;
return (LL)(c[num].x[ls].x-l[num]+1)*k[num]+c[num].x[ls].y;
int main()
freopen(&a.in&,&r&,stdin);
freopen(&my.out&,&w&,stdout);
scanf(&%d&,&n);
for (int i=1;i&=n;i++) {
LL scanf(&%I64d&,&x);
s[i]=s[i-1]+x;
a[i].x=i; a[i].y=s[i];
block=sqrt(n);
int t=ceil(n*1.0/block);
for (int i=1;i&=t;i++) l[i]=n,r[i]=0;
for (int i=1;i&=n;i++){
belong[i]=(i-1)/block+1;
l[belong[i]]=min(l[belong[i]],i);
r[belong[i]]=max(r[belong[i]],i);
for (int i=1;i&=t;i++) build(i);
scanf(&%d&,&m);
for (int i=1;i&=m;i++){
int opt,x,y; LL
scanf(&%d%d%d&,&opt,&x,&y);
if (opt==1) {
if (belong[x]==belong[y]) {
for (int j=x;j&=y;j++) mx=max(mx,s[j]+delta[belong[x]]+k[belong[x]]*(LL)(j-l[belong[x]]+1));
printf(&%I64d\n&,mx);
for (int j=x;j&=r[belong[x]];j++) mx=max(mx,s[j]+delta[belong[x]]+k[belong[x]]*(LL)(j-l[belong[x]]+1));
for (int j=l[belong[y]];j&=y;j++)
mx=max(mx,s[j]+delta[belong[y]]+k[belong[y]]*(LL)(j-l[belong[y]]+1));
for (int j=belong[x]+1;j&=belong[y]-1;j++)
mx=max(mx,solve(j)+delta[j]);
printf(&%I64d\n&,mx);
if (opt==0) {
scanf(&%I64d&,&val);
if (belong[x]==belong[y]) {
for (int j=x;j&=y;j++)
s[j]+=(LL)(j-x+1)*val,a[j].y=s[j];
for (int j=y+1;j&=r[belong[y]];j++) s[j]+=(LL)(y-x+1)*val,a[j].y=s[j];
for (int j=belong[y]+1;j&=t;j++) delta[j]+=(LL)(y-x+1)*
build(belong[x]);
for (int j=belong[x]+1;j&=belong[y]-1;j++)
delta[j]+=(LL)(l[j]-x)*val,k[j]+=
for (int j=x;j&=r[belong[x]];j++) s[j]+=(LL)(j-x+1)*val,a[j].y=s[j];
build(belong[x]);
for (int j=l[belong[y]];j&=y;j++) s[j]+=(LL)(j-x+1)*val,a[j].y=s[j];
for (int j=y+1;j&=r[belong[y]];j++) s[j]+=(LL)(y-x+1)*val,a[j].y=s[j];
for (int j=belong[y]+1;j&=t;j++) delta[j]+=(LL)(y-x+1)*
build(belong[y]);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：86417次
积分：8805
积分：8805
排名：第1711名
原创：809篇
转载：12篇
评论：17条
(87)(96)(93)(51)(41)(51)(4)(3)(120)(94)(70)(39)(40)(53)

我要回帖

更多关于 221.204.225.38 的文章

 

随机推荐