梦熊十三联测 A题 加减乘除

这道题放在了T1.本来以为挺简单的，结果愣是卡了我1小时，还没做出来，先ko了T3，才把这道题的暴力写了写，拿了40pts

这道题总的来说思路挺简单的，就是没想出来，看思路吧：

我们能注意到，给的两类操作并不会改变单调性：队以仁义的x≤y，在操作后仍然满足x`≤y`

我们将原序列升序排列，可以分别二分出最大和最小的下标

时间复杂度O(n logmax|Ai| )

为了防止超时可以开__int128

下面是暴力代码（40pts）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
long long  read() {
	long long  x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
		x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
int n, q, l, r, ans;
int a[N];
signed main() {
	freopen("arithmetic.in", "r", stdin);
	freopen("arithmetic.out", "w", stdout);
	n = read(), q = read(), l = read(), r = read();
	for (int i = 1; i <= n; i++) {
		a[i] = read();
	}
	while (q--) {
		int opt, x, s, t;
		opt = read(), x = read(), s = read(), t = read();
		if (opt == 1) {
			for (int i = 1; i <= n; i++) {
				if (a[i] >= x) {
					a[i] = (a[i] + s) * t;
				}
			}
		} else {
			for (int i = 1; i <= n; i++) {
				if (a[i] <= x) {
					a[i] = (a[i] - s) / t;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] >= l && a[i] <= r) ans++;
	}
	printf("%lld", ans);
	return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef __int128 i128;
int n, q, qry[200010][4], a[200010], L, R;
i128 foo(int x) {
	i128 ans = x;
	for (int i = 1; i <= q; i++) {
		if (qry[i][0] == 1 && ans >= qry[i][1])
			ans = (ans + qry[i][2]) * qry[i][3];
		if (qry[i][0] == 2 && ans <= qry[i][1])
			ans = (ans - qry[i][2]) / qry[i][3];
	}
	return ans;
}
signed main() {
	freopen("arithmetic.in", "r", stdin);
	freopen("arithmetic.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> q >> L >> R;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= q; i++) cin >> qry[i][0] >> qry[i][1] >> qry[i][2] >> qry[i][3];
	int l = 1, r = n, ans = n + 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		i128 x = foo(a[mid]);
		if (L <= x) {
			ans = mid;
			r = mid - 1;
		} else
			l = mid + 1;
	}
	int sws = 0;
	l = 1, r = n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		i128 x = foo(a[mid]);
		if (x <= R) {
			sws = mid;
			l = mid + 1;
		} else
			r = mid - 1;
	}
	if (ans > sws)
		puts("0");
	else
		printf("%lld\n", sws - ans + 1);
	return 0;
}