QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #769676 | #9543. Good Partitions | Aestas16 | RE | 34ms | 12936kb | C++14 | 9.6kb | 2024-11-21 18:55:52 | 2024-11-21 18:55:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> void fr(T &a, bool f = 0, char ch = getchar()) {
for (a = 0; ch < '0' || ch > '9'; ch = getchar()) (ch == '-') && (f = 1);
for (; ch >= '0' && ch <= '9'; ch = getchar()) a = (a * 10) + (ch - '0');
f && (a = -a);
}
template <class T, class ...Y> void fr(T &a, Y &...b) { fr(a), fr(b...); }
int fr() { int a; return fr(a), a; }
const int N = 4e5;
int n, a[N + 10], d[N + 10];
mt19937 rnd((unsigned long long)(new char));
struct Node {
int val, rndval, gcd, sz;
Node *ch[2];
void pushup() { gcd = __gcd(val, __gcd(ch[0]->gcd, ch[1]->gcd)); }
} mem[N + 10], *atot, *rt, *null;
void Init() { atot = mem, null = atot, null->ch[0] = null->ch[1] = null, rt = null; }
Node *newNode(int val) { return atot++, atot->ch[0] = atot->ch[1] = null, atot->val = atot->gcd = val, atot->sz = 1, atot->rndval = rnd(), atot; }
void splitval(Node *u, int val, Node *&x, Node *&y) {
if (u == null) return x = y = null, void();
if (u->val <= val) x = u, splitval(u->ch[1], val, u->ch[1], y);
else y = u, splitval(u->ch[0], val, x, u->ch[0]);
u->pushup();
}
Node *merge(Node *x, Node *y) {
if (x == null || y == null) return (x == null) ? y : x;
if (x->rndval < y->rndval) return x->ch[1] = merge(x->ch[1], y), x->pushup(), x;
return y->ch[0] = merge(x, y->ch[0]), y->pushup(), y;
}
void erase(int val) {
// printf("erase(%d)\n", val);
Node *x, *y, *z;
splitval(rt, val, y, z);
splitval(y, val - 1, x, y);
y = merge(y->ch[0], y->ch[1]);
rt = merge(merge(x, y), z);
}
void insert(int val) {
// printf("insert(%d)\n", val);
Node *x, *y;
splitval(rt, val, x, y);
rt = merge(merge(x, newNode(val)), y);
// rt = merge(rt, newNode(val));
}
void print(Node *u) {
if (u == null) return ;
print(u->ch[0]), printf("val = %d gcd = %d\n", u->val, u->gcd), print(u->ch[1]);
}
signed main() {
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i) d[j]++;
for (int _ = fr(), q; _--;) {
Init();
fr(n, q);
for (int i = 1; i <= n; i++) fr(a[i]);
set<int> s;
s.insert(0);
for (int i = 1; i < n; i++)
if (a[i] > a[i + 1]) {
insert(i - *s.rbegin());
s.insert(i);
}
s.insert(n);
if (rt->gcd == 0) printf("%d\n", n);
else printf("%d\n", d[rt->gcd]);
for (int __ = 1, pos, val; __ <= q; __++) {
fr(pos, val);
a[pos] = val;
if (n == 1) { puts("1"); continue; }
auto it = s.lower_bound(pos);
// printf("*it = %d\n", *it);
if (pos == 1) {
if (*it == pos) {
if (a[pos] <= a[pos + 1]) {
int l = *prev(it), r = *it;
erase(pos - l);
if (r != n) erase(r - pos);
if (r != n) insert(r - l);
s.erase(pos);
}
} else {
if (a[pos] > a[pos + 1]) {
int l = *prev(it), r = *it;
if (r != n) erase(r - l);
insert(pos - l);
if (r != n) erase(r - pos);
s.insert(pos);
}
}
} else if (pos == n) {
if (*prev(it) == pos - 1) {
if (a[pos - 1] <= a[pos]) {
int l = *prev(prev(it)), r = *it;
// l, pos - 1, r
if (r != n) erase(r - pos + 1);
erase(pos - l - 1);
if (r != n) insert(r - l);
s.erase(pos - 1);
}
} else {
if (a[pos - 1] > a[pos]) {
int l = *prev(it), r = *it;
if (r != n) erase(r - l);
insert(pos - 1 - l);
if (r != n) insert(r - pos + 1);
s.insert(pos - 1);
}
}
} else {
if (*it == pos) {
if (*prev(it) == pos - 1) {
if (a[pos - 1] <= a[pos] && a[pos] <= a[pos + 1]) {
int l = *prev(prev(it)), r = *next(it);
// l, pos - 1, pos, r
erase(pos - l - 1), erase(1);
if (r != n) erase(r - pos);
if (r != n) insert(r - l);
s.erase(pos - 1), s.erase(pos);
} else if (a[pos - 1] <= a[pos]) {
int l = *prev(prev(it)), r = *it;
// l, pos - 1, r
// puts("qwq");
// printf("pos = %d l = %d r = %d\n", pos, l, r);
erase(pos - l - 1);
if (r != n) erase(r - pos + 1);
if (r != n) insert(r - l);
s.erase(pos - 1);
} else if (a[pos] <= a[pos + 1]) {
int l = *prev(it), r = *next(it);
erase(pos - l);
if (r != n) erase(r - pos);
if (r != n) insert(r - l);
s.erase(pos);
}
} else {
if (a[pos] <= a[pos + 1] && a[pos - 1] > a[pos]) {
// l, pos, r ----> l, pos - 1, r
int l = *prev(it), r = *next(it);
erase(pos - l);
if (r != n) erase(r - pos);
insert(pos - l - 1);
if (r != n) insert(r - pos + 1);
s.erase(pos), s.insert(pos - 1);
} else if (a[pos] <= a[pos + 1]) {
int l = *prev(it), r = *next(it);
erase(pos - l);
if (r != n) erase(r - pos);
if (r != n) insert(r - l);
s.erase(pos);
} else if (a[pos - 1] > a[pos]) {
int l = *prev(it), r = *it;
// l, pos, r ----> l, pos - 1, pos, r
erase(pos - l);
insert(1), insert(pos - l - 1);
s.insert(pos - 1);
}
}
} else {
if (*prev(it) == pos - 1) {
if (a[pos] > a[pos + 1] && a[pos - 1] <= a[pos]) {
int l = *prev(prev(it)), r = *it;
// l, pos - 1, r ----> l, pos, r
erase(pos - l - 1);
if (r != n) erase(r - pos + 1);
insert(pos - l);
if (r != n) insert(r - pos);
s.erase(pos - 1), s.insert(pos);
} else if (a[pos - 1] <= a[pos]) {
int l = *prev(prev(it)), r = *it;
erase(pos - l - 1);
if (r != n) erase(r - pos + 1);
if (r != n) insert(r - l);
s.erase(pos - 1);
} else if (a[pos] > a[pos + 1]) {
int l = *prev(prev(it)), r = *it;
// l, pos - 1, r ----> l, pos - 1, pos, r
if (r != n) erase(r - pos + 1);
insert(1);
if (r != n) insert(r - pos);
s.insert(pos);
}
} else {
if (a[pos - 1] > a[pos] && a[pos] > a[pos + 1]) {
int l = *prev(it), r = *it;
// l, r ----> l, pos - 1, pos, r
if (r != n) erase(r - l);
insert(pos - l - 1), insert(1);
if (r != n) insert(r - pos);
s.insert(pos - 1), s.insert(pos);
} else if (a[pos - 1] > a[pos]) {
int l = *prev(it), r = *it;
// l, r ----> l, pos - 1, r
if (r != n) erase(r - l);
insert(pos - l - 1);
if (r != n) insert(r - pos + 1);
s.insert(pos - 1);
} else if (a[pos] > a[pos + 1]) {
int l = *prev(it), r = *it;
// l, r ----> l, pos, r
if (r != n) erase(r - l);
insert(pos - l);
if (r != n) insert(r - pos);
s.insert(pos);
}
}
}
}
// for (auto v : s) printf("%d ", v);
// puts("");
// printf("gcd = %d\n", rt->gcd);
// print(rt);
if (rt->gcd == 0) printf("%d\n", n);
else printf("%d\n", d[rt->gcd]);
}
}
return 0;
}
/*
2
5 2
4 3 2 6 1
2 5
3 5
5 2
4 3 2 6 1
2 5
3 5
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5960kb
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: 6ms
memory: 7896kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 34ms
memory: 12936kb
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 ...
output:
160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160 200000 160...
result:
ok 200001 lines
Test #4:
score: -100
Runtime Error
input:
1 200000 200000 200001 200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 1999...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...