梦熊十三联测 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;
}