You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
49 lines
1.2 KiB
C++
49 lines
1.2 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 5e4 + 10;
|
|
int a[N], m[N], qs[N], qcnt;
|
|
int calc(int n)
|
|
{
|
|
//long long ans = 1ll * n * (n + 1) * (2 * n + 1) / 6;
|
|
long long ans = 1ll * n * (n + 1) / 2;
|
|
if (ans % 3 == 0)
|
|
{
|
|
ans /= 3;
|
|
ans = (ans % 123456789) * (2ll * n + 1);
|
|
}
|
|
else
|
|
{
|
|
ans = (ans % 123456789) * ((2ll * n + 1) / 3);
|
|
}
|
|
return ans % 123456789;
|
|
}
|
|
int main()
|
|
{
|
|
int T, n, Q;
|
|
cin >> T;
|
|
while (T--)
|
|
{
|
|
qcnt = 0;
|
|
cin >> n >> Q;
|
|
for (int i = 0; i < Q; i++)
|
|
scanf("%d", a + i);
|
|
int cur = 0x3f3f3f3f;
|
|
for (int i = Q - 1; i >= 0; i--)
|
|
if (a[i] < cur)
|
|
cur = qs[qcnt++] = a[i];
|
|
for (int i = 0, j = qcnt; i < j;)
|
|
swap(qs[i++], qs[--j]);
|
|
qs[qcnt] = n + 1;
|
|
long long ans = 0;
|
|
for (int i = 0; i < qcnt; i++)
|
|
{
|
|
int r = qs[i + 1] - qs[i];
|
|
ans = (ans + calc(r)) % 123456789;
|
|
}
|
|
cout << ans % 123456789 << endl;
|
|
}
|
|
return 0;
|
|
}
|