Atcoder abc287

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
G(离线,线段树)Ex(Floyd-Warshall,bitset)

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

G - Balance Update Query

n种卡，每种无限多，初始每种 单价ai,最多取bi张

q个询问，每次三种可能操作

  1. 修改一个的上限bi

  2. 修改一个的单价ai

  3. 问 恰好取x张的最大价值

范围

n,q 2e5

ai [0,1e9]

bi [0,1e4]

2s

1024mb

我的想法

如果固定，贪心从单价大到小的去取

对单价排序 做根号分治

让每个块的个数 保持在sqrt(n)个

这样每次修改操作就是 最多改变 sqrt(n)个块， 每个块内部就是 log(sqrt(n)) 的操作次数 时间复杂度 O(q sqrt(n) log(sqrt(n)))

而查询， 因为可以做块的个数和与代价和记录， 所以 暴力找在哪个块，再在块里暴力搜，O(q (sqrt(n)+log(sqrt(n))))

2s 还是会tle的

200000*math.sqrt(200000)*math.log(math.sqrt(200000))/math.log(2) = 91203683.14743526

它的确也tle了

https://atcoder.jp/contests/abc287/submissions/38429726

21AC + 19TLE

题解

离线 一下，其实知道所有会出现的 ai,bi

直接把价格ai 离散化掉, 就是个无脑 线段树上二分了

代码

segtree(2396Byte,256ms,31112KB)

https://atcoder.jp/contests/abc287/submissions/38669755

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
#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 SEG_ROOT 0,0,N
#define SEG_L (o*2+1)
#define SEG_R (o*2+2)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

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

int score[200010];
int quota[200010];
vector<array<int,3> >Q;
vector<ll> xval;
ll init[400010]; // {quota sum}
array<ll,2> seg[1600010]; // {quota sum, score sum}

array<ll,2> up(array<ll,2> l,array<ll,2> r){ return {l[0]+r[0],l[1]+r[1]}; }

void build(int o,int l,int r){
  if(l+1==r){
    seg[o] = {init[l],init[l]*xval[l]};
    return ;
  }
  build(SEG_L_CHILD);
  build(SEG_R_CHILD);
  seg[o] = up(seg[SEG_L],seg[SEG_R]);
}

void add(int o,int l,int r,int i,int inc){
  if(l+1==r){
    seg[o][0] += inc;
    seg[o][1] += inc*xval[l];
    return ;
  }
  if(i < mid) add(SEG_L_CHILD,i,inc);
  else        add(SEG_R_CHILD,i,inc);
  seg[o] = up(seg[SEG_L],seg[SEG_R]);
}

ll query(int o,int l,int r,int & cnt){
  if(seg[o][0] <= cnt){
    cnt -= seg[o][0];
    return seg[o][1];
  }
  ll ret=0;
  if(l+1==r){ // seg[o][0] > cnt
    ret = cnt*xval[l];
    cnt -= cnt;
    return ret;
  }
  ret += query(SEG_R_CHILD,cnt);
  if(cnt) ret+= query(SEG_L_CHILD,cnt);
  return ret;
}

int main(){
  int n=read();
  rep(i,0,n) {
    score[i]=read(); // score
    quota[i]=read(); // quota
    xval.push_back(score[i]);
  }
  int q=read();
  rep(i,0,q){
    int op=read();
    int x=read();
    if(op==1){
      int y=read();
      xval.push_back(y);
      Q.push_back({op,x-1,y});
    }else if(op==2){
      int y=read();
      Q.push_back({op,x-1,y});
    }else if(op==3){
      Q.push_back({op,x,0});
    }
  }
  sort(begin(xval),end(xval));
  xval.erase(unique(begin(xval),end(xval)),end(xval));
  auto idx=[&](int x){return lower_bound(begin(xval),end(xval),x)-begin(xval);};
  rep(i,0,n) init[idx(score[i])] += quota[i];
  int N = xval.size();
  build(SEG_ROOT);
  for(auto [op,x,y]:Q){
    if(op==1){
      add(SEG_ROOT,idx(score[x]),-quota[x]);
      score[x] = y;
      add(SEG_ROOT,idx(score[x]),quota[x]);
    }else if(op==2){
      int diff = y-quota[x];
      add(SEG_ROOT,idx(score[x]),diff);
      quota[x] = y;
    }else if(op==3){
      printf("%lld\n",(seg[0][0] < x)?-1:query(SEG_ROOT,x));
    }
  }
  return 0;
}

Fenwick(2198 Byte, 214ms, 25816KB)

https://atcoder.jp/contests/abc287/submissions/38686072

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

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

int score[200010];
int quota[200010];
vector<array<int,3> >Q;
vector<ll> xval;

array<ll,2> operator+(array<ll,2>l,array<ll,2>r){ return {l[0]+r[0],l[1]+r[1]}; }
array<ll,2> operator-(array<ll,2>l,array<ll,2>r){ return {l[0]-r[0],l[1]-r[1]}; }

