Good Bye 2014 E. New Year Domino

80 阅读 0 评论 53 点赞

我是靠谱客的博主负责大树，这篇文章主要介绍Good Bye 2014 E. New Year Domino，现在分享给大家，希望可以做个参考。

Codeforces 500E. New Year Domino

这一题可以用在线做，但是我还没想清楚怎么维护....之前说只能离线做简直是打脸

可以用类似DP的思路，前面k-1个多米诺到第k个的决策最优，再计算从前k个多米诺到第k+1个的决策最优。

我们考虑第k-1个骨牌, 假设 len[k-1]+pos[k-1] < pos[k], 那么就肯定需要把它的高度增加 pos[k] - pos[k-1] - len[k-1]; 反之，就不用管.

接着我们考虑第k-2个个骨牌, 因为我们之前扫描过k-1了,所以现在k-2骨牌倒下后肯定能够碰到第k-1个骨牌,

然后现在有两种方法让k-2碰倒第k个,

一、k-2倒下后直接喷到k, 需要增加的长度是 temp1 = x[k] - x[k-2] - y[k-2]

二、k-2倒下后碰到k-1,k-1再倒下碰到k, 需要增加的长度是 temp2 = x[k] - x[k-1] - y[k-1](因为k-2倒下后肯定能碰到k-1)

于是我们就比较temp1和temp2,选择优的那一个.

因此我们可以从第一个骨牌扫描到最后一个骨牌。

假设现在我们扫描到了第k个骨牌,它前面肯定存在一个区间 (a1, k-1], 这个区间内的每个多米诺的最优情况都是不直接碰到k,而是先碰倒k-1,然后让k-1碰到k;

然后在(a1, k-1]这个区间前面,肯定还有一个区间(a2, a1], 这个区间每个多米诺的最优情况都是不直接碰到k,而是先碰倒a1, 然后a1碰到k;

接下来就会有(a3, a2] .... [1, ak]如此类推

对于(a1, k-1]这个区间内的所有多米诺长度, 都需要增加 max(x[k] - x[k-1] - y[k-1], 0);

对于(a2, a1 ]这个区间内的所有多米诺长度, 都需要增加 max(x[k] - x[a1] - y[a1], 0);

因此可以发现，长度增加是区间更新，所以用线段树维护多米诺骨牌的增加长度。

因为每一次都是相对于现在多米诺的最优增量（也就是最小），所以每次转移到后面的骨牌时，这些增量永远是相对更小的，因此可以不用清空，直接维护。

现在的问题就变成了怎么去找 a0(我们令a0 = k-1), a1, a2, a3 ... ak;

其实可以发现 x[ai] + y[ai] < x[a(i+1)] + y[a(i+1)] 并且 x[ai] + y[ai] >= x[j] + y[j] ( a(i+1)<j<=ai )

然后就可以用一个单调队列来维护ai

复制代码

//
whn6325689
//
Mr.Phoebe
//
http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
#define ls id<<1
#define rs id<<1|1
const int MAXN=200010;
int n,len[MAXN],pos[MAXN],m;
vector<pii> qu[MAXN];
int ans[MAXN];
deque<int> deq;
struct Node
{
int l,r;
int num;
}t[MAXN<<2];
void build(int id,int l,int r)
{
t[id].l=l,t[id].r=r;
t[id].num=0;
if(l==r)
return;
int mid=MID(l,r);
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(int id,int l,int r,int v)
{
if(l>r)
return;
if(t[id].l==l && t[id].r==r)
{
t[id].num+=v;
return;
}
int mid=MID(t[id].l,t[id].r);
if(r<=mid)
update(ls,l,r,v);
else if(l>mid)
update(rs,l,r,v);
else
{
update(ls,l,mid,v);
update(rs,mid+1,r,v);
}
}
void pushdown(int id)
{
t[ls].num+=t[id].num;
t[rs].num+=t[id].num;
t[id].num=0;
}
int query(int id,int x)
{
if(t[id].r==t[id].l)
return t[id].num;
pushdown(id);
int mid=MID(t[id].l,t[id].r);
if(x<=mid)
return query(ls,x);
else
return query(rs,x);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(pos[i]),read(len[i]);
read(m);
for(int i=1,u,v;i<=m;i++)
{
read(u),read(v);
qu[v].pb(mp(u,i));//按照右端点排序也行
}
build(1,1,n);
for(int k=2;k<=n;k++)
{
while(!deq.empty())//单调队列
{
int id=deq.back();
if(len[id]+pos[id] <= len[k-1]+pos[k-1])
deq.pop_back();
else
break;
}
bool flag=0;
deq.push_back(k-1);
while(!deq.empty())
{
int id=deq.back();
if(len[id]+pos[id] >= pos[k])
break;
deq.pop_back();
int last=0,temp=pos[k]-len[id]-pos[id];
if(!deq.empty())
last=deq.back();
update(1,last+1,id,temp);
len[id]+=temp;
flag=1;
}
if(flag)
deq.push_back(k-1);
for(int i=0;i<qu[k].size();i++)
{
int last=qu[k][i].first;
int temp=qu[k][i].second;
ans[temp]=query(1,last);
}
}
for(int i=1;i<=m;i++)
write(ans[i]),putchar('n');
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
//
whn6325689
//
Mr.Phoebe
//
http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
#define ls id<<1
#define rs id<<1|1
const int MAXN=200010;
int n,len[MAXN],pos[MAXN],m;
vector<pii> qu[MAXN];
int ans[MAXN];
deque<int> deq;
struct Node
{
int l,r;
int num;
}t[MAXN<<2];
void build(int id,int l,int r)
{
t[id].l=l,t[id].r=r;
t[id].num=0;
if(l==r)
return;
int mid=MID(l,r);
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(int id,int l,int r,int v)
{
if(l>r)
return;
if(t[id].l==l && t[id].r==r)
{
t[id].num+=v;
return;
}
int mid=MID(t[id].l,t[id].r);
if(r<=mid)
update(ls,l,r,v);
else if(l>mid)
update(rs,l,r,v);
else
{
update(ls,l,mid,v);
update(rs,mid+1,r,v);
}
}
void pushdown(int id)
{
t[ls].num+=t[id].num;
t[rs].num+=t[id].num;
t[id].num=0;
}
int query(int id,int x)
{
if(t[id].r==t[id].l)
return t[id].num;
pushdown(id);
int mid=MID(t[id].l,t[id].r);
if(x<=mid)
return query(ls,x);
else
return query(rs,x);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(pos[i]),read(len[i]);
read(m);
for(int i=1,u,v;i<=m;i++)
{
read(u),read(v);
qu[v].pb(mp(u,i));//按照右端点排序也行
}
build(1,1,n);
for(int k=2;k<=n;k++)
{
while(!deq.empty())//单调队列
{
int id=deq.back();
if(len[id]+pos[id] <= len[k-1]+pos[k-1])
deq.pop_back();
else
break;
}
bool flag=0;
deq.push_back(k-1);
while(!deq.empty())
{
int id=deq.back();
if(len[id]+pos[id] >= pos[k])
break;
deq.pop_back();
int last=0,temp=pos[k]-len[id]-pos[id];
if(!deq.empty())
last=deq.back();
update(1,last+1,id,temp);
len[id]+=temp;
flag=1;
}
if(flag)
deq.push_back(k-1);
for(int i=0;i<qu[k].size();i++)
{
int last=qu[k][i].first;
int temp=qu[k][i].second;
ans[temp]=query(1,last);
}
}
for(int i=1;i<=m;i++)
write(ans[i]),putchar('n');
return 0;
}