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

---

T1

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

• $opt=0$：请将 $A_l,...,A_r$ 的值加上 $c$。
• $opt=1$：查询 $A_r$ 的值。

考虑分块。

考虑转化成差分数组，$B_i$ 记录 $A_i-A_{i-1}$ 的值。这样操作 $0$ 转化成将 $B_l$ 加 $c$，$B_{r+1}$ 减 $c$；操作 $1$ 转化成 $\sum_{j=1}^r B_j$。

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

我们修改时 $O(\sqrt n)$ 暴力维护每一块的和（可以 $O(1)$ 但是没必要），这样查询时中间每一个整块就可以 $O(1)$ 了，又因为整块数量不超过 $O(\sqrt n)$，所以查询整块就是 $O(\sqrt 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(n\sqrt n)$。

---

T4

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

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

T1 加强版。

考虑分块。

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

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

查询的时候整块依旧查和就行，散块就要先下放 lazytag 然后再暴力找 $A_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

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

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

考虑分块。

先思考不带修改怎么做。

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

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

注意查询的常数比修改的常数大很多，所以需要调整块长。经测试在块长为 $250$ 时可以跑进 $3.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(n\sqrt n\log n)$。

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

---

T3

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

---

T5

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

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

考虑分块。

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

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

显然对于一个块，$A_i$ 均小于等于 $1$，即 $\sum_{j=l}^r A_i\le len$，那这个块的所有修改就都是无效的。我们遇到无效的修改就跳过，有效的就直接暴力修。显然，根据刚才的结论，每个块最多只会被修改 $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(n\sqrt n+n\log\log V)$。

---

T6

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

• $opt=0$：给定三个数 $opt,l,r$，请在 $A_l$ 前面插入一个数 $r$。
• $opt=1$：给定两个数 $opt,c$，查询 $A_c$ 的值。

数据随机生成。

考虑分块。

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

---

T7

和 T4 一样，不写。

---

T8

题意解析：给定一个长度为 $n$ 的数组 $A$，你需要进行 $n$ 次操作。每次操作给定三个数 $l,r,c$。

请查询 $A_l,...,A_r$ 内一个数内元素为 $c$ 的个数，并将区间所有元素改为 $c$。

考虑分块。

我们把 $A$ 数组分成 $\sqrt n$ 个块，设置 lazytag 为当前块内所有元素为一个相同的值 $k$（如果不同则 $k=-1$），这样如果遇到 $k\not= -1$ 的块就可以直接改 lazytag 了，否则就暴力。显然这样如果不算一开始的元素的话，单次操作是 $O(\sqrt n)$ 的。而一开始的元素也只会查询 $O(n)$ 次，所以总时间复杂度还是 $O(n\sqrt n)$。

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

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

		public:

		Block(){}
		Block(int n, std::vector <T> a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			lazytag.resize(n / len + 5, -1);
			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;
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
		}

		int query(int l, int r, T val){
			int ans = 0;
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++){
					if(a[i] == val) ans++;
					a[i] = val;
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				if(a[i] == val) ans++;
				a[i] = val;
			}
			for(int i = curl + 1; i < curr; i++){
				if(lazytag[i] != -1){
					if(lazytag[i] == val) ans += len;
					lazytag[i] = val;
					continue;
				}
				for(int j = left[i]; j <= right[i]; j++){
					if(a[j] == val) ans++;
					a[j] = val;
				}
				lazytag[i] = val;
			}
			for(int i = left[curr]; i <= r; i++){
				if(a[i] == val) ans++;
				a[i] = val;
			}
			return ans;
		}
	};
}

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

---

T9

题意解析：给定一个长度为 $n$ 的数组 $A$，你需要进行 $n$ 次操作。每次操作给定两个数 $l,r$。

请查询 $A_l,...,A_r$ 中的最小众数。

考虑分块。

