QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #738322 | #9543. Good Partitions | absabs | TL | 0ms | 7660kb | C++23 | 15.0kb | 2024-11-12 18:41:18 | 2024-11-12 18:41:20 |
Judging History
answer
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "D:/OneDrive/study/cpp/.vscode/debug.h"
#else
#define debug(...) 42;
#endif
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ll __int128_t
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 10;
const double eps = 1e-6;
int arr[MAXN], w[MAXN];
int n, q;
struct Node
{
int l, r;
int sum, d;
} tr[MAXN * 4];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r) // 算左右两边的信息
{ // 节点和两个儿子
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
return;
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
return ;
}
void build(int u, int l, int r)
{
if (l == r)
{
int b = w[r] - w[r - 1]; // 存进去的是差分数组,由辗转除法可知,两数的最大公约数和一个数与两数差的最大公约数一致
tr[u] = {l, r, b, b};
return;
}
else
{
// tr[u].l = l, tr[u].r = r;
tr[u] = {l,r,0,0};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x)
{
int b = tr[u].sum + v;
tr[u] = {x, x, b, b};
return ;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
modify(u << 1, x, v);
else
modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (l > r)
return Node{0, 0, 0, 0};
if (tr[u].l >= l && tr[u].r <= r)
return tr[u]; // 在区间内部
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
return query(u << 1, l, r); // 都在左半边
else if (l > mid)
return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res = {0, 0, 0, 0};
pushup(res, left, right);
return res;
}
}
}
void fun()
{
if (n == 1)
{
cout << n << endl;
return;
}
if (n == 2)
{
if (w[2] == 2)
cout << 2 << endl;
else
cout << 1 << endl;
return;
}
auto left = query(1, 1, 1); /// 求1到l的前缀和
auto right = query(1, 1 + 1, n - 1); // 最大公约数
int d = abs(gcd(left.sum, right.d)), now = w[n], cnt = 0;
// cout << d << " eeeee " << now << " " << cnt << endl;
for (int i = 1; i <= sqrt(d); i++)
{
// if (i > now)
// break;
if (d % i == 0)
{
cnt++;
int tp = d / i;
if (tp != i)
cnt++;
}
}
if (d == 0)
cout << n << endl;
else
cout << cnt << endl;
return ;
}
void solve()
{
cin >> n >> q;
int cnt = 1;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= n; i++)
w[i] = 0;
set<int> st;
for (int i = 2; i <= n; i++)
{
if (arr[i] < arr[i - 1])
{
w[i - 1] = cnt;
cnt = 1;
st.insert(i - 1);
}
else
cnt++;
}
w[n] = cnt;
st.insert(n);
arr[0] = w[0] = 0;
int indx, x;
build(1, 1, n);
fun();
while (q--)
{
cin >> indx >> x;
arr[indx] = x;
// cout << "begin\n";
// for(auto L : st)
// cout << L << " ";
// cout << "\nend\n";
if (w[indx])
{
if (w[indx] == 1)
{
if (indx == 1)
{
if (arr[1] <= arr[2])
{
int d = -w[1];
w[1] = 0;
modify(1, 1, d);
if (1 + 1 <= n)
modify(1, 2, -d);
auto tp = st.upper_bound(indx);
int t = *tp;
// int t = upper_bound(w + 1, w + 1 + n, 0) - w;
w[t] += 1;
d = 1;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(1)) st.erase(1);
}
fun();
continue;
}
else if (indx == n)
{
if (n - 1 >= 1 && arr[n] >= arr[n - 1])
{
int d = w[n - 1];
w[n] += d;
modify(1, n, d);
w[n - 1] = 0;
d = -d;
if(n - 1 >= 1)
modify(1, n - 1, d);
modify(1, n, -d);
if(!st.count(n)) st.insert(n);
if(w[n - 1] == 0) st.erase(n - 1);
}
else if(n - 1 >= 1 && arr[n - 1] > arr[n])
{
int d = w[n] - 1;
w[n - 1] = d;
modify(1,n - 1,d);
modify(1,n,-d);
w[n] = 1;
d = -d;
modify(1,n,d);
if(!st.count(n - 1)) st.insert(n - 1);
}
fun();
continue;
}
if (indx - 1 >= 1 && indx + 1 <= n && arr[indx - 1] <= arr[indx] && arr[indx] <= arr[indx + 1])
{
int sum = w[indx - 1];
int d = -w[indx - 1];
w[indx - 1] = 0;
if(indx > 1)
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = -w[indx];
sum += w[indx];
w[indx] = 0;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
w[t] += sum;
d = -sum;
// if(!st.count(t)) st.insert(t);
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
st.erase(indx - 1);
st.erase(indx);
}
else if (indx - 1 >= 1 && arr[indx - 1] <= arr[indx])
{
int d = -w[indx - 1];
w[indx - 1] = 0;
if(indx > 1)
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
auto tp = st.lower_bound(indx);
int t = *tp;
d = -d;
w[t] += d;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(indx - 1)) st.erase(indx - 1);
if(!st.count(indx)) st.insert(indx);
}
else if (indx + 1 <= n && arr[indx] <= arr[indx + 1])
{
int d = -w[indx];
w[indx] = 0;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
auto tp = st.upper_bound(indx);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
int t = *tp;
d = -d;
w[t] += d;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(indx)) st.insert(indx);
}
}
else
{
if (indx == n)
{
if (indx == 1)
{
continue;
}
if (arr[n - 1] > arr[n])
{
int d = w[n] - 1;
w[n - 1] += d;
modify(1, n - 1, d);
// if(n <= n)
modify(1, n, -d);
d = -d;
w[n] = 1;
modify(1, n, d);
if(!st.count(n - 1)) st.insert(n - 1);
}
}
else
{
if (indx > 1 && arr[indx] < arr[indx - 1]) // 断开
{
int d = w[indx] - 1;
w[indx - 1] += d;
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = 1 - w[indx];
w[indx] = 1;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
if(!st.count(indx - 1)) st.insert(indx - 1);
if(!st.count(indx)) st.insert(indx);
}
if (indx < n && arr[indx] <= arr[indx + 1])
{
int sum = w[indx];
int d = -w[indx];
w[indx] = 0;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
auto tp = st.upper_bound(indx);
int t = *tp;
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
w[t] += sum;
d = -d;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(indx)) st.erase(indx);
}
}
}
}
else
{
if (indx == 1 && arr[1] > arr[2])
{
// int t = upper_bound(w + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
w[t]--;
int d = -1;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
d = 1;
w[1] = 1;
modify(1, 1, d);
if (2 <= n)
modify(1, 2, -d);
if(!st.count(1)) st.insert(1);
}
else
{
if (indx < n && arr[indx] > arr[indx + 1])//断开
{
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
int sum = w[t];
int R = t - indx;
int L = w[t] - R;
int d = R - w[t];
// int d = w[t] - (t - indx) - w[indx];
w[indx] += L;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = R - w[t];
w[t] = R;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
st.insert(indx);
if(w[t] == 0) st.erase(t);
}
if (indx > 1 && arr[indx - 1] > arr[indx] && !w[indx - 1]) // 断开
{
auto tp = st.lower_bound(indx);
int t = *tp;
int R = t - indx + 1,L = w[t] - R;
int d = L;
w[indx - 1] += L;
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = R - w[t];;
w[t] += d;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(w[indx - 1]) st.insert(indx - 1);
else st.erase(indx - 1);
if(!st.count(t)) st.insert(t);
}
if (indx > 1 && arr[indx - 1] <= arr[indx])
{
auto tp = st.lower_bound(indx);
int t = *tp;
int d = -w[indx - 1];
w[indx - 1] = 0;
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = -d;
w[t] += w[indx - 1];
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(indx - 1)) st.erase(indx - 1);
if(w[t]) st.insert(t);
}
if (indx < n && arr[indx] <= arr[indx + 1])
{
auto tp = st.upper_bound(indx);
int t = *tp;
int sum = w[indx];
int d = -w[indx];
w[indx] = 0;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
// auto tp = st.upper_bound(indx);
// int t = *tp;
w[t] += sum;
d = sum;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
if(st.count(indx)) st.erase(indx);
}
}
}
// cout << "\narr :\n";
// for(int i=1;i<=n;i++) cout << arr[i] << " ";
// cout << endl;
// cout << "\nw :\n";
// for(int i=1;i<=n;i++) cout << w[i] << " ";
// cout << endl;
fun();
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
while (_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7660kb
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: 7640kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: -100
Time Limit Exceeded
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 192 200 224 240 240 240 256 240 288 240 280 320 288 300 288 320 288 320 336 300 288 320 320 320 384 280 336 320 360 320 320 300 384 360 336 320 384 400 384 320 360 320 336 360 384 320 360 320 384 400 448 320 336 360 384 400 384 320 420 320 384 360 352 480 360 320 448 400 432 320 384 3...