rt

线段树

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct node
{
    int x,y;
}a[maxn];
int sum[maxn<<2],mi[maxn<<2]={INT_MAX},qy[maxn],cz[maxn],n,q;
void build(int l,int r,int rt)//板子是正确的
{
    if(l==r)
    {
        sum[rt]=qy[l];
        mi[rt]=cz[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void update(int l,int r,int rt,int i,int j,int k)
{
        // cout<<l<<' '<<r<<" "<<rt<<' '<<"#######"<<k<<endl;
    if(l==r)
    {
        sum[rt]=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(i<=mid)
        update(l,mid,rt<<1,i,j,k);
    if(mid<j)
        update(mid+1,r,rt<<1|1,i,j,k);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    // mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void change(int l,int r,int rt,int i,int j,int k)
{
    if(l==r)
    {
        mi[rt]=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(i<=mid)
        change(l,mid,rt<<1,i,j,k);
    if(mid<j)
        change(mid+1,r,rt<<1|1,i,j,k);
    // sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}

int query(int l,int r,int rt,int i,int j)
{
    // cout<<"********"<<sum[rt]<<endl;
    if(l>=i&&r<=j)
    {
        return sum[rt];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(i<=mid)ans+=query(l,mid,rt<<1,i,j);
    if(mid<j)ans+=query(mid+1,r,rt<<1|1,i,j);
    return ans;
}
int q1(int l,int r,int rt,int i,int j)
{
    if(l>=i&&r<=j)
    {
        return mi[rt];
    }
    int mid=(l+r)>>1;
    int ans=INT_MAX;
    if(i<=mid)ans=min(ans,q1(l,mid,rt<<1,i,j));
    if(mid<j)ans=min(ans,q1(mid+1,r,rt<<1|1,i,j));
    return ans;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        qy[i]=abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y);
        if(i==1)
            qy[i]=0;
        // cout<<qy[i]<<endl;
    }
    for(int i=2;i<n;i++)
    {
        cz[i]=(abs(a[i+1].x+-a[i-1].x)+abs(a[i+1].y-a[i-1].y))-qy[i]-qy[i+1];
        // cout<<"#######"<<cz[i]<<endl;
    }
    build(1,n,1);
    for(int i=1;i<=q;i++)
    {
        char x;
        int l,r,k;
        cin>>x;
        cin>>l>>r;
        if(x=='U')
        {
            cin>>k;
            a[l].x=r;
            a[l].y=k;qy[l]=abs(a[l].x-a[l-1].x)+abs(a[l].y-a[l-1].y);
            update(1,n,1,l,l,qy[l]);qy[l+1]=abs(a[l].x-a[l+1].x)+abs(a[l].y-a[l+1].y);
            update(1,n,1,l+1,l+1,qy[l+1]);
            // cout<<"addasffa"<<endl;
            // cout<<qy[l]<<' '<<qy[l+1]<<endl;
            cz[l-1]=abs(a[l-2].x-a[l].x)+abs(a[l-2].y-a[l].y)-qy[l]-qy[l-1];
            change(1,n,1,l-1,l-1,cz[l-1]);cz[l]=abs(a[l-1].x-a[l+1].x)+abs(a[l-1].y-a[l+1].y)-qy[l]-qy[l+1];
            change(1,n,1,l,l,cz[l]);cz[l]=abs(a[l].x-a[l+2].x)+abs(a[l].y-a[l+2].y)-qy[l+2]-qy[l+1];
            change(1,n,1,l+1,l+1,cz[l]);
        }
        else
        {
            cout<<query(1,n,1,l+1,r)+((l+1<=r-1)?min(q1(1,n,1,l+1,r-1),0):0)<<endl;
        }
    }
    return 0;
}