【未完】洛谷数列分块入门全家桶题解

userId_undefined

cjdstttttt

题解仙人时空双修者尊贵铂金勇敢小狗CSP-J一等奖出题人

2025-11-23 11:58:36

发布于：广东

8阅读
0回复
0点赞

好毒瘤。为什么数据还有 00 和负数。

T1

题意解析：给定一个长度为 nn 的数组 AA，你需要进行 nn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,c。

  • opt=0opt=0：请将 Al,...,ArA_l,...,A_r 的值加上 cc。
  • opt=1opt=1：查询 ArA_r 的值。

考虑分块。

考虑转化成差分数组，BiB_i 记录 Ai−Ai−1A_i-A_{i-1} 的值。这样操作 00 转化成将 BlB_l 加 cc，Br+1B_{r+1} 减 cc；操作 11 转化成 ∑j=1rBj\sum_{j=1}^r B_j。

我们将数组分成 O(n)O(\sqrt n) 块，查询时我们可以分成两边的散块和中间的整块查询。

我们修改时 O(n)O(\sqrt n) 暴力维护每一块的和（可以 O(1)O(1) 但是没必要），这样查询时中间每一个整块就可以 O(1)O(1) 了，又因为整块数量不超过 O(n)O(\sqrt n)，所以查询整块就是 O(n)O(\sqrt n) 的；散块直接 O(n)O(\sqrt n) 暴力查即可。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> block;
		std::vector <int> belong, left, right;
		int n, len;
		
		public:
		
		Block(){}
		Block(int n, std::vector <T> &a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			block.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);
			
			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				block[belong[i]] += a[i];
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
		}
		
		void modify(int idx, T val){
			if(idx > n) return;
			a[idx] += val;
			int cur = belong[idx];
			block[cur] = 0;
			for(int i = left[cur]; i <= right[cur]; i++){
				block[cur] += a[i];
			}
		}
		
		T query(int l, int r){
			T ans = 0;
			if(belong[l] == belong[r]){
				for(int i = l; i <= r; i++) ans += a[i];
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			for(int i = l; i <= right[curl]; i++){
				ans += a[i];
			}
			for(int i = curl + 1; i < curr; i++){
				ans += block[i];
			}
			for(int i = left[curr]; i <= r; i++){
				ans += a[i];
			}
			return ans;
		} 
	};
}

时间复杂度：O(nn)O(n\sqrt n)。

T4

题意解析：给定一个长度为 nn 的数组 AA，你需要进行 nn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,c。

  • opt=0opt=0：请将 Al,...,ArA_l,...,A_r 的值加上 cc。
  • opt=1opt=1：查询 (∑j=lrAj)mod  (c+1)(\sum_{j=l}^r A_j)\mod (c+1) 的值。此时保证 c≥0c\ge 0。

T1 加强版。

考虑分块。

我们修改的时候也可以分成整块和散块。

对于整块，我们可以直接修改该块的和并打上 lazytag，等到它要分成散块时再下放；对于散块，先下放 lazytag，然后暴力修改。

查询的时候整块依旧查和就行，散块就要先下放 lazytag 然后再暴力找 AiA_i。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> block;
		std::vector <T> lazytag;
		std::vector <int> belong, left, right;
		int n, len;
		
		void push_down(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				a[i] += lazytag[idx];
			}
			lazytag[idx] = 0;
		}
		
		void push_up(int idx){
			block[idx] = 0;
			for(int i = left[idx]; i <= right[idx]; i++){
				block[idx] += a[i];
			}
		}
		
		public:
		
		Block(){}
		Block(int n, std::vector <T> &a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			block.resize(n / len + 5);
			lazytag.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);
			
			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				block[belong[i]] += a[i];
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
		}
		
		void modify(int l, int r, T val){
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++){
					a[i] += val;
				}
				push_up(belong[l]);
				return;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				a[i] += val;
			}
			for(int i = curl + 1; i < curr; i++){
				block[i] += len * val;
				lazytag[i] += val;
			}
			for(int i = left[curr]; i <= r; i++){
				a[i] += val;
			}
			push_up(curl), push_up(curr);
		}
		
		T query(int l, int r){
			T ans = 0;
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++) ans += a[i];
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				ans += a[i];
			}
			for(int i = curl + 1; i < curr; i++){
				ans += block[i];
			}
			for(int i = left[curr]; i <= r; i++){
				ans += a[i];
			}
			return ans;
		} 
	};
}

