QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #737218 | #9543. Good Partitions | absabs | TL | 1ms | 7780kb | C++23 | 13.2kb | 2024-11-12 15:06:00 | 2024-11-12 15:06:01 |
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;
for (int i = 2; i <= n; i++)
{
if (arr[i] < arr[i - 1])
{
w[i - 1] = cnt;
cnt = 1;
}
else
cnt++;
}
w[n] = cnt;
arr[0] = w[0] = 0;
int indx, x;
build(1, 1, n);
fun();
while (q--)
{
cin >> indx >> x;
arr[indx] = x;
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);
int t = -1;
for(int i=1;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t] += 1;
d = 1;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
fun();
continue;
}
else if (indx == n)
{
if (n - 1 >= 1 && arr[n] >= arr[n - 1])
{
w[n] += 1;
modify(1, n, 1);
w[n - 1]--;
if(n - 1 >= 1)
modify(1, n - 1, -1);
modify(1, 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] + 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];
w[indx] = 0;
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
int t = -1;
for(int i=indx+1;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t] += sum;
d = sum;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
else if (indx - 1 >= 1 && arr[indx - 1] <= arr[indx])
{
w[indx] += w[indx - 1];
int d = w[indx - 1];
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = -w[indx - 1];
w[indx - 1] = 0;
if(indx > 1)
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
}
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);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
int t = -1;
for(int i=indx+1;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t]++;
modify(1, t, 1);
if (t + 1 <= n)
modify(1, t + 1, -1);
}
}
else
{
if (indx == n)
{
if (indx == 1)
{
continue;
}
if (arr[n - 1] > arr[n])
{
int d = w[n] - 1 - w[n - 1];
w[n - 1] = w[n] - 1;
modify(1, n - 1, d);
// if(n <= n)
modify(1, n, -d);
d = 1 - w[n];
w[n] = 1;
modify(1, n, d);
}
}
else
{
if (indx > 1 && arr[indx] < arr[indx - 1])
{
int d = w[indx] - 1 - w[indx - 1];
w[indx - 1] = w[indx] - 1;
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 (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);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
int t = -1;
for(int i=indx+1;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t] += sum;
modify(1, t, sum);
if (t + 1 <= n)
modify(1, t + 1, -sum);
}
}
}
}
else
{
if (indx == 1&& arr[1] > arr[2])
{
// int t = upper_bound(w + 1, w + 1 + n, 0) - w;
int t = -1;
for(int i=2;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t]--;
modify(1, t, -1);
if (t + 1 <= n)
modify(1, t + 1, 1);
int d = -w[1];
w[1] = 1;
modify(1, 1, d);
if (2 <= n)
modify(1, 2, -d);
}
else
{
if (indx < n && arr[indx] > arr[indx + 1])
{
int t = -1;
for(int i=indx;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
int sum = w[t];
int d = w[t] - (t - indx) - w[indx];
w[indx] = w[t] - (t - indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = t - indx - w[t];
w[t] = t - indx;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
if (indx > 1 && arr[indx - 1] > arr[indx])
{
int d = w[indx] - 1 - w[indx - 1];
w[indx - 1] = w[indx] - 1;
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 (indx > 1 && arr[indx - 1] <= arr[indx])
{
int d = w[indx - 1];
w[indx] += w[indx - 1];
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = -w[indx - 1];
w[indx - 1] = 0;
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
}
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);
int t = -1;
for(int i=2;i<=n;i++){
if(w[i]){
t=i;
break;
}
}
w[t] += sum;
d = sum;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
}
}
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: 7736kb
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: 1ms
memory: 7780kb
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 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...