Good Bye 2014 E. New Year Domino

57 阅读 0 评论 38 点赞

我是靠谱客的博主负责大树，最近开发中收集的这篇文章主要介绍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;
}