记录编号	163503	评测结果	AAAAAAAAAA
题目名称	马拉松	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	1.255 s
提交时间	2015-05-24 16:38:41	内存使用	4.87 MiB

#include<cstdio>

using namespace std;

int n,m,dis[100010],sl[100010],tr[400001],dtr[400001];

int MAX(int x,int y)
{
    if(x>y)
        return x;
    return y;
}

int abs(int x)
{
    if(x>0)
        return x;
    return -x;
}

void build(int l,int r,int n)
{
    if(l==r)
    {
        tr[n]=sl[l];
        dtr[n]=dis[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,n<<1);
    build(m+1,r,n<<1|1);
    tr[n]=MAX(tr[n<<1],tr[n<<1|1]);
    dtr[n]=dtr[n<<1]+dtr[n<<1|1];
}

struct at{
    int x,y;
}node[100001];

struct ai{
    int dis,sl;
};

char cmd[5];

void change(int pos,int s,int d,int l,int r,int n)
{
    if(l==r)
    {
		//printf("%d %d\n",tr[n],sl[l]);
        tr[n]=sl[l];
        dtr[n]=dis[l];
        return;
    }
    int m=(l+r)>>1;
    if(pos<=m)
        change(pos,s,d,l,m,n<<1);
    else
        change(pos,s,d,m+1,r,n<<1|1);
    tr[n]=MAX(tr[n<<1],tr[n<<1|1]);
    dtr[n]=dtr[n<<1]+dtr[n<<1|1];
}

ai ask(int al,int ar,int l,int r,int n)
{
    ai ma;
	ma.dis=0;
    ma.sl=0;
    if(al<=l&&r<=ar)
    {

        ma.sl=tr[n];
        ma.dis=dtr[n];
		//printf("%d\n",ma.dis);
        return ma;
    }
    int m=(l+r)>>1;
    if(m>=al)
    {
        ma=ask(al,ar,l,m,n<<1);
    }
    if(ar>m)
    {
        ai temp=ask(al,ar,m+1,r,n<<1|1);
        ma.dis+=temp.dis;
        ma.sl=MAX(ma.sl,temp.sl);
    }
    return ma;
}
void getd(int i)
{
    dis[i]=abs(node[i].x-node[i-1].x)+abs(node[i-1].y-node[i].y);
    return;
}
void getsl(int i)
{
	sl[i]=dis[i]+dis[i+1]-abs(node[i+1].x-node[i-1].x)-abs(node[i-1].y-node[i+1].y);
	return;
}
int main()
{
	freopen("marathona.in","r",stdin);
	freopen("marathona.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&node[i].x,&node[i].y);
        dis[i]=abs(node[i].x-node[i-1].x)+abs(node[i].y-node[i-1].y);
    }
    for(int i=2;i<n;i++)
    {
        sl[i]=dis[i]+dis[i+1]-abs(node[i+1].x-node[i-1].x)-abs(node[i+1].y-node[i-1].y);
    }
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",cmd);
        int x,y,w;
        if(cmd[0]=='Q')
        {
            scanf("%d%d",&x,&y);
            ai ax=ask(x+1,y-1,1,n,1);
            printf("%d\n",ax.dis-ax.sl+dis[y]);
        }
        else
        {
            scanf("%d%d%d",&w,&x,&y);
            node[w].x=x;
            node[w].y=y;
            getd(w);
            getd(w+1);
            getd(w-1);
            getsl(w);
            getsl(w+1);
            getsl(w-1);
            change(w,sl[w],dis[w],1,n,1);
            change(w-1,sl[w-1],dis[w-1],1,n,1);
            change(w+1,sl[w+1],dis[w+1],1,n,1);
        }
    }
}