QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736046 | #9543. Good Partitions | ucup-team1412 | RE | 3ms | 9540kb | C++23 | 3.2kb | 2024-11-11 23:49:45 | 2024-11-11 23:49:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll maxn = 1e5 + 10;
const ll inf = 3e9;
vector<ll> loc;
ll aa[maxn];
ll n, q;
ll yinzi[maxn];
ll sum[maxn << 2];
ll add[maxn << 2];
ll gcd(ll x, ll y) {
return y == 0 ? x : gcd(y, x % y);
}
void push_up(ll rt) {
sum[rt] = gcd(sum[rt << 1], sum[rt << 1 | 1]);
}
// void push_down(ll rt, ll l, ll r) {
// if (add[rt]) {
// add[rt << 1] = gcd(add[rt << 1], add[rt]);
// add[rt << 1 | 1] = gcd(add[rt << 1 | 1], add[rt]);
// sum[rt << 1] = gcd(sum[rt << 1], add[rt]);
// sum[rt << 1 | 1] == gcd(sum[rt << 1 | 1], add[rt]);
// add[rt] = 0;
// }
// }
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
void build(ll l, ll r, ll rt) {
// add[rt] = 0;
if (l == r) {
if (aa[l] > aa[l + 1]) sum[rt] = l;
else sum[rt] = 0;
return;
}
ll mid = (l + r) >> 1;
build(lson);
build(rson);
push_up(rt);
}
void update(ll l, ll r, ll c, ll pos, ll rt) {
ll mid = (l + r) >> 1;
if (l == r) {
sum[rt] = c;
return;
}
if (pos <= mid) update(l, mid, c, pos, rt << 1);
else update(r, mid + 1, c, pos, rt << 1 | 1);
push_up(rt);
}
ll query(ll a, ll b, ll l, ll r, ll rt) {
if (a <= l && b >= r)
return sum[rt];
// push_down(rt, l, r);
ll mid = (l + r) >> 1;
ll ans = 0;
if (a <= mid)
ans = gcd(ans, query(a, b, lson));
if (b > mid)
ans = gcd(ans, query(a, b, rson));
return ans;
}
vector<ll> pri;
bool not_prime[maxn];
ll d[maxn], num[maxn];
void pre(ll n) {
d[1] = 1;
for (ll i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
d[i] = 2;
num[i] = 1;
}
for (ll pri_j : pri) {
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
num[i * pri_j] = num[i] + 1;
d[i * pri_j] = d[i] / num[i * pri_j] * (num[i * pri_j] + 1);
break;
}
num[i * pri_j] = 1;
d[i * pri_j] = d[i] * 2;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cout << gcd(6, 9) << ' ' << gcd(3, 18) << ' ' << gcd(1, 189);
ll t;
cin >> t;
pre(maxn);
while (t--) {
cin >> n >> q;
for (ll i = 1; i <= n; i++) {
cin >> aa[i];
}
aa[n + 1] = inf;
build(1, n, 1);
ll ans = query(1, n, 1, n, 1);
if (ans == 0) ans = n;
else ans = d[ans];
cout << ans << endl;
while (q--) {
ll x, y;
cin >> x >> y;
if (y > aa[x + 1])update(1, n, x, x, 1);
else update(1, n, 0, x, 1);
if (aa[x - 1] > y)update(1, n, x - 1, x - 1, 1);
else if (x > 1) update(1, n, 0, x - 1, 1);
ans = query(1, n, 1, n, 1);
if (ans == 0) ans = n;
else ans = d[ans];
cout << ans << endl;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 9540kb
input:
1 5 2 4 3 2 6 1 2 5 3 5
output:
1 2 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 8220kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: -100
Runtime Error
input:
1 200000 200000 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...