健康年糕/p
therearenwoodenrodsverticallyplacedoverahorizontalline.therodsarenumbered1throughnfromlefttoright.each rodi (1in ) ISplacer
atermitewantstoeatalltherodsonebyone.itstartseatingfromanarbitraryrods (1sn ).Then，aftereating a rod i， thetermiteselectsthenextrodtoeatbasedonthefollowingmethod.amongtheremainingrodsj，theonewithmaximumhj-| Xi-XJ|is selech
If there are still ties，the left-most rod is selected。
yourtaskistocalculatethetotal (horizontal ) distancetraveledbythetermitetoeatalltherods。
输入
thefirstlineoftheinputcontainstwospace-separatedintegersn，the number of rods，and s， thestartingRodnumber(1sn100000 ).therodsaredescribedinthenextnlines.ont helin e1i ) 1In )，thei-throdisspecifiedwiththtwon
输出功率
youshouldprintasingleintegerdenotingthetotaldistancetraveledbythetermite。
样品输入复印
5 31 34 88 210 411 1样品输出副本
2011-12-17问题摘要：给出起始位置。 从开始位置每次选择一个位置。 其位置满足问题给出的条件，按要求跳转所有点后，询问横坐标移动的距离。
主题：先遇到绝对值，先去掉绝对值
对于一个位置I来说，任意j都有：
ji : q[j].h - q[j].x q[i].x
ji: q[j].h q[j].x - q[i].x
因此，只要维持两侧的最大值，就可以决定选择哪个点
主题要求在同一时刻选择最接近I的。 也就是说，左是右，右是左
在这种情况下，可以直接使用段树的推送函数
对于每个点跳跃后的标记，可以将此点的权重设置为-无限
所以，有一点修正区间查询
代码：/* * * keephungryandcalmcoolguang！ **//#pragmagccoptimize(3) includebits/stdc.h ) definedebug ) x ) cout ) x': ) xendl； # include stdio.h # include algorithm # include queue # include string # includeiostreamusingnamespacestd； typedef long ll； typedef unsigned long long ull； typedef pairint，int pp； const ll INF=1e17； const int Maxn=2e7dddppx0； const int maxn=5e5dddppx0； const int mod=1e9 9； const int Mod=1e9 7； ///const double eps=1e-10； inlineboolread(llnum ) {char in； bool IsN=false； in=getchar (； if(in==eof ) return false； 进入！='-
'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}ll n,m,p;ll ma[maxn],mb[maxn];///a - > 左 ,b -> 右int posa[maxn],posb[maxn];void push(int k){ if(ma[k<<1] <= ma[k<<1|1]){ ma[k] = ma[k<<1|1]; posa[k] = posa[k<<1|1]; } else{ ma[k] = ma[k<<1]; posa[k] = posa[k<<1]; } if(mb[k<<1] >= mb[k<<1|1]){ mb[k] = mb[k<<1]; posb[k] = posb[k<<1]; } else{ mb[k] = mb[k<<1|1]; posb[k] = posb[k<<1|1]; }}void build(int k,int l,int r){ ma[k] = mb[k] = -INF; posa[k] = posb[k] = -1; if(l == r) return ; int mid = (l+r)/2; build(k<<1,l,mid); build(k<<1|1,middddppx,r); push(k);}void Modify(int k,int l,int r,int pos,ll w1,ll w2){ if(l == r){ ma[k] = w1; mb[k] = w2; if(w1 == -INF) posa[k] = posb[k] = -1; else posa[k] = posb[k] = l; return; } int mid = (l+r)/2; if(pos <= mid) Modify(k<<1,l,mid,pos,w1,w2); else Modify(k<<1|1,middddppx,r,pos,w1,w2); push(k);}void Query_a(int k,int x,int y,int l,int r,ll &ans,int &pos){ if(x<=l&&y>=r){ if(ma[k] == -INF) return; if(ans<ma[k]){ ans = ma[k]; pos = posa[k]; }else if(ans == ma[k]) pos = max(pos,posa[k]); return; } int mid = (l+r)/2; if(x<=mid) Query_a(k<<1,x,y,l,mid,ans,pos); if(y>mid) Query_a(k<<1|1,x,y,middddppx,r,ans,pos); push(k);}void Query_b(int k,int x,int y,int l,int r,ll &ans,int &pos){ if(x<=l&&y>=r){ if(mb[k] == -INF) return; if(ans<mb[k]){ ans = mb[k]; pos = posb[k]; }else if(ans == mb[k]) if(~posb[k]) pos = min(pos,posb[k]); return; } int mid = (l+r)/2; if(x<=mid) Query_b(k<<1,x,y,l,mid,ans,pos); if(y>mid) Query_b(k<<1|1,x,y,middddppx,r,ans,pos); push(k);}struct node{ ll x,y;}q[maxn];int main(){ read(n);read(m); build(1,1,n); for(int i=1;i<=n;i++){ read(q[i].x); read(q[i].y); Modify(1,1,n,i,q[i].x+q[i].y,q[i].y-q[i].x); } ll ans = 0, s = 1; while(1){ ll tempm = m; Modify(1,1,n,m,-INF,-INF); ll ansa = -INF,ansb = -INF; int apos = -1,bpos = -1; if(m>1) Query_a(1,1,m-1,1,n,ansa,apos); if(m<n) Query_b(1,mdddppx,n,1,n,ansb,bpos); if(apos == -1 && bpos == -1) break; else if(apos == -1 && ~bpos) m = bpos; else if(~apos && bpos == -1) m = apos; else{ if(ansa-q[m].x>ansb+q[m].x) m = apos; else if(ansa-q[m].x<ansb+q[m].x) m = bpos; else{ if(q[m].x-q[apos].x <= q[bpos].x - q[m].x) m = apos; else m = bpos; } } ans += abs(q[m].x-q[tempm].x); } printf("%lldn",ans); return 0;}/**4 31 32 103 114 10**/