线段树区间更新

难点1：当整个区间发生更新时，这样的更新这个区间带来的影响是什么
难点2：区间发生更新时，不但区间要发生更新还有 $lazy$ 的变化

线段树2

代码长了，千万不能用记性去记代码

区间乘法 $*v$：$sumv[id] *= v, lazy\_add[id] *=v, lazy\_mul[id] *= v$
区间加法 $+v$：$sumv[id] += (r - l + 1) * v, lazy\_add[id] += v;$
区间赋值 $v$：$sumv[id] = (r-l+1)*v,lazy\_modify[id] = v, lazy\_add[id]=0,lazy\_mul[id]=1$

     add   mul
      0     1
 +1   1     1
 *2   2     2
 +3   5     2
 *4   20    8

对于 +x 操作： add + x
对于 *y 操作： add * y, mul * y

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
long long n, m, MOD;
long long sumv[4 * maxn];
long long lazy_add[4 * maxn];
long long lazy_mul[4 * maxn];
long long a[maxn];
void pushup(int id){
	sumv[id] = (sumv[id * 2] + sumv[id * 2 + 1]) % MOD;	
}
void pushdown(int id, int l, int r){
	// 根据规律由于我们在update已经修改了lazy
	// 所以先 * 再 + 
	if (lazy_add[id] == 0 && lazy_mul[id] == 1) return;
	//先更新左区间
	int mid = (l + r) / 2;
	sumv[id * 2] = (sumv[id * 2] * lazy_mul[id]) % MOD;
	sumv[id * 2] = (sumv[id * 2] + lazy_add[id] * (mid - l + 1) % MOD) % MOD;
	lazy_add[id * 2] = lazy_add[id * 2] * lazy_mul[id] % MOD;
	lazy_add[id * 2] = (lazy_add[id * 2] + lazy_add[id]) % MOD;
	lazy_mul[id * 2] = lazy_mul[id * 2] * lazy_mul[id] % MOD;
	//再更新右区间
	sumv[id * 2 + 1] = (sumv[id * 2 + 1] * lazy_mul[id]) % MOD;
	sumv[id * 2 + 1] = (sumv[id * 2 + 1] + lazy_add[id] * (r - mid) % MOD) % MOD;
	lazy_add[id * 2 + 1] = lazy_add[id * 2 + 1] * lazy_mul[id] % MOD;
	lazy_add[id * 2 + 1] = (lazy_add[id * 2 + 1] + lazy_add[id]) % MOD;
	lazy_mul[id * 2 + 1] = lazy_mul[id * 2 + 1] * lazy_mul[id] % MOD;
	//清空 lazy
	lazy_add[id] = 0;
	lazy_mul[id] = 1;
}
void build(int id, int l, int r){
	lazy_add[id] = 0;
	lazy_mul[id] = 1;
	if (l == r){
		sumv[id] = a[l];
		return;	
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	pushup(id);
}
void update_mul(int id, int l, int r, int x, int y, long long v){
	if (x <= l && r <= y){
		sumv[id] = sumv[id] * v % MOD;
		lazy_add[id] = lazy_add[id] * v % MOD;
		lazy_mul[id] = lazy_mul[id] * v % MOD;
		return;	
	}	
	pushdown(id, l, r);
	int mid = (l + r) / 2;
	if (x <= mid){
		update_mul(id * 2, l, mid, x, y, v);	
	}
	if (y > mid){
		update_mul(id * 2 + 1, mid + 1, r, x, y, v);	
	}
	pushup(id);
}
void update_add(int id, int l, int r, int x, int y, long long v){
	if (x <= l && r <= y){
		sumv[id] = (sumv[id] + (r - l + 1) * v % MOD) % MOD;
		lazy_add[id] = (lazy_add[id] + v) % MOD;
		return;	
	}	
	pushdown(id, l, r);
	int mid = (l + r) / 2;
	if (x <= mid){
		update_add(id * 2, l, mid, x, y, v);	
	}
	if (y > mid){
		update_add(id * 2 + 1, mid + 1, r, x, y, v);	
	}
	pushup(id);
}
long long query(int id, int l, int r, int x, int y){
	if (x <= l && r <= y){
		return sumv[id];	
	}	
	pushdown(id, l, r);
	int mid = (l + r) / 2;
	long long ans = 0;
	if (x <= mid){
		ans += query(id * 2, l, mid, x, y);
		ans %= MOD;
	} 
	if (y > mid){
		ans += query(id * 2 + 1, mid + 1, r, x, y);
		ans %= MOD;
	}
	return ans;
}
int main(){
	scanf("%lld%lld%lld", &n, &m, &MOD);
	for (int i = 1; i <= n; ++i){
		scanf("%lld", &a[i]);	
	}
	build(1, 1, n);
	while (m--){
		int op, x, y;
		long long z;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1){
			scanf("%lld", &z);
			update_mul(1, 1, n, x, y, z);
		} else if (op == 2){
			scanf("%lld", &z);
			update_add(1, 1, n, x, y, z);
		} else {
			printf("%lld\n", query(1, 1, n, x, y));
		}
	}
	return 0;	
}

相同的数字

同时枚举 $l,r$ 肯定是超时的
那么优化思路：思考如何减少枚举数量，思考有没有办法枚举 $l$ 的情况下快速找到对应的 $r$，或者是枚举 $r$ 的情况下快速找到 $l$
一般考虑的是枚举右端点找左端点

二分答案 $mid$，那么就有了一个预设值
$check(mid)$ 判断是否存在一个区间满足 $x/y <= mid$

如何判断是否存在一个区间满足 $x/y <= mid?$

$siz[l,r] / (r-l+1) <= mid$
$siz[l,r] <= mid * (r-l+1)$
$siz[l,r] <= mid * r - mid * l + mid$
$siz[l,r] + mid *l <= mid * (r + 1)$

所以问题回到了：枚举 $r$，判断是否存在一个 $l$ 满足以上式子

void build(int id, int l, int r, double mid){
	if (l == r){
		minv[id] = mid * l;
		return;	
	}
}

二分答案 mid
bool check(double mid){
	build(1, 1, n, mid);
	//ed[i]表示i最后一次出现的下标
	memset(ed, 0, sizoef(ed));
	for (int r = 1; r <= n; ++r){
		//把siz数组中 ed[a[i]] + 1 到 i 整体 +1
		update_add(1, 1, n, ed[a[r]] + 1, r, 1);	
		if (query(1, 1, n, 1, r) <= mid * (r + 1)){
			return true;
		}
		ed[a[r]] = r;
	}
	return false;
}