T2

题意解析：给定一个长度为 nn 的数组 AA，你需要进行 nn 次操作。每次操作给定四个数 opt,l,r,copt,l,r,c。

  • opt=0opt=0：请将 Al,...,ArA_l,...,A_r 的值加上 cc。
  • opt=1opt=1：查询在 Al,...,ArA_l,...,A_r 中，有多少个数小于 c2c^2。

考虑分块。

先思考不带修改怎么做。

我们把 AA 数组分为 O(n)O(\sqrt n) 个块，我们将每个块内的元素从小到大排序。查询时我们对整块进行 lower_bound，两边的小块暴力查找即可。O(nnlog⁡n)O(n\sqrt{n}\log n)。

注意到修改整块对整块的顺序不影响，不需要重新排序，直接打 lazytag 即可，查询带 lazytag 查就行。散块先下放 lazytag（其实不下放也行），然后暴力修改 AiA_i，最后 sort 排序即可。

注意查询的常数比修改的常数大很多，所以需要调整块长。经测试在块长为 250250 时可以跑进 3.57s3.57s。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> b;
		std::vector <T> lazytag;
		std::vector <int> belong, left, right;
		int n, len;

		void push_down(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				a[i] += lazytag[idx];
			}
			lazytag[idx] = 0;
		}

		void push_up(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				b[i] = a[i];
			}
			std::sort(b.begin() + left[idx], b.begin() + right[idx] + 1);
		}

		public:

		Block(){}
		Block(int n, std::vector <T> &a){
			this -> n = n;
			len = 250;
			this -> a.resize(n + 5);
			b.resize(n + 5);
			lazytag.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);

			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				b[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
			for(int i = 1; left[i]; i++){
				std::sort(b.begin() + left[i], b.begin() + right[i] + 1);
			}
		}

		void modify(int l, int r, T val){
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++){
					a[i] += val;
				}
				push_up(belong[l]);
				return;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				a[i] += val;
			}
			for(int i = curl + 1; i < curr; i++){
				lazytag[i] += val;
			}
			for(int i = left[curr]; i <= r; i++){
				a[i] += val;
			}
			push_up(curl), push_up(curr);
		}

		T query(int l, int r, T val){
			T ans = 0;
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				push_up(belong[l]);
				for(int i = l; i <= r; i++){
					if(a[i] < val) ans++;
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			push_up(curl), push_up(curr);
			for(int i = l; i <= right[curl]; i++){
				if(a[i] < val) ans++;
			}
			for(int i = curl + 1; i < curr; i++){
				int idx = lower_bound(b.begin() + left[i], b.begin() + right[i] + 1, val - lazytag[i]) - b.begin() - 1;
				ans += idx - left[i] + 1;
			}
			for(int i = left[curr]; i <= r; i++){
				if(a[i] < val) ans++;
			}
			return ans;
		}
	};
}

时间复杂度：O(nnlog⁡n)O(n\sqrt n\log n)。

Bonus：尝试以 O(nnlog⁡n)O(n\sqrt{n\log n}) 的时间复杂度通过该题。

T3

和 T2 差不多，不讲。代码见我的板子。

T5

题意解析：给定一个长度为 nn 的数组 AA，你需要进行 nn 次操作。每次操作给定三个数 opt,l,ropt,l,r。

  • opt=0opt=0：请将 Al,...,ArA_l,...,A_r 的值都变为原先的值的根号。
  • opt=1opt=1：查询 (∑j=lrAj)(\sum_{j=l}^r A_j) 的值。

考虑分块。

首先我们注意到每个 AiA_i 被开 log⁡log⁡Ai\log\log A_i 次根就变为 11 了，所以其实能影响答案的单点改也就那么几次，后面的修改就相当于木棍木棍的中间两个字了。

思考如何判断某些修改是无效的。

显然对于一个块，AiA_i 均小于等于 11，即 ∑j=lrAi≤len\sum_{j=l}^r A_i\le len，那这个块的所有修改就都是无效的。我们遇到无效的修改就跳过，有效的就直接暴力修。显然，根据刚才的结论，每个块最多只会被修改 O(log⁡log⁡V)O(\log\log V) 次。对于散块，那还说啥了，直接暴力即可。

