Znzryb's Blog

The 2025 ICPC Asia East Continent Online Contest (II)——D. Arcane Behemoths

Posted on 2025-09-17 Edited on 2026-04-06

思路讲解

这个就是我们这个数在 rank=2 到 rank=i 的总和。

FOR(i, 2, N) {
    ll lans = 0;
    lans = binpow(2, N - i) * (binpow(3, i - 1) - 1);
    lans %= mod;
    lans *= inv2;
    lans %= mod;
    lans *= A[i];
    lans %= mod;
    ans += lans;
    ans %= mod;
}

rank=1 的时候的贡献。

FOR(i, 1, N) {
    ll lans = binpow(2, N - i) * A[i];
    lans %= mod;
    ans += lans;
    ans %= mod;
}

AC代码

https://qoj.ac/submission/1345581

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll binpow(ll a, ll k) {
    a %= mod;
    ll res = 1;
    if (k < 0)
        return 1;
    while (k) {
        if (k & 1) {
            res *= a;
            res %= mod;
        }
        k >>= 1;
        a *= a;
        a %= mod;
    }
    return res;
}
inline void __() {
    cin >> N;
    vll A(N + 5);
    FOR(i, 1, N) { cin >> A[i]; }
    sort(A.begin() + 1, A.begin() + N + 1);
    ll ans = 0;
    ll inv2 = binpow(2, mod - 2);
    FOR(i, 2, N) {
        ll lans = 0;
        lans = binpow(2, N - i) * (binpow(3, i - 1) - 1);
        lans %= mod;
        lans *= inv2;
        lans %= mod;
        lans *= A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    // #ifdef LOCAL
    //     cerr << "OK/n";
    // #endif
    FOR(i, 1, N) {
        ll lans = binpow(2, N - i) * A[i];
        lans %= mod;
        ans += lans;
        ans %= mod;
    }
    ans %= mod;
    if (ans < 0)
        ans += mod;
    cout << ans << "\n";
}
/*
AC
https://qoj.ac/submission/1345581
*/

心路历程（WA，TLE，MLE……）

The 2025 ICPC Asia East Continent Online Contest (II)——C. Jiaxun!

Posted on 2025-09-17 Edited on 2026-04-06

思路讲解

不难发现，可以用二分答案做。

那么思路就是发现ab，ac都可以看为是A的，但是因为ab，ac的不对称性，所以都要检验一遍。

具体check函数见下面。

ll a,b,c,ab,ac,bc,abc;
bool check(ll mid){
    if(a+ac+ab+abc<mid) return false;
    if(b+bc+ab+abc<mid) return false;
    if(c+bc+ac+abc<mid) return false;
    if(a+c+ab+ac+bc+abc<2*mid) return false;
    if(a+b+ab+ac+bc+abc<2*mid) return false;
    if(b+c+ab+ac+bc+abc<2*mid) return false;
    if(N/3<mid) return false;
    return true;
}

AC代码

https://vjudge.net/solution/63690535

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*

*/
ll a,b,c,ab,ac,bc,abc;
bool check(ll mid){
    if(a+ac+ab+abc<mid) return false;
    if(b+bc+ab+abc<mid) return false;
    if(c+bc+ac+abc<mid) return false;
    if(a+c+ab+ac+bc+abc<2*mid) return false;
    if(a+b+ab+ac+bc+abc<2*mid) return false;
    if(b+c+ab+ac+bc+abc<2*mid) return false;
    if(N/3<mid) return false;
    return true;
}
inline void __(){
    cin>>N;
    cin>>a>>b>>ab>>c>>ac>>bc>>abc;
    ll l=0,r=N;
    while (l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<l<<"\n";
}
/*
AC
https://vjudge.net/solution/63690535
*/

心路历程（WA，TLE，MLE……）

START201——Delete Maximum（计数问题最重要的就是找到一个特征）

Posted on 2025-09-13 Edited on 2026-04-06

思路讲解

通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。

最大值为：1 的长度为：1 的东西：1
最大值为：2 的长度为：1 的东西：1
最大值为：2 的长度为：2 的东西：1
最大值为：3 的长度为：1 的东西：1
最大值为：3 的长度为：2 的东西：1
最大值为：3 的长度为：3 的东西：1
最大值为：4 的长度为：1 的东西：1
最大值为：4 的长度为：2 的东西：1
最大值为：4 的长度为：3 的东西：1
最大值为：4 的长度为：4 的东西：1
最大值为：5 的长度为：1 的东西：1
最大值为：5 的长度为：2 的东西：1
最大值为：5 的长度为：3 的东西：1
最大值为：5 的长度为：4 的东西：1
最大值为：5 的长度为：5 的东西：1
最大值为：6 的长度为：1 的东西：1
最大值为：6 的长度为：2 的东西：1
最大值为：6 的长度为：3 的东西：1
最大值为：6 的长度为：4 的东西：1
最大值为：6 的长度为：5 的东西：1
最大值为：6 的长度为：6 的东西：1
最大值为：7 的长度为：1 的东西：1
最大值为：7 的长度为：2 的东西：1
最大值为：7 的长度为：3 的东西：1
最大值为：7 的长度为：4 的东西：1
最大值为：7 的长度为：5 的东西：1
最大值为：7 的长度为：6 的东西：1
最大值为：7 的长度为：7 的东西：1
最大值为：8 的长度为：1 的东西：1
最大值为：8 的长度为：2 的东西：1
最大值为：8 的长度为：3 的东西：1
最大值为：8 的长度为：4 的东西：1
最大值为：8 的长度为：5 的东西：1
最大值为：8 的长度为：6 的东西：1
最大值为：8 的长度为：7 的东西：1
最大值为：8 的长度为：8 的东西：1
最大值为：9 的长度为：1 的东西：1
最大值为：9 的长度为：2 的东西：1
最大值为：9 的长度为：3 的东西：1
最大值为：9 的长度为：4 的东西：1
最大值为：9 的长度为：5 的东西：1
最大值为：9 的长度为：6 的东西：1
最大值为：9 的长度为：7 的东西：1
最大值为：9 的长度为：8 的东西：1
最大值为：9 的长度为：9 的东西：1
最大值为：10 的长度为：1 的东西：1
最大值为：10 的长度为：2 的东西：1
最大值为：10 的长度为：3 的东西：1
最大值为：10 的长度为：4 的东西：1
最大值为：10 的长度为：5 的东西：1
最大值为：10 的长度为：6 的东西：1
最大值为：10 的长度为：7 的东西：1
最大值为：10 的长度为：8 的东西：1
最大值为：10 的长度为：9 的东西：1
最大值为：10 的长度为：10 的东西：1
最大值为：11 的长度为：1 的东西：1
最大值为：11 的长度为：2 的东西：1
最大值为：11 的长度为：3 的东西：1
最大值为：11 的长度为：4 的东西：1
最大值为：11 的长度为：5 的东西：1
最大值为：11 的长度为：6 的东西：1
最大值为：11 的长度为：7 的东西：1
最大值为：11 的长度为：8 的东西：1
最大值为：11 的长度为：9 的东西：1
最大值为：11 的长度为：10 的东西：1
最大值为：11 的长度为：11 的东西：1

如果说是一个递增的一个序列，我们可以得到任何长度的序列（不大于本身值）。但是如果序列发生变化，就不行了。

最大值为：11 的长度为：1 的东西：1
最大值为：11 的长度为：2 的东西：1
最大值为：11 的长度为：3 的东西：1
最大值为：11 的长度为：4 的东西：1
最大值为：11 的长度为：5 的东西：1
最大值为：11 的长度为：6 的东西：1
最大值为：11 的长度为：7 的东西：1
最大值为：11 的长度为：8 的东西：1
最大值为：11 的长度为：9 的东西：1
最大值为：11 的长度为：10 的东西：1
最大值为：11 的长度为：11 的东西：1

AC代码

https://www.codechef.com/viewsolution/1191801507

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T>> v){cerr<<"{\n";for (auto i : v) _print(i), cerr << "\n";cerr<<" }";}
#endif

using  ll = long long;using ull = unsigned long long;
using ld=double;using LD=long double;
using i128 = __int128;
using pdd = pair<ld,ld>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<ld>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)2e5+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*
通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。

