【Luogu3113】马拉松赛跑Marathon

来源和评测点

USACO14DEC Gold
Luogu3113

题目

【题目大意】
N个点的路线(1<=N<=100,000),必须按顺序经过。

询问特定的子路线需要多长时间才能跑完,
其中的子路线是从完整路线的检查点中截取的的连续子序列。

牛可能会选择在任何时候跳过一个检查点,但不允许在子路线中跳过第一个或最后一个点

可能修改点的坐标

由于该课程设置在市中心的街道网络中,
两个点之间的距离(x1,y1)和(x2,y2)是由|x1-x2|+|y1-y2|得出的。
【输入格式】
第一行N和Q (1<=Q<=100,000).

下面N行 每个点的坐标(x,y),大小范围是-1000..1000
下面Q行 每行一个操作
“U I X Y” 修改 点I (1<=I<= N) 的坐标为(X, Y).
“Q I J” 询问从I到J的最短距离(可以跳过除起点、终点外的其他点)(I <= J)
【输出格式】
每个Q输出距离值
【输入样例】
5 5
-4 4
-5 -3
-1 5
-3 4
0 5
Q 1 5
U 4 0 1
U 4 -1 1
Q 2 4
Q 1 4
【输出样例】
11
8
8

分析

使用线段树维护两个完全不同的信息。
值1是每个节点到上一个节点的距离
值2是每个节点被忽略后的收益(一般是负数)
维护值1的和、值2的最小值

每次修改影响两个值1,三个值2

信息的维护用线段树达到log,树状数组则比较麻烦

玄学AC之
本来线段树不忽略编号1,wa几个点都是个位数级别差异
后来想着顺便加速(因为编号1从来不用),结果AC
如果有人知道,可以在讨论区评论一下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll myabs(ll x) {return x>0?x:-x;}
ll mymin(ll x,ll y) {return x<y?x:y;}
const int MAXN=110000;
int n;
struct nod
{
int l,r,mid,lc,rc;
ll s,mi;//分别维护值1的和、值2的最小值
}s[MAXN*2];
int ln=0;
int build(int l,int r)
{
int t=++ln;
s[t].l=l;s[t].r=r;s[t].mid=(l+r)>>1;
if(l<r)
{
s[t].lc=build(l,s[t].mid);
s[t].rc=build(s[t].mid+1,r);
}
return t;
}
void change1(int w,int x,ll c)
{
if(s[w].l==s[w].r)
{
s[w].s=c;
return;
}
int lc=s[w].lc,rc=s[w].rc;
if(x<=s[w].mid) change1(lc,x,c);
else change1(rc,x,c);
s[w].s=s[lc].s+s[rc].s;
}
void change2(int w,int x,ll c)
{
if(s[w].l==s[w].r)
{
s[w].mi=c;
return;
}
int lc=s[w].lc,rc=s[w].rc;
if(x<=s[w].mid) change2(lc,x,c);
else change2(rc,x,c);
s[w].mi=mymin(s[lc].mi,s[rc].mi);
}
ll ask1(int w,int l,int r)
{
if(s[w].l==l and s[w].r==r) return s[w].s;
int lc=s[w].lc,rc=s[w].rc;
if(r<=s[w].mid) return ask1(lc,l,r);
if(l>s[w].mid) return ask1(rc,l,r);
return ask1(lc,l,s[w].mid)+ask1(rc,s[w].mid+1,r);
}
ll ask2(int w,int l,int r)
{
if(l>r) return 0;
if(s[w].l==l and s[w].r==r) return s[w].mi;
int lc=s[w].lc,rc=s[w].rc;
if(r<=s[w].mid) return ask2(lc,l,r);
if(l>s[w].mid) return ask2(rc,l,r);
return mymin(ask2(lc,l,s[w].mid),ask2(rc,s[w].mid+1,r));
}
//值1是每个节点到上一个节点的距离
//值2是每个节点被忽略后的收益(一般是负数)
int xx[MAXN],yy[MAXN];
ll get(int x,int sf)//与往前sf个节点的距离
{
return myabs(xx[x]-xx[x-sf])+myabs(yy[x]-yy[x-sf]);
}
ll p[MAXN];//顺便存储值
char ss[10];
int main()
{
int q;scanf("%d%d",&n,&q);
build(1,n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&xx[i],&yy[i]);
if(i==1) continue;
change1(1,i-1,p[i]=get(i,1));
}
for(int i=2;i<=n-1;i++) change2(1,i-1,get(i+1,2)-p[i]-p[i+1]);
while(q--)
{
scanf("%s",ss);
if(ss[0]=='Q')
{
int x,y;scanf("%d%d",&x,&y);
printf("%lld\n",ask1(1,x+1-1,y-1)+ask2(1,x+1-1,y-1-1));
}
else
{
int a;scanf("%d",&a);
scanf("%d%d",&xx[a],&yy[a]);
//修改值1两处
change1(1,a-1,p[a]=get(a,1));
change1(1,a+1-1,p[a+1]=get(a+1,1));
//对应值2三处
change2(1,a-1-1,get(a,2)-p[a-1]-p[a]);
change2(1,a-1,get(a+1,2)-p[a]-p[a+1]);
change2(1,a+1-1,get(a+2,2)-p[a+1]-p[a+2]);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-12/马拉松赛跑Marathon.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!