分块

教主的魔法

这道题首先可以分块,对于每一个块直接$sort$一下,查询的时候对于每个块就直接二分

修改操作是一个很经典的套路,对每个块维护一个$sum$,每个块的值就是其值加上$sum$,边角料暴力修改即可

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
// luogu-judger-enable-o2
/***************************************************************
File name: P2801.cpp
Author: ljfcnyali
Create time: 2019年06月16日 星期日 16时00分21秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
typedef long long LL;

const int maxn = 2000010;

LL a[maxn], p[maxn], f[1010][1010], block, n, m, num, sum[1010];

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%lld%lld", &n, &m);
block = sqrt(n); num = n - block * block;
REP(i, 0, n + block) a[i] = -0x3f3f3f3f;
REP(i, 1, n)
{
scanf("%lld", &a[i]);
p[i] = (i - 1) / block + 1;
f[p[i]][i - (p[i] - 1) * block] = a[i];
}
REP(i, 1, block) sort(f[i] + 1, f[i] + block + 1);
sort(f[block + 1] + 1, f[block + 1] + block + 1);
REP(i, 1, m)
{
getchar();
getchar(); char c = getchar();
LL l, r, w; scanf("%lld%lld%lld", &l, &r, &w);
if ( c == 'A' )
{
LL ans = 0;
if ( p[l] == p[r] )
{
REP(j, l, r) if ( a[j] + sum[p[l]] >= w ) ++ ans;
printf("%lld\n", ans); continue ;
}
REP(j, l, p[l] * block) if ( a[j] + sum[p[l]] >= w ) ++ ans;
REP(j, (p[r] - 1) * block + 1, r) if ( a[j] + sum[p[r]] >= w ) ++ ans;
REP(j, p[l] + 1, p[r] - 1)
{
LL L = 1, R = block, s = block + 1;
while ( L <= R )
{
LL Mid = L + R >> 1;
if ( f[j][Mid] + sum[j] >= w ) { R = Mid - 1; s = Mid; }
else L = Mid + 1;
}
ans += block - s + 1;
}
printf("%lld\n", ans);
}
else
{
if ( p[l] == p[r] )
{
REP(j, l, r) a[j] += w;
LL x = (p[l] - 1) * block;
REP(j, 1, block) f[p[l]][j] = a[x + j];
sort(f[p[l]] + 1, f[p[l]] + block + 1);
continue ;
}
REP(j, l, p[l] * block) a[j] += w;
REP(j, (p[r] - 1) * block + 1, r) a[j] += w;
LL x = (p[l] - 1) * block;
REP(j, 1, block) f[p[l]][j] = a[x + j];
x = (p[r] - 1) * block;
REP(j, 1, block) f[p[r]][j] = a[x + j];
sort(f[p[l]] + 1, f[p[l]] + block + 1);
sort(f[p[r]] + 1, f[p[r]] + block + 1);
REP(j, p[l] + 1, p[r] - 1) sum[j] += w;
}
}
return 0;
}

[HNOI2010]弹飞绵羊

这道题对于每一个点我们可以用$O(n)$维护一个$s[i],to[i]$分别表示从$i$跳出这个块的次数和跳出后的点

接下来的查找操作就可以$O(\sqrt n)$的进行了,修改操作暴力修改那个块即可

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
// luogu-judger-enable-o2
/***************************************************************
File name: P3203.cpp
Author: ljfcnyali
Create time: 2019年06月17日 星期一 09时34分29秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )

const int maxn = 200010;

int block, p[maxn], a[maxn], to[maxn], s[maxn], n, m;

inline void Solve(int l, int r)
{
for ( int i = r; i >= l; -- i )
{
int L = (p[i] - 1) * block + 1, R = p[i] * block;
if ( i + a[i] > R ) { to[i] = i + a[i]; s[i] = 1; }
else { s[i] = s[i + a[i]] + 1; to[i] = to[i + a[i]]; }
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n); block = sqrt(n) * 2;
REP(i, 1, n) { scanf("%d", &a[i]); p[i] = (i - 1) / block + 1; }
Solve(1, n);
scanf("%d", &m);
REP(i, 1, m)
{
int opt; scanf("%d", &opt);
if ( opt == 1 )
{
int x, ans = 0; scanf("%d", &x); ++ x;
while ( x <= n ) { ans += s[x]; if ( to[x] == x ) break ; x = to[x]; }
printf("%d\n", ans);
}
else
{
int x, val; scanf("%d%d", &x, &val); ++ x;
a[x] = val; Solve((p[x] - 1) * block + 1, p[x] * block);
}
}
return 0;
}