*/
ll Pos[MAXN];
inline void __(){
    cin>>N;
    vll A(N+5);
    FOR(i,1,N){
        cin>>A[i];
        Pos[A[i]]=i;
    }
    ll id=max(A[1],A[N]);
    ll ans=0;
    // 通过打表，我们发现这个通过最大值和这个长度，我们可以唯一确定一个序列。
    vll pre(N+5,INF),suf(N+5,INF);
    FOR(i,1,N){
        pre[i]=min(pre[i-1],A[i]);
    }
    ROF(i,N,1){
        suf[i]=min(suf[i+1],A[i]);
    }
    FOR(i,1,N){
        if(i==N){
            // 如果说这个 i 是 N，在中间的话就就会直接被删掉 
            if(Pos[i]==1 || Pos[i]==N){
                ans+=N;
            }else{
                ans++;
            }
            continue;
        }
        if(i==1 || i==2){
            ans+=i;
            continue;
        }
        if(i<=suf[Pos[i]] || i<=pre[Pos[i]]){
            ans+=i;
        }else{
            ans++;
        }
    }
    ans%=mod;
    cout<<ans<<"\n";
    // ROF(i,N,1){
    //     if(Pos[i]==1 && Pos[i]==N){
    //         id=i;
    //         break;
    //     }
    // }

    
}
/*
AC
https://www.codechef.com/viewsolution/1191801507
1
4
1 3 2 4


[ 1 ]: 2
[ 1 2 ]: 1
[ 2 ]: 1
[ 3 ]: 1
[ 3 1 ]: 1
[ 3 1 2 ]: 1
[ 3 1 4 2 ]: 1
最大值为：1 的长度为：1 的东西：1
最大值为：2 的长度为：1 的东西：1
最大值为：2 的长度为：2 的东西：1
最大值为：3 的长度为：1 的东西：1
最大值为：3 的长度为：2 的东西：1
最大值为：3 的长度为：3 的东西：1
最大值为：4 的长度为：4 的东西：1



*/

