USACO 2014 December Contest, Gold Problem 2. Marathon

http://www.usaco.org/index.php?page=viewproblem2&cpid=495

一開始也不知道這題是在做什麼

之後想想我們似乎要維護個兩點之間距離 + 跨一點的距離

然後似乎很麻煩

題解也不知道要怎麼寫XD

往上面兩個方向仔細去想即可

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <utility>

#include <cmath>

using namespace std;

typedef long long LL;

const int MAX_N = 100003;

LL pre_seg[400021];

LL two_seg[400021];

LL d[MAX_N];

LL d2[MAX_N];

void Build(int id,int L,int R) {

if (L==R) {

pre_seg[id] = d[L];

return;

}

int mid=(L+R)>>1;

Build(id*2,L,mid);

Build(id*2+1,mid+1,R);

pre_seg[id]=pre_seg[id*2]+pre_seg[id*2+1];

}

void modify(int id,int L,int R,int pos,int val) {

if (L==R) {

pre_seg[id]=val;

return;

}

int mid=(L+R)>>1;

if (pos<=mid) modify(id*2,L,mid,pos,val);

else modify(id*2+1,mid+1,R,pos,val);

pre_seg[id]=pre_seg[id*2]+pre_seg[id*2+1];

}

int query(int id,int L,int R,int l,int r) {

if (L>r || l > R) return 0;

if (l<=L && R<=r) {

return pre_seg[id];

}

int mid=(L+R)>>1;

return query(id*2,L,mid,l,r)+query(id*2+1,mid+1,R,l,r);

}

void Build2(int id,int L,int R) {

if (L==R) {

two_seg[id]=d2[L];

return;

}

int mid=(L+R)>>1;

Build2(id*2,L,mid);

Build2(id*2+1,mid+1,R);

two_seg[id]=max(two_seg[id*2],two_seg[id*2+1]);

}

void modify2(int id,int L,int R,int pos,int val) {

if (L==R) {

two_seg[id]=val;

return;

}

int mid=(L+R)>>1;

if (pos<=mid) modify2(id*2,L,mid,pos,val);

else modify2(id*2+1,mid+1,R,pos,val);

two_seg[id]=max(two_seg[id*2],two_seg[id*2+1]);

}

int query2(int id,int L,int R, int l,int r) {

if (l>r) return 0;

if (L>r || l > R) return 0;

else if (l<=L && R<=r) return two_seg[id];

int mid=(L+R)>>1;

return max(query2(id*2,L,mid,l,r),query2(id*2+1,mid+1,R,l,r));

}

int x[MAX_N];

int y[MAX_N];

int main () {

freopen("marathon.in","r",stdin);

freopen("marathon.out","w",stdout);

int n,q;

while (scanf("%d %d",&n,&q) != EOF) {

for (int i=1;n>=i;i++) {

scanf("%d %d",&x[i],&y[i]);

if (i>1) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

}

if (i>2) {

d2[i-2]=d[i-2]+d[i-1]-abs(x[i]-x[i-2])-abs(y[i]-y[i-2]);

}

}

Build(1,1,n-1);

Build2(1,1,n-2);

for (int i=0;q>i;i++) {

char t;

cin >> t;

if (t=='Q') {

int i,j;

scanf("%d %d",&i,&j);

printf("%d\n",query(1,1,n-1,i,j-1)-query2(1,1,n-2,i,j-2));

}

else {

int i,j,k;

scanf("%d %d %d",&i,&j,&k);

x[i]=j;

y[i]=k;

if (i>1&&n>i) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

modify(1,1,n-1,i,abs(x[i+1]-x[i])+abs(y[i+1]-y[i]));

d[i]=abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);

modify(1,1,n-1,i-1,abs(x[i]-x[i-1])+abs(y[i]-y[i-1]));

}

else if (i==1) {

d[i]=abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);

modify(1,1,n-1,i,abs(x[i+1]-x[i])+abs(y[i+1]-y[i]));

}

else if (i==n) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

modify(1,1,n-1,i-1,abs(x[i]-x[i-1])+abs(y[i]-y[i-1]));

}

if (i>2) d2[i-2]=d[i-2]+d[i-1]-abs(x[i]-x[i-2])-abs(y[i]-y[i-2]);

if (i>1&&i<n) d2[i-1]=d[i-1]+d[i]-abs(x[i+1]-x[i-1])-abs(y[i+1]-y[i-1]);

if (i<n-1)d2[i]=d[i]+d[i+1]-abs(x[i+2]-x[i])-abs(y[i+2]-y[i]);

if (i>2) modify2(1,1,n-2,i-2,d2[i-2]);

if (i>1 && i<n) modify2(1,1,n-2,i-1,d2[i-1]);

if (i<n-1) modify2(1,1,n-2,i,d2[i]);

}

}

// cout<<"---\n";

// for (int x=1;n-1>=x;x++) printf("%d\n",query(1,1,n-1,x,x));

// cout<<"---\n";

// for (int x=1;n-2>=x;x++) printf("%d\n",query2(1,1,n-2,x,x));

// for (int x=1;n-2>=x;x++) cout<<"d2["<<x<<"]="<<d2[x]<<endl;

}

}