专栏文章

分块进阶

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miok8pka
此快照首次捕获于
2025/12/02 20:34
3 个月前
此快照最后确认于
2025/12/02 20:34
3 个月前
查看原文

P2801 教主的魔法

与上次做的最后一题一样，上次做的是找小于 cc，这次是大于等于 cc，所以我们 copy 一下，答案就是 (r−l+1)−ask(l,r,k)(r - l + 1) - ask(l,r,k)。
CPP
#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 表查询，散块两端用前后缀最大值维护。
CPP
#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 就是求和。
CPP
#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;
}

P4109 [HEOI2015] 定价

末尾 0 越多，移除后长度 aa 越小，荒谬度可能越低，所以我们重点关注两类数：
  • [L,R][L, R] 内靠近 LL 的小范围数；
  • 区间内 1000 的倍数，这样 0 更多。
根据上面模拟即可。
CPP
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long

using namespace std;

int t;

int calc(int x) {
	int cnt1 = 0, cnt2 = 0;
	bool f = 0;
	while (x) {
		if (x % 10 != 0 && !f) {
			if (x % 10 == 5) {
				cnt2 = 1;
			}
			f = 1;
		}
		if (f) {
			cnt1++;
		}
		x /= 10;
	}
	return 2 * cnt1 - cnt2;
}

signed main() {
	for (cin >> t; t--;) {
		int l, r;
		cin >> l >> r;
		int minn = 1e18, rr;
		if (l % 1000 != 0) {
			rr = l - l % 1000 + 1000;
		} else {
			rr = l;
		}
		rr = min(rr, r);
		int idx = 0;
		for (int i = l; i <= rr; i++) {
			int x = calc(i);
			if (x < minn) {
				minn = x, idx = i;
			}
		}
		for (int i = rr; i <= r; i += 1000) {
			int x = calc(i);
			if (x < minn) {
				minn = x, idx = i;
			} 
		}
		cout << idx << '\n';
	}
	return 0;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

跟上次第一题蛮像。
查询时使用二分，确定二分范围，遍历区间涉及的所有块，同步被标记为修改过的块，获取区间内元素的最小值（ltlt）和最大值（rtrt），作为二分初始范围。
查询时上一题一样用 lower_bound。
CPP
#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], a[N];
vector<int> G[N];
bool vis[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 p) {
	G[p].clear();
	for (int i = L[p]; i <= R[p]; i++) {
		a[i] += lazy[p];
		G[p].push_back(a[i]);
	}
	sort (G[p].begin(), G[p].end());
	lazy[p] = 0;
	vis[p] = 0;
}

int check(int l, int r, int k) {
	int p = pos[l], q = pos[r], ans = 0;
	if (p == q) {
		for (int i = l; i <= r; i++) {
			if (a[i] + lazy[p] < k) {
				ans++;
			}
		}
		return ans;
	}
	for (int i = l; i <= R[p]; i++) {
		if (a[i] + lazy[p] < k) {
			ans++;
		}
	}
	for (int i = L[q]; i <= r; i++) {
		if (a[i] + lazy[q] < k) {
			ans++;
		}
	}
	for (int i = p + 1; i <= q - 1; i++) {
		if (G[i][0] >= k - lazy[i])
			continue;
		int tmp = G[i].size() - 1;
		if (G[i][tmp] < k - lazy[i]) {
			ans += R[i] - L[i] + 1;
			continue;
		}
		ans += lower_bound(G[i].begin(), G[i].end(), k - lazy[i]) - G[i].begin();
	}
	return ans;
}

void change(int l, int r, int val) {
	int p = pos[l], q = pos[r];
	if (p == q) {
		for (int i = l; i <= r; i++) {
			a[i] += val;
		}
		vis[p] = 1;
		return;
	}
	for (int i = p + 1; i <= q - 1; i++) {
		lazy[i] += val;
	}
	for (int i = l; i <= R[p]; i++) {
		a[i] += val;
	}
	for (int i = L[q]; i <= r; i++) {
		a[i] += val;
	}
	vis[p] = vis[q] = 1;
}

int query(int l, int r, int k) {
	int lt = 1e9, rt = -1e9, p = pos[l], q = pos[r];
	for (int i = p; i <= q; i++) {
		if (vis[i])	{
			EA(i);
		}
		lt = min(lt, G[i][0] + lazy[i]);
		rt = max(rt, G[i][G[i].size() - 1] + lazy[i]);
	}
	lt--, rt++;
	if (k > r - l + 1) {
		return -1;
	}
	while (lt + 1 < rt) {
		int mid = lt + rt >> 1;
		int tmp = check(l, r, mid);
		if (tmp > k - 1) {
			rt = mid;
		} else {
			lt = mid;
		}
	}
	return rt - 1;
}

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--) {
		int opt, l, r, c;
		cin >> opt >> l >> r >> c;
		if (opt == 1) {
			cout << query(l, r, c) << '\n';
		} else {
			change(l, r, c);
		}
	}
	return 0;
}

P3203 [HNOI2010] 弹飞绵羊

对于 change 函数，预处理能到的点，从 xx 在的块从右往左枚举位置 ii，toi=i+aito_i = i + a_i。
若 toito_i 超出当前块的右边界，则一步就行 stepi=1step_i = 1。
否则，stepi=steptoi+1step_i = step_{to_i} + 1，且 toi=toi+aito_i = to_{i + a_i}。
查询时，直接根据 stepistep_i 记录答案即可。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, a[N], L[N], R[N], pos[N], to[N], step[N], q;

void init() {
	int len = sqrt(n), 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] = min(R[num], n);
	for (int i = 1; i <= num; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
		}
	}
}

int query(int x) {
	int ans = 0;
	while (x <= n) {
		ans += step[x];
		x = to[x];
	}
	return ans;
}

void change(int x, int y) {
	a[x] = y;
	for (int i = R[pos[x]]; i >= L[pos[x]]; i--) {
		to[i] = i + a[i];
		if (to[i] > R[pos[i]]) {
			step[i] = 1;
		} else {
			step[i] = step[to[i]] + 1;
			to[i] = to[i + a[i]];
		}
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	init();
	for (int i = n; i >= 1; i--) {
		to[i] = a[i] + i;
		if (to[i] > R[pos[i]]) {
			step[i] = 1;
		} else {
			step[i] = step[to[i]] + 1;
			to[i] = to[i + a[i]];
		}
	}
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		y++;
		if (x == 1) {
			cout << query(y) << '\n';
		} else {
			int k;
			cin >> k;
			change(y, k);
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...