class Fenwick{
public:
  vector<array<ll,2> > qs; // quota, score sum
  vector<array<ll,2> > point; // quota, score sum
  Fenwick(int sz){ // 0-index
    qs.resize(sz);
    point.resize(sz);
  }
  void add(int x,int inc){
    array<ll,2> diff = {inc, inc*xval[x]};
    point[x] = point[x] + diff;
    for(x+=1;x<=(int)qs.size();x+=(x&-x)){
      qs[x-1] = qs[x-1] + diff;
    }
  }

  ll query(int cnt){
    int x = qs.size();
    ll res = 0;
    for(;x;){
      if(qs[x-1][0] <= cnt){
        cnt -= qs[x-1][0];
        res += qs[x-1][1];
        x-=(x&-x);
      }else{
        if(point[x-1][0] <= cnt){
          cnt -= point[x-1][0];
          res += point[x-1][1];
          x-=1;
        }else{
          return res += cnt*xval[x-1];
        }
      }
    }
    return cnt==0?res:-1;
  }
};

int main(){
  int n=read();
  rep(i,0,n) {
    score[i]=read(); // score
    quota[i]=read(); // quota
    xval.push_back(score[i]);
  }
  int q=read();
  rep(i,0,q){
    int op=read();
    int x=read();
    if(op==1){
      int y=read();
      xval.push_back(y);
      Q.push_back({op,x-1,y});
    }else if(op==2){
      int y=read();
      Q.push_back({op,x-1,y});
    }else if(op==3){
      Q.push_back({op,x,0});
    }
  }
  sort(begin(xval),end(xval));
  xval.erase(unique(begin(xval),end(xval)),end(xval));
  auto idx=[&](int x){return lower_bound(begin(xval),end(xval),x)-begin(xval);};
  Fenwick fw(xval.size());
  rep(i,0,n) fw.add(idx(score[i]), quota[i]);
  for(auto [op,x,y]:Q){
    if(op==1){
      fw.add(idx(score[x]),-quota[x]);
      score[x] = y;
      fw.add(idx(score[x]),quota[x]);
    }else if(op==2){
      fw.add(idx(score[x]),y-quota[x]);
      quota[x] = y;
    }else if(op==3){
      printf("%lld\n", fw.query(x));
    }
  }
  return 0;
}

Ex - Directed Graph and Query

n点,m边 有向图

path 的cost 定义，最大index的点的index

Q个询问, 每次询问si -> ti 最小cost的path的cost,或报告不存在

范围

n 2000

m <= n(n-1)

q 1e4

4.5s

1024mb

我的思路

n不太大，q也很小

直接暴力 枚举源？ 似乎是O(n m) => O(n^3)

既然是最小的

那么考虑点的id从小到大

所以直接维护每个点可达的点的集合 和 来源点的集合

如果没有环的话，两两之间最多一次

有环的话，(a,b,c) -> (a,d,e) ?

因为两两之间 其实也就是N^2,

问题就是如何得到两两之间的答案

题解

Floyd-Warshall 暴力+bitset

O(N^3+NQ)

bitset可以加速 1/64

Floyd-Warshall

例如 1->2->3->1

在处理3之前， 3能到[1,2], 但是2不能到1, 虽然 2能到3， 但是從統計上， 每次新增的是 max(首，尾，i), 所以有 只能经过更大的到达的如果有连接 也是初始连接，不会有中间的连接

到3的时候 所有的也只是

1
2
3
4
rep(i,1,n+1){
  rep(j,1,n+1) if(d[j][i]) d[j]|=d[i]; // floyd-warshall
  rep(j,0,q) if(ans[j]==-1 and d[s[j]][t[j]]) ans[j]=max({s[j],t[j],i}); // 前面不可达， 增加了i可达
}

代码

https://atcoder.jp/contests/abc287/submissions/38673314

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
int s[10010];
int t[10010];
int ans[10010];
bitset<2010> d[2010]; // d[i] 能到的点
int main() {
  int n=read();
  int m=read();
  rep(i,0,m){
    int u=read();
    int v=read();
    d[u][v]=1;
  }
  int q=read();
  rep(i,0,q){
    s[i]=read();
    t[i]=read();
    ans[i]=-1;
  }
  rep(i,1,n+1){
    rep(j,1,n+1) if(d[j][i]) d[j]|=d[i];
    rep(j,0,q) if(ans[j]==-1 and d[s[j]][t[j]]) ans[j]=max({s[j],t[j],i});
  }
  rep(i,0,q) printf("%d\n",ans[i]);
  return 0;
}

总结

现场打的，卡了前面的题，

G

想了半天分块， 但似乎是 n sqrt(n) log(n) 差亿点能过的那种

实际上就是离线掉,然后无脑线段树了

Ex

bitset不熟 + Floyd-Warshall 不熟

以及我还以为有什么能做到N^2的科技

参考

官方题解