查询时和 T1 一样查就行。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> block;
		std::vector <int> belong, left, right;
		int n, len;
		
		void push_up(int idx){
			block[idx] = 0;
			for(int i = left[idx]; i <= right[idx]; i++){
				block[idx] += a[i];
			}
		}

		public:

		Block(){}
		Block(int n, std::vector <T> &a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			block.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);

			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				block[belong[i]] += a[i];
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
		}

		void modify(int l, int r){
			if(belong[l] == belong[r]){
				for(int i = l; i <= r; i++){
					a[i] = sqrtl(a[i]);
				}
				push_up(belong[l]);
				return;
			}
			int curl = belong[l], curr = belong[r];
			for(int i = l; i <= right[curl]; i++){
				a[i] = sqrtl(a[i]);
			}
			for(int i = curl + 1; i < curr; i++){
				if(block[i] <= len) continue;// 何意味 
				for(int j = left[i]; j <= right[i]; j++){
					a[j] = sqrtl(a[j]);
				}
				push_up(i);
			}
			for(int i = left[curr]; i <= r; i++){
				a[i] = sqrtl(a[i]);
			}
			push_up(curl), push_up(curr);
		}

		T query(int l, int r){
			T ans = 0;
			if(belong[l] == belong[r]){
				for(int i = l; i <= r; i++){
					ans += a[i];
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			for(int i = l; i <= right[curl]; i++){
				ans += a[i];
			}
			for(int i = curl + 1; i < curr; i++){
				ans += block[i];
			}
			for(int i = left[curr]; i <= r; i++){
				ans += a[i];
			}
			return ans;
		}
	};
}

时间复杂度：O(nn+nlog⁡log⁡V)O(n\sqrt n+n\log\log V)。

T6

题意解析：给定一个初始长度为 nn 的数组 AA，你需要进行 nn 次操作。每次操作给定？个数 opt,...opt,...。

  • opt=0opt=0：给定三个数 opt,l,ropt,l,r，请在 AlA_l 前面插入一个数 rr。
  • opt=1opt=1：给定两个数 opt,copt,c，查询 AcA_c 的值。

数据随机生成。

考虑分块。

我们把 AA 数组分成 O(n)O(\sqrt n) 块，每块是一个 vector，记录块内的元素。修改先找大块，如果 AlA_l 位于这个块，就直接 insert；不在的话继续往下找。查询和插入同理。由于数据随机生成，所以这种做法每个块期望长度依然是 O(n)O(\sqrt n)，时间复杂度也是 O(nn)O(n\sqrt n)。

但是，注意到如果块长占比过大，那么随机选点落到它的概率就更大，这样它的块长也更大……所以，为了减少这种恶性循环的危害，建议将块长调小一点。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <std::vector <T>> a;
		std::vector <T> lazytag;
		std::vector <int> belong, left, right;
		int n, len;

		public:

		Block(){}
		Block(int n, std::vector <T> a){
			this -> n = n;
			len = 0.3 * sqrtl(n) + 1;
			this -> a.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);

			for(int i = 1; i <= n; i++){
				belong[i] = (i - 1) / len + 1;
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
			for(int i = 1; left[i]; i++){
				for(int j = left[i]; j <= right[i]; j++){
					this -> a[i].push_back(a[j]);
				}
			}
		}

		void insert(int idx, T val){
			int cur = 0;
			for(int i = 1; left[i]; i++){
				if(int(cur + a[i].size()) < idx){
					cur += a[i].size();
					continue;
				}
				a[i].insert(a[i].begin() + idx - cur - 1, val);
				return;
			}
		}

		T query(int idx){
			int cur = 0;
			for(int i = 1; left[i]; i++){
				if(int(cur + a[i].size()) < idx){
					cur += a[i].size();
					continue;
				}
				return a[i][idx - cur - 1];
			}
			return -1;
		}
	};
}

时间复杂度：O(nn)O(n\sqrt n)。

T7

和 T4 一样，不写。

userId_undefined
去预览
0/2000

全部评论 1

热门讨论