心路历程（WA，TLE，MLE……）

START201——Permutation Cost Sum（排列成环，交换排序）

Posted on 2025-09-12 Edited on 2026-04-06

思路讲解

我们发现，即便我们选了一个这个O(1)的，解决简单问题（单组问题的方法），好像也没什么用？所以说问题难道是引导我们怎么直接计算这个东西？我只能说是无从下手呀。

Cycle decomposition of permutations

这个东西是什么意思那？

https://nor-blog.pages.dev/posts/2023-01-09-permutations-for-beginners/

其实就是排列成环。

我们发现这个无视距离的交换就非常适合用图论来分析。

最后时间复杂度是 $O(N\sqrt N)$ 。

FOR(i, 1, N) {
    if (fa[i] == i) {
        ll freq = cnt[i];
        if (freq == 1)
            continue;
        if (memo[freq]) {
            ans += memo[freq];
            ans %= mod;
            continue;
        }
        ll lans = 0;
        // 这里A的定义和题目里面反过来了，不过我认为都一样
        FOR(a, 1, N) {
            ll b = a - a / freq;
            if (b > 1) {
                // 前面是会变化的 b 来接手
                lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                lans %= mod;
                // 注意 b 的上限是 N
                // 而不是 a
                lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                lans %= mod;
            } else {
                lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                lans %= mod;
            }
        }
        memo[freq] = lans;
        ans += lans;
        ans %= mod;
    }
}

AC代码

https://www.codechef.com/viewsolution/1190700079

源代码

// by Gospel_rock
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
    cerr << "[ ";
    for (T i : v)
        _print(i), cerr << " ";
    cerr << "]";
}
template <typename T> void _print(set<T> s) {
    cerr << "{ ";
    for (T i : s)
        _print(i), cerr << " ";
    cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
    cerr << "{";
    _print(p.first);
    cerr << ", ";
    _print(p.second);
    cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
    cerr << "{ ";
    for (auto &p : m)
        _print(p), cerr << " ";
    cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
    cerr << "{\n";
    for (auto i : v)
        _print(i), cerr << "\n";
    cerr << " }";
}
#endif