首先我们可以 $O(n)$ 递推求出 $[i,i],[i,i+1],[i,i+2],...,[i,n]$ 的最小众数。所以我们可以 $O(n\sqrt n)$ 求出 $[\sqrt n,\sqrt n]$，$[\sqrt n,2\sqrt n],[\sqrt n,3\sqrt n],...,[\sqrt n,n],[2\sqrt n,2\sqrt n],[2\sqrt n,3\sqrt n],...,[n,n]$ 的最小众数。记录下来。

然后我们 $O(n\sqrt n)$ 预处理每个块每个元素的个数，然后做前缀和。

每一个查询还是分成整块和散块。整块的话直接查表。

我们枚举散块的每一个元素，显然不超过 $2\sqrt n$ 个。我们可以通过查表找到整块内它们出现的个数，然后暴力统计散块内出现的个数，更新答案。

namespace cjdst{
    template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <std::vector <T>> bucket;
		std::vector <T> tmpbucket;
		std::vector <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 = 1500;
			this -> a.resize(n + 5);
			block.resize(n / len + 5, std::vector <T>(n / len + 5));
			bucket.resize(n / len + 5, std::vector <T>(n + 5));
			tmpbucket.resize(n + 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;
				bucket[belong[i]][a[i]]++;
				right[belong[i]] = i;
				if(!left[belong[i]]){
					for(int j = 1; j <= n; j++){
						bucket[belong[i]][j] += bucket[belong[i - 1]][j];
					}
					left[belong[i]] = i;
				}
			}
			for(int i = 1; left[i]; i++){
				std::vector <int> b(n + 5, 0);
				T cur = -1;
				for(int j = i; left[j]; j++){
					for(int k = left[j]; k <= right[j]; k++){
						b[a[k]]++;
						if(cur == -1 || b[a[k]] > b[cur] || (b[a[k]] == b[cur] && a[k] < cur)) cur = a[k];
					}
					block[i][j] = cur;
				}
			}
		}

		T query(int l, int r){
			T ans = -1;
			if(belong[r] - belong[l] <= 1){
				for(int i = l; i <= r; i++){
					tmpbucket[a[i]]++;
					if(ans == -1 || tmpbucket[ans] < tmpbucket[a[i]] || (tmpbucket[ans] == tmpbucket[a[i]] && ans > a[i])) ans = a[i];
				}
				for(int i = l; i <= r; i++){
					tmpbucket[a[i]]--;
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			ans = block[curl + 1][curr - 1];
			for(int i = l; i <= right[curl]; i++){
				tmpbucket[a[i]]++;
			}
			for(int i = left[curr]; i <= r; i++){
				tmpbucket[a[i]]++;
			}
			
			for(int i = l; i <= right[curl]; i++){
				int times1 = tmpbucket[a[i]] + bucket[curr - 1][a[i]] - bucket[curl][a[i]];
				int times2 = tmpbucket[ans] + bucket[curr - 1][ans] - bucket[curl][ans];
				if(times1 > times2 || (times1 == times2 && ans > a[i])){
					ans = a[i];
				}
			}
			for(int i = left[curr]; i <= r; i++){
				int times1 = tmpbucket[a[i]] + bucket[curr - 1][a[i]] - bucket[curl][a[i]];
				int times2 = tmpbucket[ans] + bucket[curr - 1][ans] - bucket[curl][ans];
				if(times1 > times2 || (times1 == times2 && ans > a[i])){
					ans = a[i];
				}
			}
			
			for(int i = l; i <= right[curl]; i++){
				tmpbucket[a[i]]--;
			}
			for(int i = left[curr]; i <= r; i++){
				tmpbucket[a[i]]--;
			}
			return ans;
		}
		
		void test(std::vector <T> &b){
			for(int i = 1; left[i]; i++){
				for(int j = 1; left[j]; j++){
					std::cout << i << ' ' << j << ' ' << b[block[i][j]] << '\n';
				}
			}
			std::cout.flush();
		}
	};
}

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