LibreOJ 6278. 数列ブロック入門2題解
3824 ワード
タイトルリンク:https://loj.ac/problem/6278
タイトルの説明
長い(n)の数列と、ある値(x)より小さい区間加算の要素数を尋ねる(n)個の操作が与えられます.
入力フォーマット
最初の行に数値(n)を入力します.2行目には(n)個の数字を入力し、(i)個目には(a_i)と入力し、スペースで区切ります.次に、(n)行問合せを入力し、行ごとに4つの数値(opt)、(l)、(r)、(c)を入力してスペースで区切ります.(opt=0)の場合、([l,r])の間にある数字に(c)が加算されます.(opt=1)の場合、問合せ([l,r])のうち、(c^2)未満の数を表す.
出力フォーマット
質問のたびに、1行1つの数字を出力して答えを表します.
サンプル入力
サンプル出力
問題を解く構想.
同様に、ブロックは各ブロックのサイズ(lfloorsqrt{n}rfloor)で分割される.ここでは、(p[i])が属するブロック番号を同様に(p[i])で表し、(k)番目のブロックの累積更新値を(v[k])で表します.同時に、私たちはもう一つの配列(b[i])を開き、(b)配列は実は(a)配列のマッピングです.では、どのようにマッピングされていますか?(a[l..r])が同じブロックに属し、(a[l]がこのブロックの最初の要素であり、)a[r$がこのブロックの最後の要素であると仮定すると、(b[l..r])は(a[l..r])の順序付けの結果である.(b[l])は(a[l..r])の中で最も小さい要素に対応する. (b[l+1])は(a[l..r])の中で小さい要素に対応する. …… (b[r])は、(a[l..r])の中で最大の要素に対応します.
ブロック(k)の一部の要素を変更すると、ブロック(k)に対応する(b)配列のこの区間をソートする必要があります(ブロック(k)については、座標範囲は([(k-1)times m+1,min(ktimes m,n)]).
変更操作:区間がブロック(k)を完全にカバーしていない場合、繰り返しブロック内の各要素は、(a[i]+=c)となる. それ以外の場合(ブロック(k))、は(v[k]+=c)となります.
クエリー操作:区間がブロック(k)を完全にカバーしていない場合、繰り返しブロックの各要素は、(a[i]ltc^2-v[p[i])が成立するか否かを判断する. それ以外の場合(完全にブロック(k))は、(b)配列に単調性があるため、ブロック(k)に含まれる区間範囲内の(b[l..r])を二分してどれだけの要素(b[i]lt c^2-v[k])を取得します.
最後に答えをまとめます.
毎回変更する時間の複雑度は(O(sqrt{n}));各クエリの時間的複雑度は(O(sqrt{n}timessqrt{sqrt{n})=O(n^{frac 34}))であり、
全部で(n)回の操作があるので、全体の時間複雑度は(O(ntimes n^{frac 34}))である.
実装コードは次のとおりです.
タイトルの説明
長い(n)の数列と、ある値(x)より小さい区間加算の要素数を尋ねる(n)個の操作が与えられます.
入力フォーマット
最初の行に数値(n)を入力します.2行目には(n)個の数字を入力し、(i)個目には(a_i)と入力し、スペースで区切ります.次に、(n)行問合せを入力し、行ごとに4つの数値(opt)、(l)、(r)、(c)を入力してスペースで区切ります.(opt=0)の場合、([l,r])の間にある数字に(c)が加算されます.(opt=1)の場合、問合せ([l,r])のうち、(c^2)未満の数を表す.
出力フォーマット
質問のたびに、1行1つの数字を出力して答えを表します.
サンプル入力
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
サンプル出力
3
0
2
問題を解く構想.
同様に、ブロックは各ブロックのサイズ(lfloorsqrt{n}rfloor)で分割される.ここでは、(p[i])が属するブロック番号を同様に(p[i])で表し、(k)番目のブロックの累積更新値を(v[k])で表します.同時に、私たちはもう一つの配列(b[i])を開き、(b)配列は実は(a)配列のマッピングです.では、どのようにマッピングされていますか?(a[l..r])が同じブロックに属し、(a[l]がこのブロックの最初の要素であり、)a[r$がこのブロックの最後の要素であると仮定すると、(b[l..r])は(a[l..r])の順序付けの結果である.
ブロック(k)の一部の要素を変更すると、ブロック(k)に対応する(b)配列のこの区間をソートする必要があります(ブロック(k)については、座標範囲は([(k-1)times m+1,min(ktimes m,n)]).
変更操作:
クエリー操作:
最後に答えをまとめます.
毎回変更する時間の複雑度は(O(sqrt{n}));各クエリの時間的複雑度は(O(sqrt{n}timessqrt{sqrt{n})=O(n^{frac 34}))であり、
全部で(n)回の操作があるので、全体の時間複雑度は(O(ntimes n^{frac 34}))である.
実装コードは次のとおりです.
#include
using namespace std;
const int maxn = 50050;
int n, m, a[maxn], b[maxn], p[maxn], v[300], op, l, r, c;
void update_part(int pid) {
int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1); // , RE , m
for (int i = i1; i < i2; i ++)
b[i] = a[i];
sort(b+i1, b+i2);
}
void add(int l, int r, int c) {
if (p[l] == p[r]) { // ,
for (int i = l; i <= r; i ++) a[i] += c;
update_part(p[l]);
return;
}
if (l % m != 1) { // l p[l]
for (int i = l; p[i]==p[l]; i ++) {
a[i] += c;
}
update_part(p[l]);
}
else v[p[l]] += c;
if (r % m != 0) { // r p[r]
for (int i = r; p[i]==p[r]; i --)
a[i] += c;
update_part(p[r]);
}
else v[p[r]] += c;
for (int i = p[l]+1; i < p[r]; i ++)
v[i] += c;
}
int count_part(int pid, int c) {
int i1 = (pid-1)*m+1, i2 = min(pid*m+1, n+1);
int cnt = lower_bound(b+i1, b+i2, c*c-v[pid]) - (b+i1);
return cnt;
}
int get_count(int l, int r, int c) {
int cnt = 0;
if (p[l] == p[r]) { // ,
for (int i = l; i <= r; i ++)
if (a[i]+v[p[i]] < c*c)
cnt ++;
return cnt;
}
if (l % m != 1) { // l p[l]
for (int i = l; p[i]==p[l]; i ++)
if (a[i]+v[p[i]] < c*c)
cnt ++;
}
else cnt += count_part(p[l], c);
if (r % m != 0) { // r p[r]
for (int i = r; p[i]==p[r]; i --)
if (a[i]+v[p[i]] < c*c)
cnt ++;
}
else cnt += count_part(p[r], c);
for (int i = p[l]+1; i < p[r]; i ++)
cnt += count_part(i, c);
return cnt;
}
int main() {
scanf("%d", &n);
m = sqrt(n);
for (int i = 1; i <= n; i ++) p[i] = (i-1)/m + 1;
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = m; i <= n; i += m) update_part(p[i]); //
for (int i = 0; i < n; i ++) {
scanf("%d%d%d%d", &op, &l, &r, &c);
if (op == 0) add(l, r, c);
else printf("%d
", get_count(l, r, c));
}
return 0;
}