QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733066 | #9543. Good Partitions | Alorithm | WA | 3ms | 3824kb | C++17 | 3.6kb | 2024-11-10 17:01:53 | 2024-11-10 17:01:54 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;
struct SegTree {
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)
int n;
vector<int> val, g;
SegTree(int N = 0) : n(N) {
val.resize(n << 2 | 1);
g.resize(n << 2 | 1);
}
void updata(int p) {
g[p] = gcd(g[ls], g[rs]);
}
void add(int x, int k, int p, int l, int r) {
if (l == r) {
val[p] += k;
if (val[p] > 0)
g[p] = x;
else
g[p] = 0;
return;
}
if (x <= mid)
add(x, k, ls, l, mid);
else
add(x, k, rs, mid + 1, r);
updata(p);
}
int query() {
return g[1];
}
};
const int MAXN = 2e5 + 5;
vector<int> fac(MAXN);
void init() {
for (int i = 1; i <= MAXN; i++)
for (int j = i; j <= MAXN; j += i)
fac[j]++;
}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
using pii = pair<int, int>;
set<pii> s; // left, right
int l = 1;
for (int i = 2; i <= n; i++) {
if (a[i] >= a[i - 1])
continue;
s.insert({ l, i - 1 });
l = i;
}
s.insert({ l, n });
// for (auto [l, r] : s)
// cout << l << ' ' << r << endl;
SegTree tr(n);
for (auto it = s.begin(); it != s.end(); it++) {
if (next(it) != s.end()) {
// cout << it->first << ' ' << it->second << endl;
int len = it->second - it->first + 1;
tr.add(len, 1, 1, 1, n);
}
}
cout << fac[tr.query()] << endl;
auto ist = [&](int l, int r) {
int len = r - l + 1;
auto pos = s.insert({ l, r }).first;
if (next(pos) != s.end())
tr.add(len, 1, 1, 1, n);
return pos;
};
auto rmv = [&](set<pii>::iterator pos) {
int l = pos->first;
int r = pos->second;
int len = r - l + 1;
if (next(pos) != s.end())
tr.add(len, -1, 1, 1, n);
s.erase(pos);
};
while (q--) {
int p, v;
cin >> p >> v;
auto pos = prev(s.lower_bound(make_pair(p + 1, 0)));
int l = pos->first;
int r = pos->second;
int len = r - l + 1;
rmv(pos);
if (p < r)
ist(p + 1, r);
auto pp = ist(p, p);
if (l < p)
ist(l, p - 1);
a[p] = v;
// for (auto [l, r] : s)
// cout << l << ' ' << r << endl;
int r1 = p;
if (p < n && a[p] <= a[p + 1]) {
auto p2 = next(pp);
int l2 = p2->first, r2 = p2->second;
int len2 = r2 - l2 + 1;
rmv(p2);
rmv(pp);
pp = ist(p, r2);
r1 = r2;
}
// cout << endl;
// for (auto [l, r] : s)
// cout << l << ' ' << r << endl;
if (p > 1 && a[p - 1] <= a[p]) {
auto p2 = prev(pp);
int l2 = p2->first, r2 = p2->second;
int len2 = r2 - l2 + 1;
rmv(pp);
rmv(p2);
pp = ist(l2, r1);
}
// for (auto [l, r] : s)
// cout << l << ' ' << r << endl;
cout << fac[tr.query()] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3660kb
input:
1 5 2 4 3 2 6 1 2 5 3 5
output:
1 2 3
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3824kb
input:
1 1 1 2000000000 1 1999999999
output:
0 0
result:
wrong answer 1st lines differ - expected: '1', found: '0'