New Year Domino-cf - 500E（线段树+离线）

110 阅读 0 评论 73 点赞

我是靠谱客的博主时尚皮皮虾，这篇文章主要介绍New Year Domino-cf - 500E（线段树+离线），现在分享给大家，希望可以做个参考。

题目：https://codeforces.com/problemset/problem/500/E

题意：

多米诺骨牌从1~n，知其所在坐标位置和牌的高度，要求让查询的一段连续位置的骨牌按次序倒下需要增加的长度

题解

第一次只考虑到了两个相连的骨牌前一个对后一个有影响，忽略了前面足够高的骨牌可能会对后面多个位置的骨牌的影响。

错误代码

复制代码

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
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define M_PI 3.14159265358979323846
ll p[200005],l[200005],a[200005];
struct node{
int l,r;
ll w;
}t[800005];
void build(int k,int l,int r)
{
t[k].l=l;
t[k].r=r;
t[k].w=0;
if(l==r)
{
t[k].w=a[l];
return;
}
int mid=(l+r)/2;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
t[k].w=t[2*k].w+t[2*k+1].w;
}
ll query(int k,int x,int y)
{
ll ans=0;
if(x<=t[k].l&&y>=t[k].r)
return t[k].w;
int mid=(t[k].l+t[k].r)/2;
if(x<=mid) ans+=query(2*k,x,mid);
if(y>mid) ans+=query(2*k+1,mid+1,y);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i]>>l[i];
a[1]=0;
for(int i=2;i<=n;i++)
{
if(p[i]-p[i-1]<=l[i-1]) a[i]=0;
else a[i]=p[i]-p[i-1]-l[i-1];
}
build(1,1,n);
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
cout<<query(1,x+1,y)<<endl;
}
return 0;
}

研究了其他人的题解之后，发现可以离线线段树查询一段区间内未被覆盖的长度。从查询的区间左端点较为靠后的区间开始往前查询，每次查询骨牌从后往前排列到该区间的左端点，然后再查询，这样就不会受到前面长骨牌的影响。

