atcoder abc 382 lazy_tag线段树

A Daily Cookie

代码：
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n, d;
    cin >> n >> d;
    string s;
    cin >> s;
    int cnt = d;
    for(auto t: s) if(t == '.') cnt ++;
    cout << min(n, cnt);
}

B Daily Cookie2

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n, d;
    cin >> n >> d;
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    for(int i = 0; i < n; i ++ ) {
      if(d && s[i] == '@') {
        d --;
        s[i] = '.';
      }
    }
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}

C Kaiten Sushi 

问题：

思路：容易得到：寿司会被第一个美食等级小于其本身美味程度的人吃掉，并且，如果后面人的美食等级如果大于前面那个人的美食等级，那么后面那个人将永远不会吃到寿司，因为他能吃的寿司，他前面的一定可以吃，并且他前面的人有对寿司的优先选择权。因此这道题就变成了先以第一个人为开头，维护出一个美食等级递减的序列，并对每一块寿司在这个序列上二分查找第一个小于其本身美味程度的人

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n + 1), b(m + 1);
  for(int i = 1; i <= n; i ++ ) cin >> a[i];
  vector<pair<int, int>> c;
  c.push_back({a[1], 1});
  for(int i = 1; i <= n; i ++ ) if(a[i] < c.back().first) c.push_back({a[i], i});
  int tot = c.size() - 1;
  for(int i = 1; i <= m; i ++ ) cin >> b[i];
  for(int i = 1; i <= m; i ++ ) {
    int l = 0, r = tot;
    while(l < r) {
      int mid = l + r >> 1;
      if(c[mid].first <= b[i]) r = mid;
      else l = mid + 1;
    }
    if(c[l].first <= b[i]) cout << c[l].second << "\n";
    else cout << "-1\n";
  }
  return 0;
}

D keep distance

思路：对于每一个Ai，都有一个数据范围，并且这个范围的差值不超过10，因此考虑爆搜 ＋ 剪枝

另外，取两种极端情况就可以得到这个范围 

区间左端点： 1， 1 + 10，1 + 10 + 10， 1 + (n - 1) * 10 

区间右端点  m - (n - 1) * 10, m - 10, m 

代码：
 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> l(n + 1), r(n + 1);
  for(int i = 1; i <= n; i ++ ) {
      if(i == 1) l[i] = 1;
      else l[i] = l[i - 1] + 10;
  }
    

  int cnt = 0;
  for(int i = n; i >= 1; i -- ) {
      r[i] = m - cnt * 10;
      cnt ++;
  }
   
    //for(int i = 1; i <= n; i ++ ) cout << l[i] << " " << r[i] << "\n";
  vector<int> ans(n + 1);
  vector<vector<int>> res;
  function<void(int)> dfs = [&](int u) {
    if(u == n + 1) {
        for(int i = 2; i <= n; i ++ ) if(ans[i] - ans[i - 1] < 10) return;
        res.push_back(ans);
        return;
    }
    
    for(int i = l[u]; i <= r[u]; i ++ ) {
        ans[u] = i;
        if(u != 1 && i - ans[u - 1] < 10) continue;
        dfs(u + 1);
    }
  };
  
  dfs(1);
  cout << res.size() << "\n";
  for(auto t: res) {
      for(auto tt: t) {
          if(tt == 0) continue;
          cout << tt << " ";
      }
      cout << "\n";
  }
  return 0;
}
/*
10
1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23
*/

F falling bars

问题：

思路：首先翻译一下题意，大致题意就是一个个矩形区域在一个h * w的区域中自上向下掉落，当且仅当这个矩形下方无矩形时，这个矩形才可以向下掉落，并且不会超过边界。容易注意到这样一个性质，最开始靠下的矩形的掉落一定不会受到最开始比其高的矩形的影响，因为矩形下落速度都一样。那么可以把所给矩形按照高度排序，并自下而上按顺序加入区域中，把离线改成在线。现在考虑如何把矩形对矩形的影响表示出来，如果一个长为L的矩形下落，如果可以查询出这个区间范围内当前最高点，那么最高点 - 1就是该矩形的高度，并且该矩形最终会对他本身这个长度区间的最高点产生影响，也需要区间更新的操作，那么区间查询，区间更新，很明显，懒标记线段树

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int h, w, n;
struct node {
    int l, r, val, tag;
}tr[4 * N];

void pushup(int u) {
    tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
}

void pushdown(int u) {
    tr[u << 1].tag = min(tr[u << 1].tag, tr[u].tag);
    tr[u << 1 | 1].tag = min(tr[u << 1 | 1].tag, tr[u].tag);
    tr[u << 1].val = min(tr[u << 1].val, tr[u].tag);
    tr[u << 1 | 1].val = min(tr[u << 1 | 1].val, tr[u].tag);
    tr[u].tag = h + 1;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].val = h + 1, tr[u].tag = h + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int x) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].val = min(tr[u].val, x);
        tr[u].tag = min(tr[u].tag, x);
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if(mid >= l) modify(u << 1, l, r, x);
        if(mid < r) modify(u << 1 | 1, l, r, x);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].val;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = h + 1;
    pushdown(u);
    if(mid >= l) res = min(res, query(u << 1, l, r));
    if(mid < r) res = min(res, query(u << 1 | 1, l, r));
    return res;
}

int main() {
    cin >> h >> w >> n;
    struct node {
        int x, y, len, id;
        bool operator < (const node &W) const {
            return x > W.x;
        }
    };
    
    build(1, 1, w);
    vector<node> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i].x >> a[i].y >> a[i].len;
    for(int i = 1; i <= n; i ++ ) a[i].id = i;
    sort(a.begin() + 1, a.end());
    vector<int> ans(n + 1);
    for(int i = 1; i <= n; i ++ ) {
        int l = a[i].y, r = a[i].y + a[i].len - 1;
        int now = query(1, l, r);
        ans[a[i].id] = now - 1;
        modify(1, l, r, now - 1);
    }
    
    for(int i = 1; i <= n; i ++ ) cout << ans[i] << "\n";
    cout << "\n";
    return 0;
}