首页 > 其他分享 >突刺贯穿的第二分块

突刺贯穿的第二分块

时间:2023-03-17 23:57:35浏览次数:62  
标签:const 分块 int maxv 贯穿 maxn mathcal return 突刺

[CF896E] Welcome home, Chtholly

给定一个长为 \(n\) 的序列 \(a_1\sim a_n\),\(m\) 次操作,分两种:

  • 1 l r x,将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。

  • 2 l r x,询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。

\(1\le n,m,a_i,x\le 10^5\)。


lxl 的分块科技,很奇妙。

考虑根据这个特殊的值域搞点什么东西。

分块以后可以直接在每个块内开 \(10^5\) 个桶存这个块里的数。这样询问操作就可以解决了。

考虑修改操作,散块重构,对于整块,两种暴力:

  • 给 \(\le x\) 的数加上 \(x\),然后给整个块打上一个整体减 \(x\) 的 tag。

  • 枚举 \(\gt x\) 的桶 \(i\),将桶 \(i\) 和 \(i-x\) 合并。

单次操作 \(\mathcal O(V)\),这是坏的。考虑平衡思想,将两者结合。记录整块最大值 \(\rm maxv\),分类:

  • \(\mathrm{maxv}\le 2x\),采用暴力 2.

  • \(\mathrm{maxv}\gt 2x\),采用暴力 1.

相当于用 \(\mathcal O(Dx)\) 的代价使得 \(\rm maxv\) 减小了 \(x\)。总复杂度 \(\mathcal O(Dn\sqrt n)\),这是好的。

考虑用一个 \(\mathcal O(1)\) 复杂度的数据结构维护桶的合并。使用并查集,因为每条边至多被遍历一遍,单次复杂度均摊 \(\mathcal O(1)\)。

强化版卡空间,可以离线,对于每个块单独计算对所有询问的贡献。

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
const int S = 400;

int read() {
	int s = 0;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar());
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}

void print(int x) {
	if(x > 9)
		print(x / 10);
	putchar(x % 10 + '0');
	return ;
}

