HDU 6315 Naive Operations

发表于 | 分类于

Description

给你一个\(1\ldots n\)的排列\(b_i\)和一个长为\(n\)的序列\(a_i\)，\(a_i\)初始全为\(0\)。然后要求支持以下两种操作：

  • add l r：将\(a_i\)中区间\([l, r]\)的每一个位置都加一。
  • query l r：查询\(\sum_{i = l}^r\lfloor\frac{a_i}{b_i}\rfloor\)。

多组数据（一个点最多五组）。\(1\leq n\leq 10^5\)。

Solution

设\(c_i = \lfloor\frac{a_i}{b_i}\rfloor\)。首先一次加操作可能会导致一些\(c_i\)的变动，也可能不造成。那么假设我们在每次变动的时候都进行单点修改，那么对于位置\(i\)其被修改次数最多为\(\lfloor\frac{q}{b_i}\rfloor\)，因此即使在极限情况下修改次数也不过是\(O(n\log n)\)级别的，用树状数组维护\(c_i\)即可。

接下来考虑怎样才能知道\(c_i\)是否在这次操作后需要改动。不妨记\(d_i\)表示\(i\)这个位置还要加多少才能迎来下一次\(c_i\)变动，那么我们每次add就是对一个区间的\(d_i\)减，如果\(d_i = 0\)的话就需要修改。注意到此时\(d_i\)一定是该区间内最小的，因此不断取最小值变动相应\(c_i\)，然后再修改\(d_i\)即可。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 100005;
const int maxno = maxn << 2;
typedef std::pair<int, int> pii;
pii minv[maxno]; int addv[maxno];
void maintain(int o) {
  minv[o] = std::min(minv[o << 1], minv[o << 1 | 1]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o].first += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    paint(o << 1, addv[o]);
    paint(o << 1 | 1, addv[o]);
    addv[o] = 0;
  }
}

int b[maxn];
void build_tree(int o, int L, int R) {
  addv[o] = 0;
  if(L == R) {
    minv[o] = std::make_pair(b[L], L);
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, int p, int v) {
  if(L == R) {
    minv[o].first = v;
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o);
  }
}
void modify(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M, ql, qr, v);
    if(qr > M) modify(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
pii query(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    pii ret = std::make_pair(0x7f7f7f7f, 0);
    if(ql <= M) ret = std::min(ret, query(o << 1, L, M, ql, qr));
    if(qr > M) ret = std::min(ret, query(o << 1 | 1, M + 1, R, ql, qr));
    return ret;
  }
}

int C[maxn]; int n;
inline int lowbit(int x) {
  return x & (-x);
}
void add(int p, int v) {
  while(p <= n) {
    C[p] += v;
    p += lowbit(p);
  }
}
int sum(int p) {
  int ans = 0;
  while(p > 0) {
    ans += C[p];
    p -= lowbit(p);
  }
  return ans;
}
int query(int l, int r) {
  return sum(r) - sum(l - 1);
}

int main() {
  int q;
  while(scanf("%d%d", &n, &q) == 2) {
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &b[i]);
    }
    build_tree(1, 1, n); memset(C, 0, sizeof(C));
    char buf[10];
    while(q --) {
      int l, r; scanf("%s%d%d", buf, &l, &r);
      if(buf[0] == 'a') {
        modify(1, 1, n, l, r, -1);
        pii t;
        while((t = query(1, 1, n, l, r)).first == 0) {
          add(t.second, 1);
          modify(1, 1, n, t.second, b[t.second]);
        }
      } else {
        printf("%d\n", query(l, r));
      }
    }
  }
  return 0;
}