复制代码

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define M_PI 3.14159265358979323846
ll l[200005],r[200005],a[400005];
struct q{
int s,e,id;
ll ans;
}qu[200005];
struct node{
int lazy;
ll w;
}t[1600005];
int cmp1(q x,q y)
{
if(x.s!=y.s) return x.s>y.s;
else return x.e>y.e;
}
int cmp2(q x,q y)
{
return x.id<y.id;
}
void push_down(int k,int l,int r)
{
if(t[k].lazy)
{
int mid=(l+r)/2;
t[2*k].w=a[mid+1]-a[l];
t[2*k+1].w=a[r+1]-a[mid+1];
t[k].lazy=0;
t[2*k].lazy=t[2*k+1].lazy=1;
}
}
void update(int k,int l,int r,int L,int R)
{
if(l<=L&&r>=R)
{
t[k].lazy=1;
t[k].w=a[R+1]-a[L];
return;
}
push_down(k,L,R);
int mid=(L+R)/2;
if(l<=mid) update(2*k,l,r,L,mid);
if(r>mid) update(2*k+1,l,r,mid+1,R);
t[k].w=t[2*k].w+t[2*k+1].w;
}
ll query(int k,int x,int y,int L,int R)
{
ll ans=0;
if(x<=L&&y>=R)
{
return t[k].w;
}
push_down(k,L,R);
int mid=(L+R)/2;
if(x<=mid) ans+=query(2*k,x,y,L,mid);
if(y>mid) ans+=query(2*k+1,x,y,mid+1,R);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
int p,h;
int an=0;
for(int i=1;i<=n;i++)
{
cin>>p>>h;
l[i]=p;
r[i]=p+h;
a[++an]=p;
a[++an]=p+h;
}
sort(a+1,a+an+1);
an=unique(a+1,a+an+1)-a-1;
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>qu[i].s>>qu[i].e;
qu[i].id=i;
}
sort(qu+1,qu+q+1,cmp1);//按照查询的左端点从大到小进行排列
int nx=n;
for(int i=1;i<=q;i++)
{
while(nx>=qu[i].s)//每次都更新到要查询的区间的左端点，这样每次查询不会受到前面的骨牌的影响
{
int L=lower_bound(a+1,a+an+1,l[nx])-a;
int R=lower_bound(a+1,a+an+1,r[nx])-a-1;
//cout<<L<<' '<<R<<endl;
update(1,L,R,1,an-1);
nx--;
}
int x=qu[i].s,y=qu[i].e;
int L=lower_bound(a+1,a+an+1,l[x])-a;
int R=lower_bound(a+1,a+an+1,l[y])-a-1;
//cout<<x<<" "<<y<<' '<<L<<' '<<R<<endl;
qu[i].ans=l[y]-l[x]-query(1,L,R,1,an-1);
}
sort(qu+1,qu+q+1,cmp2);
for(int i=1;i<=q;i++)
cout<<qu[i].ans<<endl;
return 0;
}

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
118
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#define M_PI 3.14159265358979323846
ll l[200005],r[200005],a[400005];
struct q{
int s,e,id;
ll ans;
}qu[200005];
struct node{
int lazy;
ll w;
}t[1600005];
int cmp1(q x,q y)
{
if(x.s!=y.s) return x.s>y.s;
else return x.e>y.e;
}
int cmp2(q x,q y)
{
return x.id<y.id;
}
void push_down(int k,int l,int r)
{
if(t[k].lazy)
{
int mid=(l+r)/2;
t[2*k].w=a[mid+1]-a[l];
t[2*k+1].w=a[r+1]-a[mid+1];
t[k].lazy=0;
t[2*k].lazy=t[2*k+1].lazy=1;
}
}
void update(int k,int l,int r,int L,int R)
{
if(l<=L&&r>=R)
{
t[k].lazy=1;
t[k].w=a[R+1]-a[L];
return;
}
push_down(k,L,R);
int mid=(L+R)/2;
if(l<=mid) update(2*k,l,r,L,mid);
if(r>mid) update(2*k+1,l,r,mid+1,R);
t[k].w=t[2*k].w+t[2*k+1].w;
}
ll query(int k,int x,int y,int L,int R)
{
ll ans=0;
if(x<=L&&y>=R)
{
return t[k].w;
}
push_down(k,L,R);
int mid=(L+R)/2;
if(x<=mid) ans+=query(2*k,x,y,L,mid);
if(y>mid) ans+=query(2*k+1,x,y,mid+1,R);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
int p,h;
int an=0;
for(int i=1;i<=n;i++)
{
cin>>p>>h;
l[i]=p;
r[i]=p+h;
a[++an]=p;
a[++an]=p+h;
}
sort(a+1,a+an+1);
an=unique(a+1,a+an+1)-a-1;
int q;
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>qu[i].s>>qu[i].e;
qu[i].id=i;
}
sort(qu+1,qu+q+1,cmp1);//按照查询的左端点从大到小进行排列
int nx=n;
for(int i=1;i<=q;i++)
{
while(nx>=qu[i].s)//每次都更新到要查询的区间的左端点，这样每次查询不会受到前面的骨牌的影响
{
int L=lower_bound(a+1,a+an+1,l[nx])-a;
int R=lower_bound(a+1,a+an+1,r[nx])-a-1;
//cout<<L<<' '<<R<<endl;
update(1,L,R,1,an-1);
nx--;
}
int x=qu[i].s,y=qu[i].e;
int L=lower_bound(a+1,a+an+1,l[x])-a;
int R=lower_bound(a+1,a+an+1,l[y])-a-1;
//cout<<x<<" "<<y<<' '<<L<<' '<<R<<endl;
qu[i].ans=l[y]-l[x]-query(1,L,R,1,an-1);
}
sort(qu+1,qu+q+1,cmp2);
for(int i=1;i<=q;i++)
cout<<qu[i].ans<<endl;
return 0;
}