int pre[maxn],val[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

struct node {
	int rt,sz;
	node() {
		rt = sz = 0;
	}
} d[S + 5][maxn];

int max(const int& x,const int& y) {
	return x > y ? x : y;
}

int min(const int& x,const int& y) {
	return x < y ? x : y;
}

int n,m,a[maxn],t,maxv[S],L[S],R[S],pos[maxn],tag[S];

void pushdown(int p) {
	for(int i = L[p];i <= R[p];++ i)
		a[i] = val[find(i)],d[p][a[i]].rt = d[p][a[i]].sz = 0,a[i] -= tag[p];
	tag[p] = 0;
	for(int i = L[p];i <= R[p];++ i)
		pre[i] = 0;
	return ;
}

void Maintain(int p) {
	maxv[p] = 0;
	for(int i = L[p];i <= R[p];++ i) {
		maxv[p] = max(maxv[p] , a[i]);
		++ d[p][a[i]].sz;
		if(!d[p][a[i]].rt)
			d[p][a[i]].rt = pre[i] = i,val[i] = a[i];
		else
			pre[i] = d[p][a[i]].rt;
	}
	return ;
}

void Merge(int p,int x,int y) {
	if(d[p][y].rt)
		pre[d[p][x].rt] = d[p][y].rt;
	else
		d[p][y].rt = d[p][x].rt,val[d[p][x].rt] = y;
	d[p][y].sz += d[p][x].sz;
	d[p][x].sz = d[p][x].rt = 0;
	return ;
}

void gettag(int p,int x) {
	if(maxv[p] - tag[p] < (x << 1)) {
		for(int i = maxv[p];i > x + tag[p];-- i)
			if(d[p][i].rt)
				Merge(p , i , i - x);
		maxv[p] = min(maxv[p] , x + tag[p]);
	}
	else {
		for(int i = tag[p] + 1;i <= x + tag[p];++ i)
			if(d[p][i].rt)
				Merge(p , i , i + x);
		tag[p] += x;
	}
	return ;
}

void modify(int l,int r,int x) {
	int p = pos[l],q = pos[r];
	if(p == q) {
		pushdown(p);
		for(int i = l;i <= r;++ i)
			if(a[i] > x)
				a[i] -= x;
		Maintain(p);
	}
	else {
		pushdown(p);
		pushdown(q);
		for(int i = l;i <= R[p];++ i)
			if(a[i] > x)
				a[i] -= x;
		for(int i = L[q];i <= r;++ i)
			if(a[i] > x)
				a[i] -= x;
		Maintain(p);
		Maintain(q);
		for(int i = p + 1;i < q;++ i)
			gettag(i , x);
	}
	return ;
}

int query(int l,int r,int x) {
	int ans = 0,p = pos[l],q = pos[r];
	if(p == q) {
		for(int i = l;i <= r;++ i)
			if(val[find(i)] - tag[p] == x)
				++ ans;
	}
	else {
		for(int i = l;i <= R[p];++ i)
			if(val[find(i)] - tag[p] == x)
				++ ans;
		for(int i = L[q];i <= r;++ i)
			if(val[find(i)] - tag[q] == x)
				++ ans;
		for(int i = p + 1;i < q;++ i)
			if(x + tag[i] <= 100000)
				ans += d[i][x + tag[i]].sz;
	}
	return ans;
}

int main() {
	n = read();
	m = read();
	for(int i = 1;i <= n;++ i)
		a[i] = read(),pos[i] = (i - 1) / S + 1;
	for(int i = 1;i <= n;++ i) {
		if(!L[pos[i]])
			L[pos[i]] = i;
		R[pos[i]] = i;
	}
	for(int i = 1;i <= pos[n];++ i)
		Maintain(i);
	while(m --) {
		int op = read(),l = read(),r = read(),x = read();
		if(op == 1)
			modify(l , r , x);
		else
			print(query(l , r , x)),putchar('\n');
	}
	return 0;
}

标签:const,分块,int,maxv,贯穿,maxn,mathcal,return,突刺
From: https://www.cnblogs.com/Modirant/p/17228762.html

相关文章

  • Hate That You Know Me (15黑龙江省赛) (数学公式题)(数论分块) (前缀和,小的数学结论
      思路;遇到数学公式,一层一层剥开发现那个式子就是求n内的每一个数的倍数在n以内的数量,明显数论分块来处理这个问题然后就是因子的^2,^3,这个子问题......
  • 【CF1491H Yuezheng Ling and Dynamic Tree】(分块)
    原题链接题意给定一棵大小为\(n\)的\(1\)为根节点的树,树用如下方式给出:输入\(a_2,a_3,\dots,a_n\),保证\(1\leqa_i<i\),将\(a_i\)与\(i\)连边形成一棵树。接下......
  • [科技] 分块 FFT
    其实也不是啥科技。就是一些卷积形式的东西,直接FFT复杂度非常大。但是你分块以后再FFT/NTT就很牛逼。CodeChefCOUNTARI按照\(i,j,k\)在哪个块中,分类讨论......
  • 数学结构化语言——矩阵的分块简化(四)
    分块矩阵是线性代数中的一个重要内容,是处理阶数较高的矩阵时常采用的技巧,也是数学在多领域的研究工具。对矩阵进行适当分块,可使高阶矩阵的运算可以转化为低阶矩阵的运算,同......
  • 省选备战报告 第零辑 分块与根号平衡
    本笔记仅仅记录重点思路,详细解题过程请参阅原题题解难度从低到高为NÄIVE:有效思考时间少于十分钟EASY:能够完全独立得出MEDIUMEASY:需要题解提供关键思路跨越MEDIUM:需......
  • 【深度挖掘 RocketMQ底层源码】「底层源码挖掘系列」抽丝剥茧贯穿RocketMQ的消费者端
    承接【【深度挖掘RocketMQ底层源码】「底层源码挖掘系列」透彻剖析贯穿RocketMQ的消费者端的运行核心的流程(Pull模式-上)】pullBlockIfNotFound方法通过该方法获取该Message......
  • Java多线程分块下载器
    '''javaimportjava.io.*;importjava.net.HttpURLConnection;importjava.net.URL;importjava.nio.file.Files;importjava.nio.file.Path;importjava.nio.file.S......
  • 大文件分块上传
    #1.项目背景由于用户需求,需要上传大量图片,只能通过上传压缩包的形式上传,可是压缩包过大时,又会出现上传超时的情况,故需要将压缩包分块上传,然后解压缩图片、若图片过大则再......
  • 分块莫队学习笔记
    适用情况:对于序列A中某个子区间的问题,当遇到像众数类似的不满足区间合并的性质的数据,或者一些用线段树、树状数组比较难维护的数据时,使用分块莫队。实际上是对暴力的一种......
  • 分块
    (强制在线)单点修,区间第\(k\)小首先有一个简单的序列分块+值域二分做法:序列分块,对每个块建值域树状数组。修改时暴力修改,\(O(\log)\)。询问时将两侧散块合并建......