LibreOJ 数列分块入门

题目链接：https://loj.ac/problem/6277

题目描述

给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，单点查值。

输入格式

第一行输入一个数字 nnn。

第二行输入 nnn 个数字，第 iii 个数字为 aia_ia​i​​，以空格隔开。

接下来输入 nnn 行询问，每行输入四个数字 optmathrm{opt}opt、lll、rrr、ccc，以空格隔开。

若 opt=0mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都加 ccc。

若 opt=1mathrm{opt} = 1opt=1，表示询问 ara_ra​r​​ 的值（lll 和 ccc 忽略）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

样例输出

2
5

数据范围与提示

对于 100% 100\%100% 的数据，1≤n≤50000,−231≤others 1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 mathrm{ans} leq 2^{31}-1ans≤2​31​​−1。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-8;
15 const int INF = 2e9;
16 const LL LNF = 2e18;
17 const int MAXN = 5e4+10;
18 
19 int block;
20 int a[MAXN], lazy[MAXN];
21 void add(int pos, int c)
22 {
23     int B = pos/block;
24     for(int i = 0; i<B; i++) lazy[i] += c;
25     for(int i = B*block; i<=pos; i++) a[i] += c;
26 }
27 
28 int main()
29 {
30     int n;
31     while(scanf("%d", &n)!=EOF)
32     {
33         block = sqrt(n);
34         for(int i = 0; i<n; i++)
35             scanf("%d", &a[i]);
36         int opt, l, r, c;
37         memset(lazy, 0, sizeof(lazy));
38         for(int i = 0; i<n; i++)
39         {
40             scanf("%d%d%d%d",&opt,&l,&r,&c);
41             l--; r--;
42             if(opt==0)
43             {
44                 add(r,c);
45                 if(l!=0) add(l-1,-c);
46             }
47             else
48                 printf("%d
", a[r]+lazy[r/block]);
49         }
50     }
51 }
View Code

题目描述

给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，询问区间内小于某个值 xxx 的元素个数。

输入格式

第一行输入一个数字 nnn。

第二行输入 nnn 个数字，第 i 个数字为 aia_ia​i​​，以空格隔开。

接下来输入 nnn 行询问，每行输入四个数字 optmathrm{opt}opt、lll、rrr、ccc，以空格隔开。

若 opt=0mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都加 ccc。

若 opt=1mathrm{opt} = 1opt=1，表示询问 [l,r][l, r][l,r] 中，小于 c2c^2c​2​​ 的数字的个数。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

样例输出

3
0
2

数据范围与提示

对于 100% 100\%100% 的数据，1≤n≤50000,−231≤others 1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 mathrm{ans} leq 2^{31}-1ans≤2​31​​−1。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-8;
15 const int INF = 2e9;
16 const LL LNF = 2e18;
17 const int MAXN = 1e5+10;
18 
19 int n, block;
20 int a[MAXN], tmp[MAXN], lazy[MAXN];
21 vector<int> v[MAXN];
22 void add(int pos, int c)
23 {
24     int B = pos/block;
25     for(int i = 0; i<B; i++) lazy[i] += c;
26     for(int i = B*block; i<=pos; i++) a[i] += c;
27     for(int i = B*block; i<min(n,B*block+block); i++) tmp[i] = a[i];
28     sort(tmp+B*block,tmp+min(n,B*block+block));
29 }
30 
31 int query(int pos, int c)
32 {
33     int ret = 0;
34     int B = pos/block;
35     for(int i = 0; i<B; i++)
36         ret += lower_bound(tmp+i*block, tmp+i*block+block, c*c-lazy[i]) - (tmp+i*block);
37 
38     for(int i = B*block; i<=pos; i++)
39         if(a[i]+lazy[B]<c*c) ret++;
40 /*
41     错误：
42     ret += lower_bound(tmp+B*block, tmp+pos+1, c*c-lazy[B]) - (tmp+B*block);
43 */
44     return ret;
45 }
46 
47 int main()
48 {
49     while(scanf("%d", &n)!=EOF)
50     {
51         block = sqrt(n);
52         for(int i = 0; i<n; i++)
53             scanf("%d", &a[i]), tmp[i] = a[i];
54 
55         for(int i = 0; i<block; i++)
56             sort(tmp+i*block, tmp+i*block+block);
57          sort(tmp+block*block, tmp+n);
58 
59         int opt, l, r, c;
60         memset(lazy, 0, sizeof(lazy));
61         for(int i = 0; i<n; i++)
62         {
63             scanf("%d%d%d%d", &opt,&l,&r,&c);
64             l--; r--;
65             if(opt==0)
66             {
67                 add(r,c);
68                 if(l) add(l-1, -c);
69             }
70             else
71             {
72                 int ans = query(r, c);
73                 if(l) ans -= query(l-1, c);
74                 printf("%d
", ans);
75             }
76         }
77     }
78 }
View Code

题目描述

给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，询问区间内小于某个值 xxx 的前驱（比其小的最大元素）。

输入格式

第一行输入一个数字 nnn。

第二行输入 nnn 个数字，第 i 个数字为 aia_ia​i​​，以空格隔开。

接下来输入 nnn 行询问，每行输入四个数字 optmathrm{opt}opt、lll、rrr、ccc，以空格隔开。

若 opt=0mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都加 ccc。

若 opt=1mathrm{opt} = 1opt=1，表示询问 [l,r][l, r][l,r] 中 ccc 的前驱的值（不存在则输出 −1-1−1）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输出

3
-1

数据范围与提示

对于 100% 100\%100% 的数据，1≤n≤100000,−231≤others 1 leq n leq 100000, -2^{31} leq mathrm{others}1≤n≤100000,−2​31​​≤others、ans≤231−1 mathrm{ans} leq 2^{31}-1ans≤2​31​​−1。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-8;
15 const int INF = 2e9;
16 const LL LNF = 2e18;
17 const int MAXN = 1e5+10;
18 
19 int n, block;
20 int a[MAXN], tmp[MAXN], lazy[MAXN];
21 vector<int> v[MAXN];
22 
23 void reset(int B)
24 {
25     for(int i = B*block; i<min(n,B*block+block); i++) tmp[i] = a[i];
26     sort(tmp+B*block,tmp+min(n,B*block+block));
27 }
28 
29 void add(int l, int r, int c)
30 {
31     int lB = l/block, rB = r/block;
32     for(int i = l; i<=min(r,lB*block+block-1); i++) a[i] += c;
33     reset(lB);
34 
35     for(int i = lB+1; i<=rB-1; i++) lazy[i] += c;
36     if(lB!=rB)
37     {
38         for(int i = rB*block; i<=r; i++) a[i] += c;
39         reset(rB);
40     }
41 }
42 
43 int query(int l, int r, int c)
44 {
45     int ret = -1;
46     int lB = l/block, rB = r/block;
47     for(int i = l; i<=min(r,lB*block+block-1); i++)
48         if(a[i]+lazy[lB]<c) ret = max(ret, a[i]+lazy[lB]);
49     for(int i = lB+1; i<=rB-1; i++)
50     {
51         int cnt = lower_bound(tmp+i*block, tmp+i*block+block, c-lazy[i]) - (tmp+i*block);
52         if(cnt) ret = max(ret, tmp[i*block+cnt-1]+lazy[i]);
53     }
54     if(lB!=rB)
55     {
56         for(int i = rB*block; i<=r; i++)
57             if(a[i]+lazy[rB]<c) ret = max(ret, a[i]+lazy[rB]);
58     }
59     return ret;
60 }
61 
62 int main()
63 {
64     while(scanf("%d", &n)!=EOF)
65     {
66         block = sqrt(n);
67         for(int i = 0; i<n; i++)
68             scanf("%d", &a[i]), tmp[i] = a[i];
69 
70         for(int i = 0; i<block; i++)
71             sort(tmp+i*block, tmp+i*block+block);
72          sort(tmp+block*block, tmp+n);
73 
74         int opt, l, r, c;
75         memset(lazy, 0, sizeof(lazy));
76         for(int i = 0; i<n; i++)
77         {
78             scanf("%d%d%d%d", &opt,&l,&r,&c);
79             l--; r--;
80             if(opt==0) add(l,r,c);
81             else printf("%d
", query(l,r, c));
82         }
83     }
84 }
View Code

题目描述

给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间开方，区间求和。

输入格式

第一行输入一个数字 nnn。

第二行输入 nnn 个数字，第 i 个数字为 aia_ia​i​​，以空格隔开。

接下来输入 nnn 行询问，每行输入四个数字 optmathrm{opt}opt、lll、rrr、ccc，以空格隔开。

若 opt=0mathrm{opt} = 0opt=0，表示将位于 [l,r][l, r][l,r] 的之间的数字都开方。

若 opt=1mathrm{opt} = 1opt=1，表示询问位于 [l,r][l, r][l,r] 的所有数字的和。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

样例输出

6
2

数据范围与提示

对于 100% 100\%100% 的数据，1≤n≤50000,−231≤others 1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−2​31​​≤others、ans≤231−1 mathrm{ans} leq 2^{31}-1ans≤2​31​​−1。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const double EPS = 1e-8;
15 const int INF = 2e9;
16 const LL LNF = 2e18;
17 const int MAXN = 1e5+10;
18 
19 int n, block;
20 int a[MAXN], tmp[MAXN], cnt[MAXN], vis[MAXN], sum[MAXN];
21 void add(int l, int r)
22 {
23     int lB = l/block, rB = r/block;
24     for(int i = l; i<=min(r,lB*block+block-1); i++)
25     {
26         int val = sqrt(a[i]);
27         sum[lB] += val - a[i];
28         a[i] = val;
29         if((val==1||val==0)&&!vis[i])
30             vis[i] = 1, cnt[lB]--;
31     }
32 
33     for(int i = lB+1; i<=rB-1; i++)
34     if(cnt[i])
35     {
36         for(int j = i*block; j<i*block+block; j++)
37         {
38             int val = sqrt(a[j]);
39             sum[i] += val-a[j];
40             a[j] = val;
41             if((val==1||val==0)&&!vis[j])
42                 vis[j] = 1, cnt[i]--;
43         }
44     }
45     if(lB!=rB)
46     {
47         for(int i = rB*block; i<=r; i++)
48         {
49             int val = sqrt(a[i]);
50             sum[rB] += val - a[i];
51             a[i] = val;
52             if((val==1||val==0)&&!vis[i])
53                 vis[i] = 1, cnt[rB]--;
54         }
55     }
56 }
57 
58 int query(int l, int r)
59 {
60     int ret = 0;
61     int lB = l/block, rB = r/block;
62     for(int i = l; i<=min(r,lB*block+block-1); i++)
63         ret += a[i];
64     for(int i = lB+1; i<=rB-1; i++)
65         ret += sum[i];
66     if(lB!=rB)
67     {
68         for(int i = rB*block; i<=r; i++)
69             ret += a[i];
70     }
71     return ret;
72 }
73 
74 int main()
75 {
76     while(scanf("%d", &n)!=EOF)
77     {
78         block = sqrt(n);
79         memset(cnt, 0, sizeof(cnt));
80         memset(vis, 0, sizeof(vis));
81         memset(sum, 0, sizeof(sum));
82         for(int i = 0; i<n; i++)
83             scanf("%d", &a[i]), cnt[i/block]++, sum[i/block] += a[i];
84 
85         int opt, l, r, c;
86         for(int i = 0; i<n; i++)
87         {
88             scanf("%d%d%d%d", &opt,&l,&r,&c);
89             l--; r--;
90             if(opt==0) add(l,r);
91             else printf("%d
", query(l,r));
92         }
93     }
94 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/DOLFAMINGO/p/8681099.html