Atcoder abc266

發表於 更新於 分類於 ， Disqus： 文章字數： 815 所需閱讀時間 ≈ 3 分鐘
Ex(树状数组,二维偏序)

https://atcoder.jp/contests/abc266/tasks

Ex - Snuke Panic (2D)

N个点会出现, 第i个,在ti时刻出现在(xi,yi), 大小为ai

Takahashi 0时刻在 (0,0)

一单位时间

方案1: 可以x 正向/负向移动1

方案2: y正向移动1

方案3: 不移动

恰好在ti时刻在xi,yi则可获得ai

求可获得的ai的总和的最大值

范围

n 1e5

ti 1e9

xi,yi [0,1e9]

ai [1,1e9]

5s 1024mb

我的思路

不妨把点按照时间ti排序

dp[i] = 要获得i, 前ti能得到的最大值, 显然有局部性,

dp[i] = a[i] + max(dp[j]), yj<=yi, abs(xi-xj)+(yi-yj) <= ti-tj

对限制进行处理

abs(xi-xj)+(yi-yj) <= ti-tj 去掉abs

xi-xj+(yi-yj) <= ti-tj 且 xj-xi+(yi-yj) <= ti-tj

分离i,j

ti-xi-yi >= tj-xj-yj 且 ti+xi-yi >= tj+xj-yj

也就是 (yi,ti-xi-yi,ti+xi-yi) 三维偏序中 最大的dp[j]

然而并不会去做三维偏序的

甚至二维偏序也不太会写

题解

一样的也是三维偏序

但实际上这里并不需要t !!!

因为如果无法达到, 则直接忽略

而 i -> j 可达 等价于 3维偏序的满足, 已经说明了 t[i]< t[j], !!!

所以干掉t以后, 就可以按y排序(另外两个也行), 反正其中一个排序,剩下就是二维偏序了

代码

https://atcoder.jp/contests/abc266/submissions/35639063

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;}

//prefix max
struct BIT{
  int n;
  unordered_map<int,ll>data;
  BIT():n(0){};
  BIT(int N):n(N){};
  void set(int i,ll val){ // i \in [0,n)
    for(i++;i<=n;i+=i&-i)data[i-1]=max(data[i-1],val);
  }
  ll prod(int i){
    ll ans=0;
    for(;i;i-=i&-i)ans=max(ans,data[i-1]);
    return ans;
  }
};

struct BIT2D{
  int h,w;
  vector<BIT>data;
  BIT2D(int H,int W):h(H),w(W),data(h,BIT(w)){};
  void set(int i,int y,ll val){ // i \in [0,n)
    for(i++;i<=h;i+=i&-i) data[i-1].set(y,val);
  }
  ll prod(int i,int j){ // < i, < j
    ll ans=0;
    for(;i;i-=i&-i)ans=max(ans,data[i-1].prod(j));
    return ans;
  }
};

int main(){
  int n=read();
  vector<array<int,4>>data; // y,t-x-y,t+x-y,a
  vector<int>P,Q;
  rep(i,0,n){
    int t=read();
    int x=read();
    int y=read();
    int a=read();
    if(t>=abs(x)+y){// 可达的
      data.push_back({y,t-x-y,t+x-y,a});
      P.push_back(t-x-y);
      Q.push_back(t+x-y);
    }
  }
  sort(data.begin(),data.end()); // 按y排序

  // 离散化
  P.push_back(0);
  sort(P.begin(),P.end());
  P.erase(unique(P.begin(),P.end()),P.end());

  Q.push_back(0);
  sort(Q.begin(),Q.end());
  Q.erase(unique(Q.begin(),Q.end()),Q.end());

  BIT2D bit2d(P.size(),Q.size());
  auto fp=[&](int x){return lower_bound(P.begin(),P.end(),x)-P.begin();};
  auto fq=[&](int y){return lower_bound(Q.begin(),Q.end(),y)-Q.begin();};
  ll ans=0;
  for(auto query:data){
    auto[y,p,q,val]=query;
    p=fp(p);
    q=fq(q);
    ll ret=bit2d.prod(p+1,q+1);
    ans=max(ans,ret+val);
    bit2d.set(p,q,ret+val);
  }
  printf("%lld\n",ans);
}

总结

现场做了, 推出了Ex是个三维偏序,但不会写..

Ex

一个是没发现这里 的t可以干掉, 这样3维可以控制顺序变成二维!!!

有道理啊, 学会了2d fenwick

因为相当于 (i,j) 只会写入 log(H)log(W)个位置, 那么n个点, 就只有 n log^2

所以即使是3维也可以搞

只需要内部用unordered_map 而不是vector,就可以解决空间了

参考

官方题解