「CF91E」Igloo Skyscraper-分块

有 $n$ 个海象（编号为 $1$ 到 $n$ ）参加比赛建造自己的摩天大楼。在 $t=0$ 时，第 $i$ 个海象的摩天大楼的高度为 $a_i$ 。每一时刻，编号为 $i$ 的海象会完成 $b_i$ 层楼的建造。

在奥运会现场报道的记者向活动组织者提出了 $q$ 次询问。每次询问给出三个数字 $l_i$ ，$r_i$ ，$t_i$。活动组织者用数字 $x$ 回答每个查询，$x$ 满足：

数字 $x$ 位于从 $l_i$ 到 $r_i$ 的区间，即 $l_i \leq x \leq r_i$ 。
编号为 $x$ 的海象的摩天大楼在 $t_i$ 时刻拥有编号在 $[l_i,r_i]$ 中所有海象的摩天大楼中的最大高度。

对于每位记者的查询，输出符合上述标准的海象的编号 $x$ 。如果有多个可能的答案，请输出其中任何一个。

链接

Codeforces

题解

可以采用分块+离线的方法过掉这道题。

每个海象的楼的高度都可以视作一条直线 $y = bx + a$ ，那么我们的问题就变成了找这段区间内的直线在 $x = t$ 处的最大值。

我们注意到，如果我们将所有直线排在一起，那么我们在每一时刻最大值一定来自于一堆斜率递增的直线（就是一个下凸包）。

我们要在块内处理出按照时间顺序可能取到的直线。我们先在块内按斜率 $b$ 从小到大排序，然后去掉 $b$ 相同的直线后。我们可以再用 $O(\sqrt{n} \times \sqrt{n})$ 的时间枚举该条直线下一条应该是哪条后面的直线（判断谁的交点最靠左），然后我们就可以得到这 $O(\sqrt{n})$ 条直线的下凸包。

得到这个凸包之后，我们可以计算答案。

我们把询问对时间排序，整块判断能不能更新该点的凸包是不是需要下一条直线，零散直接暴力即可。

时间复杂度： $O((m+n) \sqrt{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
 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
#include <bits/stdc++.h>
#define inf 1e18
#define pii pair<int,int>
using namespace std;

const int MAXN = 110000;
const int MAXQ = 500;

struct Query{
  int l,r,t,id;
  bool operator < (const Query &a)const{
    return t < a.t;
  }
}q[MAXN];

int n,m,Q;
int lb[MAXN],rb[MAXN],bl[MAXN];

struct P{
  int a,b,id;
  bool operator < (const P &x) const{
    if(b != x.b) return b < x.b;
    if(a != x.a) return a > x.a;
    return 0;
  }
}p[MAXN];


double calv(P x,int t){
  return double(x.a) + double(x.b)*t;
}

bool cmp(P x,P y,int t){// 前面优，返回1，后面优秀，返回 0
  if(calv(x,t) != calv(y,t))
    return calv(x,t) > calv(y,t);
  else
    return x.b > y.b;
}

double calj(P x,P y){
  if(x.b == y.b) return inf;
  return double(x.a-y.a)/(y.b-x.b);
}

void init(){
  scanf("%d %d",&n,&m);
  for(int i = 1;i<=n;i++){
    scanf("%d %d",&p[i].a,&p[i].b);
    p[i].id = i;
  }
  for(int i = 1;i<=m;i++){
    scanf("%d %d %d",&q[i].l,&q[i].r,&q[i].t);
    q[i].id = i;
  }
  sort(q+1,q+m+1);
}

vector<P> V[MAXQ];
vector<P> tmp;

void build(){
  Q = sqrt(n);
  for(int i = 1;i<=n;i++){
    bl[i] = (i-1)/Q + 1;
    if(bl[i] != bl[i-1]) lb[bl[i]] = i,rb[bl[i-1]] = i-1;
  }
  rb[bl[n]] = n;
  
  for(int x = 1;x<=bl[n];x++){
    int L = lb[x],R = rb[x];
    for(int i = L;i<=R;i++) V[x].push_back(p[i]);
    sort(V[x].begin(),V[x].end());
    tmp.clear();
    tmp.push_back(V[x][0]);
    for(int i = 1;i < int(V[x].size());i++){
      if(V[x][i].b != V[x][i-1].b) tmp.push_back(V[x][i]);
    }
    V[x].clear();
    V[x].push_back(tmp[0]);
    for(int i = 0;i < int(tmp.size())-1;){
      int t = i;
      for(int j = i+1;j<int(tmp.size());j++)
        if(calj(tmp[i],tmp[j]) < calj(tmp[i],tmp[t]))
          t = j;
      V[x].push_back(tmp[i = t]);
    }
    V[x].push_back(tmp.back());
  }
}

int now[MAXQ];
int ans[MAXN];


void solve(){
  for(int i = 1;i<=m;i++){
    int L = q[i].l,R = q[i].r,t = q[i].t;
    int BL = bl[L],BR = bl[R],tmp = 0;
    if(BL == BR){
      for(int i = L;i<=R;i++) if(cmp(p[i],p[tmp],t)) tmp = i;  
      ans[q[i].id] = tmp;
      continue;
    }
    for(int i = BL+1;i<=BR-1;i++){
      while(now[i]+1 < int(V[i].size()) && calv(V[i][now[i]],t) <= calv(V[i][now[i]+1],t))
        now[i]++;
      if(cmp(V[i][now[i]],p[tmp],t)) tmp = V[i][now[i]].id;
    }
    for(int i = L;i<=rb[BL];i++) if(cmp(p[i],p[tmp],t)) tmp = i;  
    for(int i = lb[BR];i<=R;i++) if(cmp(p[i],p[tmp],t)) tmp = i;   
    ans[q[i].id] = tmp;
  }
  for(int i = 1;i<=m;i++){
    printf("%d\n",ans[i]);
  }
}

int main(){
  init();
  build();
  solve();
  return 0;
}

「CF91E」Igloo Skyscraper-分块

链接

题解

代码

See Also

Comments