using ll = long long;
using ull = unsigned long long;
using ld = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<ld>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    while (lT--)
        __();
    return 0;
}
/*

*/
ll fa[MAXN];
ll cnt[MAXN];
ll find(ll x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
void merge(ll x, ll y) {
    ll fax = find(x), fay = find(y);
    if (fax == fay)
        return;
    fa[fax] = fay;
    cnt[fay] += cnt[fax];
}
inline void __() {
    cin >> N;
    vll P(N + 5);
    // vector<vll> g(N + 5);
    FOR(i, 1, N) {
        fa[i] = i;
        cnt[i] = 1;
    }
    FOR(i, 1, N) {
        cin >> P[i];
        // g[i].PB(P[i]);
        merge(i, P[i]);
    }
    ll ans = 0;
    vll memo(N + 5);
    FOR(i, 1, N) {
        if (fa[i] == i) {
#ifdef LOCAL
            debug(i);
#endif
            ll freq = cnt[i];
#ifdef LOCAL
            debug(freq);
#endif
            if (freq == 1)
                continue;
            if (memo[freq]) {
                ans += memo[freq];
                ans %= mod;
                continue;
            }
            ll lans = 0;
            // 这里A的定义和题目里面反过来了，不过我认为都一样
            FOR(a, 1, N) {
                ll b = a - a / freq;
                if (b > 1) {
                    // 前面是会变化的 b 来接手
                    lans += (freq) * (1 + b - 1) * (b - 1) / 2;
                    lans %= mod;
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                } else {
                    lans += (freq - 1) * (a + a) * (N - b + 1) / 2;
                    lans %= mod;
                }
// #ifdef LOCAL
//                 debug(lans);
// #endif
            }
            memo[freq] = lans;
            ans += lans;
            ans %= mod;
        }
    }
    cout << ans << "\n";
}
/*

*/

心路历程（WA，TLE，MLE……）

START203——Set To Median（sort的魔力）

Posted on 2025-09-11 Edited on 2026-04-06

思路讲解

注释非常详细，看注释就行。

AC代码

https://www.codechef.com/viewsolution/1190317643

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*
只进行一次这个操作以后，要求数组和最大

呃，实话实说，我看了一眼题解，看到了二分答案。
你说这个会是检验这个数组和能不能达到吗？

其实我们会发现，这个也没有那么容易

或者说，我们确定一个数字为中位数以后，检查他是否可行
以及快速O(1)算出答案，可不可行那？
*/
inline void __(){
	cin>>N;
	vll A(N+5);
	FOR(i,1,N){
		cin>>A[i];
	}
	// 发现A的顺序不重要，因此我们进行排序
	sort(A.begin()+1,A.begin()+1+N);
	vll Sum(N+5);
	FOR(i,1,N){
		Sum[i]=Sum[i-1]+A[i];
	}
	// 我们会发现一个瓶颈就是这个O(1)之所以不行，就是因为
	// 就是小的数字我们当然是囊括越多小的越好
	// 但是大的数字我们又希望囊括越少大的数字越好
	// 这个时候就产生了矛盾，我们要怎样最优化这个问题那？
	// 我们注意到 
	// profit=len*A[i]-(A[1]+A[2]+A[3]+...+A[len])+(len*A[i]-(A[i+1]+A[i+2]+...+A[i+len]) )
	// 2*A[i]-A[i+1]-A[1],2*A[i]-A[i+2]-A[2]
	// 不难发现这个是单调下降的，因此用二分就行了
	ll ans=Sum[N];
#ifdef LOCAL
	_print(Sum);
#endif
	FOR(i,2,N){
		ll big=N-i;
		ll l=1,r=big;
		while(l<r){
			ll mid=l+r+1>>1;
			ll p=2*A[i]-A[mid+i]-A[mid];
			if(p>=0){
				l=mid;
			}else{
				r=mid-1;
			}
		}
		if(l==r){
			ll lans=l*A[i]*2-Sum[l]-(Sum[i+l]-Sum[i+1-1])+Sum[N];
			ans=max(lans,ans);
		}
	}
	cout<<ans<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1190317643
1
2
3 4

1
3
4 3 1

*/