codeforces 500E New Year Domino(线段树预处理+倍增）codeforces 500E New Year Domino(线段树预处理+倍增）

98 阅读 0 评论 65 点赞

我是靠谱客的博主悦耳纸鹤，这篇文章主要介绍codeforces 500E New Year Domino(线段树预处理+倍增）codeforces 500E New Year Domino(线段树预处理+倍增），现在分享给大家，希望可以做个参考。

codeforces 500E New Year Domino(线段树预处理+倍增）

【题目链接】

解题思路

先用线段树预处理能达到的最远长度，就是从后往前，对每个点，二分找到它能到的最远的木棒，找到这其中的最远距离，更新。
对每一个点，向推倒它之后第一个不能被波及到的木棒连一条边，记录一个花费。
用dp[i][j]表示第i个点走过2的j次方条边后到达的点，同时记录花费。

复制代码

1
2
3
 dp[i][j]=dp[dp[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]+cost[dp[i][j-1]][j-1];

之后倍增，j从最大开始（比如这个题我设了个29），只有当dp[i][j]<终点时才跳（因为在dp[i][j]前的都是一定要被跳的），跳完以后特判试是刚好到不了终点还有跳一条边还是已经到了。

AC代码

复制代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n;
struct node
{
int x,h;
}a[maxn];
bool cmp(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
else a.h<b.h;
}
int loc[maxn],b[maxn];
int tree[maxn<<2];
int cnt;///建新树前置0
void build(int i,int ll,int rr)
{
if(ll==rr)
{
tree[i]=b[++cnt];
}
else
{
int mid=(ll+rr)/2;
build(i*2,ll,mid);
build(i*2+1,mid+1,rr);
tree[i]=max(tree[i*2],tree[i*2+1]);
}
}
void update(int i,int x,int v,int ll,int rr)
{
if(ll==rr)
{
tree[i]=v;
return;
}
int mid=(ll+rr)/2;
if(x<=mid)
{
update(i*2,x,v,ll,mid);
}
else
{
update(i*2+1,x,v,mid+1,rr);
}
tree[i]=max(tree[i*2],tree[i*2+1]);
}
int quest(int i,int l,int r,int ll,int rr)
{
//printf("%d (%d,%d) (%d,%d)n",i,l,r,ll,rr);
if(ll==l&&rr==r) return tree[i];
int
mid=(ll+rr)/2;
if(r<=mid)
{
return quest(i*2,l,r,ll,mid);
}
else if(l>mid)
{
return quest(i*2+1,l,r,mid+1,rr);
}
else
{
return max(quest(i*2,l,mid,ll,mid),quest(i*2+1,mid+1,r,mid+1,rr));
}
}
int dp[maxn][30],cost[maxn][30];
int main()
{
int i,j,k,x,y,l,r,len,q,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].h);
}
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
b[i]=a[i].x+a[i].h;
loc[i]=a[i].x;
}
cnt=0;
build(1,1,n);
for(i=n;i>0;i--)
{
b[i]=quest(1,i,upper_bound(loc+i,loc+1+n,b[i])-1-loc,1,n);
update(1,i,b[i],1,n);
}
for(i=1;i<=n;i++)
{
y=upper_bound(loc+i,loc+1+n,b[i])-loc;
if(y>n)
{
y=n;
len=0;
}
else len=a[y].x-b[i];
dp[i][0]=y;
cost[i][0]=len;
}
for(j=1;j<30;j++)
{
for(i=1;i<=n;i++)
{
dp[i][j]=dp[dp[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]+cost[dp[i][j-1]][j-1];
}
}
//
for(i=1;i<=n;i++)
//
{
//
for(j=0;j<30;j++)
//
{
//
printf("dp[%d][%d]=%d cost[%d][%d]=%dn",i,j,dp[i][j],i,j,cost[i][j]);
//
}
//
}
scanf("%d",&q);
while(q--)
{
ans=0;
scanf("%d%d",&l,&r);
i=l;
for(j=29;j>=0;j--)
{
if(dp[i][j]<r)
{
//printf("cost[%d][%d]=%dn",i,j,cost[i][j]);
ans+=cost[i][j];
i=dp[i][j];
}
}
if(dp[i][0]<=r) ans+=cost[i][0];
printf("%dn",ans);
}
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n;
struct node
{
int x,h;
}a[maxn];
bool cmp(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
else a.h<b.h;
}
int loc[maxn],b[maxn];
int tree[maxn<<2];
int cnt;///建新树前置0
void build(int i,int ll,int rr)
{
if(ll==rr)
{
tree[i]=b[++cnt];
}
else
{
int mid=(ll+rr)/2;
build(i*2,ll,mid);
build(i*2+1,mid+1,rr);
tree[i]=max(tree[i*2],tree[i*2+1]);
}
}
void update(int i,int x,int v,int ll,int rr)
{
if(ll==rr)
{
tree[i]=v;
return;
}
int mid=(ll+rr)/2;
if(x<=mid)
{
update(i*2,x,v,ll,mid);
}
else
{
update(i*2+1,x,v,mid+1,rr);
}
tree[i]=max(tree[i*2],tree[i*2+1]);
}
int quest(int i,int l,int r,int ll,int rr)
{
//printf("%d (%d,%d) (%d,%d)n",i,l,r,ll,rr);
if(ll==l&&rr==r) return tree[i];
int
mid=(ll+rr)/2;
if(r<=mid)
{
return quest(i*2,l,r,ll,mid);
}
else if(l>mid)
{
return quest(i*2+1,l,r,mid+1,rr);
}
else
{
return max(quest(i*2,l,mid,ll,mid),quest(i*2+1,mid+1,r,mid+1,rr));
}
}
int dp[maxn][30],cost[maxn][30];
int main()
{
int i,j,k,x,y,l,r,len,q,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].h);
}
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
b[i]=a[i].x+a[i].h;
loc[i]=a[i].x;
}
cnt=0;
build(1,1,n);
for(i=n;i>0;i--)
{
b[i]=quest(1,i,upper_bound(loc+i,loc+1+n,b[i])-1-loc,1,n);
update(1,i,b[i],1,n);
}
for(i=1;i<=n;i++)
{
y=upper_bound(loc+i,loc+1+n,b[i])-loc;
if(y>n)
{
y=n;
len=0;
}
else len=a[y].x-b[i];
dp[i][0]=y;
cost[i][0]=len;
}
for(j=1;j<30;j++)
{
for(i=1;i<=n;i++)
{
dp[i][j]=dp[dp[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]+cost[dp[i][j-1]][j-1];
}
}
//
for(i=1;i<=n;i++)
//
{
//
for(j=0;j<30;j++)
//
{
//
printf("dp[%d][%d]=%d cost[%d][%d]=%dn",i,j,dp[i][j],i,j,cost[i][j]);
//
}
//
}
scanf("%d",&q);
while(q--)
{
ans=0;
scanf("%d%d",&l,&r);
i=l;
for(j=29;j>=0;j--)
{
if(dp[i][j]<r)
{
//printf("cost[%d][%d]=%dn",i,j,cost[i][j]);
ans+=cost[i][j];
i=dp[i][j];
}
}
if(dp[i][0]<=r) ans+=cost[i][0];
printf("%dn",ans);
}
return 0;
}