差分总结一 技巧和思维

P1083 借教室

https://www.luogu.org/problem/P1083
二分位置 我们可以用差分数组 确定每天用多少教室

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;

int n, m;
int a[maxn], d[maxn];
int s[maxn], t[maxn], b[maxn];

bool chk(int x) {
	memset(d, 0, sizeof d);
	for(int i = 1; i <= x; i ++) 
		d[s[i]] += b[i], d[t[i] + 1] -= b[i];
	for(int i = 1; i <= n; i ++) {
		d[i] = d[i - 1] + d[i];
		if(d[i] > a[i]) return 0;
	}
	return 1;
}

int main() {
	scanf("%d %d", &n ,&m);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i ++) scanf("%d %d %d", &b[i], &s[i], &t[i]);
	int l = 0, r = n;
	while(l < r) {
// cout << l << " " << r << endl;
		int mid = l + r + 1 >> 1;
		if(chk(mid)) l = mid;
		else r = mid - 1;
	} 
	if(l != n) printf("-1\n%d\n", l + 1);
	else puts("0");
	return 0;
}

AT2442 フェーン現象 (Foehn Phenomena)

https://www.luogu.org/problem/AT2442

根据海拔差,我们又可以求出每个位置的温度.由于n位置不会变,且一直为最后一个位置.
所以我们可以累加ans.(因为最后一个位置n永远不会变。
而且考虑到某一段区间的海拔变化,相对位置不会变,我们只需要考虑从起始位置l的温度变化,后面到达r的温度就随之变化.
这里需要注意的位置就是当r==n的时候,是不需要变化r+1位置的海拔与温度的.

差分数组 是线性的
我们输入的时候 就可以求到n位置温度
之后我们区间改 也是再差分数组 单点改 对最后求和的影响 只要 单点处理
剪掉 把新的重新加进来 注意r == n 不需要处理

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
#define int long long 
int n, q, s, t;
int a[maxn];

int getval(int x) {
	return x > 0 ? -x * s : -x * t;
}

signed main() {
	scanf("%lld %lld %lld %lld", &n, &q, &s, &t);
	int ans = 0;
	int last = 0;
	for(int i = 0, x; i <= n; i ++) {
		scanf("%lld", &x);
		if(i >= 1) {
			a[i] = x - last;
			last = x;
			ans += getval(a[i]);
		}
	}
	for(int i = 1, l, r, y; i <= q; i ++) {
		scanf("%lld %lld %lld", &l, &r, &y);
		ans -= getval(a[l]);
		a[l] += y;
		ans += getval(a[l]);
		if(r != n) 
			ans -= getval(a[r + 1]), a[r + 1] -= y, ans += getval(a[r + 1]);
		printf("%lld\n", ans);
	}
	return 0;
}

P3948 数据结构

https://www.luogu.org/problem/P3948
最开始的数组每个元素都是0
给出nn，optopt，modmod，minmin，maxmax，modmod在int范围内
操作AA，QQ
AA: LL,RR,XX 表示把[l,R][l,R]这个区间加上XX
（数组的从L到R的每个元素都加上X）
QQ: LL,RR 表示询问[L,R][L,R]这个区间中元素T满足 min<=(Timin<=(T∗i%mod)<=maxmod)<=max 的 T这样的数的个数（i是数组下标）
（元素的值数组下标%mod在min到max范围内）

查询只有 1000 组 然后 题解就给了暴力做法

这个题作为考试的第一题，是个心态题。
所谓的树状数组和线段树都是不存在的。
实际上只需暴力轻松解决。
首先暴力有66~70分。
对于Final操作
然后，类似前缀和，记录下来这个位置之前有几个满足条件的数的个数 ，这样有88~90分。
因为修改多，查询少，如果可以优化修改操作就可以AC了，显然上个差分
O(1)修改，差分维护数组，区间加的时候 a[L]+=x,a[R]-=x
总复杂度O(n*1000) （1000次修改），拿到100分

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
#define int long long

int n, m, opt, mod, mi, ma, l, r, x;
int a[maxn], sum[maxn];
char s[10];

signed main() {
	scanf("%lld %lld %lld %lld %lld", &n, &opt, &mod, &mi, &ma);
	for(int i = 1; i <= opt; i ++) {
		scanf("%s %d %d", s, &l, &r);
		if(s[0] == 'A') {
			scanf("%lld", &x);
			a[l] += x, a[r + 1] -= x;
		} else {
			int now = 0, ans = 0;
			for(int i = 1; i <= r; i ++) {
				now += a[i];
				int tmp = now * i % mod;
				if(i >= l && tmp >= mi && tmp <= ma) ans ++;
			}
			printf("%lld\n", ans);
		}
	}
	int now = 0;
	for(int i = 1; i <= n; i ++) {
		now += a[i];
		int tmp = now * i % mod;
		if(tmp >= mi && tmp <= ma) sum[i] = sum[i - 1] + 1;
		else sum[i] = sum[i - 1];
	}
	scanf("%d", &m);
	while(m --) {
		scanf("%d %d", &l, &r);
		printf("%d\n", sum[r] - sum[l - 1]);
	}
	return 0;
}