分块进阶
个人记录
P2801 教主的魔法
与上次做的最后一题一样，上次做的是找小于 $c$，这次是大于等于 $c$，所以我们 copy 一下，答案就是 $(r - l + 1) - ask(l,r,k)$。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, L[N], R[N], pos[N], lazy[N], sum[N], a[N];
vector<int> G[N];
void init() {
int len = sqrt(n);
int num = n / len;
if (n % len != 0) {
num++;
}
for (int i = 1; i <= num; i++) {
L[i] = (i - 1) * len + 1;
R[i] = i * len;
}
R[num] = n;
for (int i = 1; i <= num; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
G[i].push_back(a[j]);
}
sort(G[i].begin(), G[i].end());
}
}
void EA(int l, int r, int k) {
int p = pos[l];
for (int i = l; i <= r; i++) {
a[i] += k;
}
G[p].clear();
for (int i = L[p]; i <= R[p]; i++) {
G[p].push_back(a[i]);
}
sort (G[p].begin(), G[p].end());
}
void change(int l, int r, int val) {
int p = pos[l], q = pos[r];
if (p == q) {
EA(l, r, val);
return;
}
EA(l, R[p], val);
EA(L[q], r, val);
for (int i = p + 1; i <= q - 1; i++) {
lazy[i] += val;
}
}
int query(int l, int r, int k) {
vector<int> v;
for (int i = l; i <= r; i++) {
v.push_back(a[i] + lazy[pos[l]]);
}
sort(v.begin(), v.end());
return lower_bound(v.begin(), v.end(), k) - v.begin();
}
int ask(int l, int r, int k) {
int p = pos[l], q = pos[r];
if (p == q) {
return query(l, r, k);
}
int ans = 0;
ans += query(l, R[p], k) + query(L[q], r, k);
for (int i = p + 1; i <= q - 1; i++) {
ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
}
return ans;
}
signed main() {
cin.tie(0), cout.tie(0)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
init();
while (m--) {
char op;
int l, r, k;
cin >> op >> l >> r >> k;
if (op == 'M') {
change(l, r, k);
} else {
cout << (r - l + 1) - ask(l, r, k) << '\n';
}
}
return 0;
}
P3793 由乃救爷爷
st 表空间炸，分块时间炸，所以考虑 st 表 + 分块。
用 st 表预处理每个块，再记录每个块的前缀最大值和后缀最大值。
对于每个完整的块，用 st 表查询，散块两端用前后缀最大值维护。
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 3e7 + 5;
int n, m, a[N], p[N], q[N], dp[5005][13], L[5005], R[5005], pos[N], num;
unsigned s;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
void init() {
int len = sqrt(n);
int num = n / len + (n % len > 0);
for (int i = 1; i <= num; i++) {
L[i] = (i - 1) * len + 1;
R[i] = i * len;
}
R[num] = n;
for (int i = 1; i <= num; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
dp[i][0] = max(dp[i][0], a[j]);
}
p[L[i]] = a[L[i]], q[R[i]] = a[R[i]];
for (int j = L[i] + 1; j <= R[i]; j++) {
p[j] = max(p[j - 1], a[j]);
}
for (int j = R[i] - 1; j >= L[i]; j--) {
q[j] = max(q[j + 1], a[j]);
}
}
for (int j = 1; (1 << j) <= num; j++) {
for (int i = 1; i + (1 << j) - 1 <= num; i++) {
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
}
}
}
int query(int l, int r) {
if (l > r)
return 0;
int lg = log2(r - l + 1);
return max(dp[l][lg], dp[r - (1 << lg) + 1][lg]);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m >> s;
srand(s);
for (int i = 1; i <= n; i++) {
a[i] = read();
}
init();
ull sum = 0;
while (m--) {
int l = read() % n + 1, r = read() % n + 1;
if (l > r)
swap(l, r);
int x = pos[l], y = pos[r];
int tmp = 0;
if (x == y) {
for (int i = l; i <= r; i++) {
tmp = max(tmp, a[i]);
}
} else {
tmp = query(x + 1, y - 1);
tmp = max(tmp, max(q[l], p[r]));
}
sum += tmp;
}
cout << sum;
return 0;
}
P4879 ycz的妹子
有 0 的情况，要用数组存一下。
C 的修改就直接改。
I 有妹子就覆盖，没妹子个数就加进去。
D 对于每个块里妹子个数来找，找到了就赋值为 0。
Q 就是求和。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N], L[N], R[N], pos[N], sum[N], cnt[N], num, len;
bool vis[N];
void init() {
len = sqrt(n);
num = n / len;
if (n % len != 0) {
num++;
}
for (int i = 1; i <= num; i++) {
L[i] = (i - 1) * len + 1;
R[i] = i * len;
}
R[num] = n;
for (int i = 1; i <= num; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
sum[i] += a[j];
if (vis[j])
cnt[i]++;
}
}
return;
}
void change(int l, int r, int c) {
int p = pos[l];
int q = pos[r];
if (p == q) {
for (int i = l; i <= r; i++) {
if (!vis[i])
continue;
a[i] += c;
}
sum[p] += (r - l + 1) * c;
return;
} else {
for (int i = l; i <= R[p]; i++) {
if (!vis[i])
continue;
a[i] += c;
sum[p] += c;
}
for (int i = L[q]; i <= r; i++) {
if (!vis[i])
continue;
a[i] += c;
sum[q] += c;
}
return;
}
}
int check(int l, int r) {
int p = pos[l];
int q = pos[r], ans = 0;
if (p == q) {
for(int i = l; i <= r; i++) {
ans += a[i];
}
return ans;
} else {
for (int i = l; i <= R[p]; i++) {
ans += a[i];
}
for (int i = L[q]; i <= r; i++) {
ans += a[i];
}
p++;
q--;
for (int i = p; i <= q; i++) {
ans += sum[i];
}
return ans;
}
}
void calc1(int l, int c) {
int p = pos[l];
sum[p] -= a[l];
a[l] = c;
sum[p] += c;
if (!vis[l]) {
cnt[p] ++;
}
vis[l] = 1;
}
void calc2(int l) {
int ans = 0;
for (int i = 1; i <= num; i++) {
ans += cnt[i];
if (ans >= l) {
ans -= cnt[i];
for (int j = L[i]; j <= R[i]; j++) {
if (vis[j]) {
ans ++;
}
if (ans == l) {
vis[j] = 0;
sum[i] -= a[j];
a[j] = 0;
cnt[i] --;
break;
}
}
break;
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
vis[i] = 1;
}
n = 5e5;
init();
while (m--) {
char opt;
int l, r, c;
cin >> opt;
if (opt == 'C') {
cin >> l >> c;
change(l , l , -c);
} else if (opt == 'I') {
cin >> l >> c;
calc1(l , c);
} else if (opt == 'D') {
cin >> l;
calc2(l);
} else {
cout << check(1 , n) << "\n";
}
}
return 0;
}