codeforces516c//DrazilandPark//CodeforcesRound#292(Div.1)

题意：一个圆环上有树，猴子上下其中一棵树，再沿着换跑，再上下另一棵树。给出一个区间，问最大的运动距离是。

给出区间大小dst，和数高数组arr。

设区间[x,y]，a[x]=2*arr[x]+dst[1]+dst[2]+......dst[x]。b[x]=2*arr[x]-dst[1]-dst[2]-......dst[x]。[x,y]在线段树中就是a[y]+b[x]。线段树分为很多区间，用数组a,b,s，记录当前区间的a,b最大值，s记录该区间里所有的情况中的爬树+路程的最大值，就是两个子区间中a最大的和b最大的。叶子节点用上面的公式计算。叶子节点s为0,其它的要么区间的最大值来自子区间的s值，要么是左区间的a值+右区间的b值，或者左的b值+右的a，以上几个的最大值。查询的时候查s值。查询结果要返回a,b,s。比如查[1,3]分为[1,2]和[3]，那么结果是[1,2]的s,[3]的s,[1,2]的a+[3]的b,[1,2]的b+[3]的a，以上的最大值。因此a,b,c都要返回。

乱码：

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include iostream
#include cstdio
#include string
#include cstring
#include vector
#include cmath
#include queue
#include stack
#include map
#include set
#include algorithm
#include stack
using namespace std;
const int SZ=8e5+,INF=0x7FFFFFFF;
typedef long long lon;
lon mod=;
lon srcdst[SZ],dst[SZ],tall[SZ],a[SZ],b[SZ],s[SZ],arr[SZ];
lon n,m;
void init(lon n)
{
for(lon i=;i ++i)
{
cin dst[i];
}
for(lon i=n+;i ++i)
{
dst[i]=dst[i-n];
}
for(lon i=;i =*n+;++i)
{
dst[i]+=dst[i-];
}
for(lon i=;i ++i)cin arr[i];
void pushup(lon rt)
{
a[rt]=max(a[rt*],a[rt*+]);
b[rt]=max(b[rt*],b[rt*+]);
lon m1=max(s[rt*],s[rt*+]);
lon m2=max(a[rt*]+b[rt*+],a[rt*+]+b[rt*]);
s[rt]=max(m1,m2);
void build(lon ll,lon rr,lon rt)
{
if(ll==rr)
{
lon real=(ll-)%(n/)+;
a[rt]=*arr[real]+dst[ll];
b[rt]=*arr[real]-dst[ll];
//cout ll " " a[rt] " " b[rt] endl;
return;
}
if(ll rr)return;
lon mid=(ll+rr)/;
build(ll,mid,rt*);
build(mid+,rr,rt*+);
pushup(rt);
struct nd{
lon a,b,s;
nd (lon _a=,lon _b=,lon _s=):a(_a),b(_b),s(_s){}
bool operator==(const nd rbs)const
{
return a==rbs.a b==rbs.b s==rbs.s;
}
nd qry(lon ll,lon rr,lon ql,lon qr,lon rt)
{
nd res1,res2,rbs;
if(ll =ql rr =qr)
{
nd tmp;
tmp.a=a[rt],tmp.b=b[rt],tmp.s=s[rt];
return tmp;
}
//cout ll " " rr " " ql " " qr endl;
if(rr ql||ll qr)return rbs;
lon mid=(ll+rr)/;
if(rr =ql)res1=qry(ll,mid,ql,qr,rt*);
if(ll =qr)res2=qry(mid+,rr,ql,qr,rt*+);
if(res1==rbs)return res2;
else if(res2==rbs)return res1;
else
{
lon max1=max(res1.s,res2.s);
lon max2=max(res1.a+res2.b,res1.b+res2.a);
res1.s=max(max1,max2);
res1.a=max(res1.a,res2.a);
res1.b=max(res1.b,res2.b);
return res1;
}
int main()
{
std::ios::sync_with_stdio();
//freopen("d:\\1.txt","r",stdin);
cin n m;
init(n);
n=*n+;
build(,n,);
for(lon i=;i ++i)
{
lon ql,qr;
cin ql qr;
if(ql =qr)
{
swap(ql,qr);
++ql;
qr+=n/-;
}
else
{
swap(ql,qr);
++ql,--qr;
}
cout qry(,n,ql,qr,).s endl;
}
return ;
}