本文主要是介绍[噼昂!]problem(Pending)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

\[\color{red}{\text{校长者，真神人也，左马桶，右永神，会执利笔破邪炁，何人当之？}} \\ \begin{array}{|} \hline \color{pink}{\text{The principal is really a god}} \\ \color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\ \color{pink}{\text{holding a sharp pen to pierce the truth}} \\ \color{pink}{\text{Who can resist him? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{green}{\text{校長は本当に神であり、左側にトイレ、右側にヨンシェンがあり}} \\ \color{green}{\text{鋭いペンを持って真実を突き刺している。誰が彼に抵抗できるだろうか？ }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{lightblue}{\text{Le principal est vraiment un dieu}} \\ \color{lightblue}{\text{avec des toilettes à gauche et Yongshen à droite}} \\ \color{lightblue}{\text{tenant un stylo pointu pour percer la vérité}} \\ \color{lightblue}{\text{Qui peut lui résister ? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{purple}{\text{Der Direktor ist wirklich ein Gott}} \\ \color{purple}{\text{mit einer Toilette links und Yongshen rechts}} \\ \color{purple}{\text{der einen spitzen Stift hält}} \\ \color{purple}{\text{um die Wahrheit zu durchdringen.}} \\ \color{purple}{\text{Wer kann ihm widerstehen? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{cyan}{\text{Principalis deus est, Yongshen a dextris cum latrina}} \\ \color{cyan}{\text{acuto stylo ad perforandum veritatem: quis resistet ei? }} \\ \hline \end{array} \\ \color{red}{\text{对曰：“无人，狗欲当之，还请赐教！”}} \\ \newcommand\bra[1]{\left({#1}\right)} \newcommand\Bra[1]{\left\{{#1}\right\}} \newcommand\dx[0]{\text{dx}} \newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand\down[2]{{#1}^{\underline{#2}}} \newcommand\ddiv[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand\udiv[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand\lcm[0]{\operatorname{lcm}} \newcommand\set[1]{\left\{{#1}\right\}} \newcommand\ceil[1]{\left\lceil{#1}\right\rceil} \newcommand\floor[1]{\left\lfloor{#1}\right\rfloor} \]

---

目录

• 壹、关于题目 ¶
• 贰、关于题解 ¶
  • ◆ 结论 の 开端
  • ◆ 结论 の 使用
  • ◆ 结论 の 终焉
• 叁、关于标程 ¶
• 肆、关键 の 地方 ¶

壹、关于题目 ¶

还是没有时间去编......

贰、关于题解 ¶

哦？这道题 \(n\) 居然只有 \(10^5\)，那不是 \(\mathcal O(n^2m)=\mathcal O(n^4)\) 随便跑啊。

这固然是一种美妙的解法，不过仍然有优化的空间。

---

◆ 结论 の 开端

其实这道题为经典的 \(\rm Gale-Ryser\) 型刻划定理模型：

设 \(P_m = p_1,p_2,\cdots,p_m\) 及 \(Q_n=q_1,q_2,\cdots,q_n\) 是两个由非负整数构成的不增序列。如果存在一个简单 \(X,Y\) 二部图使得 \(X\) 中的顶点的度分别为 \(p_1,p_2,\cdots,p_m\) 且 \(Y\) 中的顶点的度分别为 \(q_1,q_2,\cdots,q_n\)，那么称序列对 \((P_m,Q_n)\) 是二部可图的。

而 \((P_m,Q_n)\) 是二部可图的充要条件为

\[\forall k\in [1,m],\sum_{i=1}^k p_i\le \sum_{i=1}^n\min(q_i,k) \;\text{holds} \]

维基百科传送门.

知道这个，我们就可以做许多事情。

---

◆ 结论 の 使用

将结论转到这道题上面，即先将 \(a\) 从大到小排序，然后

\[\forall k\in [1,n],\sum_{i=1}^k a_i\le \sum _{i=1}^m \min(b_i,k)\;\text{holds} \]

赶脚右边的 \(\min (b_i,k)\) 很难搞定，我们可以做一个转换：记 \(c_k=\sum [b_i\ge k]\)，那么右边

\[\sum_{i=1}^m\min(b_i,k) = \sum_{i=1}^k c_k \]

感觉上来说挺直观的，不解释了。

那么，不等式的成立就是

\[\forall k\in [1,n],\sum_{i=1}^kc_i-a_i\ge 0 \;\text{holds} \]

于是乎，使用线段树维护所有 \(k\) 对应的值得最小值就可以解决这个问题。

比较细节的一个地方是修改 \(a_i\) 的时候，由于我们不想改变其不降的规则，我们可以选择每次在相同值平台的左右端点改，这样就不会破坏 \(a\) 不降了。

时间复杂度 \(\mathcal O(n\log n)\).

---

◆ 结论 の 终焉

找了很多资料，没什么比较好的证明，维基百科使用矩阵，然鉴于我是线代战争的炮灰，便不了了之了。后来发现就从网络流方向入手，反而可能是更容易理解的。

先将 \(a_i\) 由大到小排序，不妨建立这样一个网络：从源点向每个左部点连边，其容量为 \(a_i\)，从每个右部点向汇点连边，容量为 \(b_i\)，每个左右部点之间都有一条容量为 \(1\) 的边。下设 \(S,T\) 分别表示左右部点的集合，\(x,y\) 分别为源汇点。

假设某种割边方案，\(x\to a_p(p\in [1,k])\) 的边都未被割掉，而 \(x\to a_q(q\in [k+1,n])\) 的边都被割掉，我们再设 \([S],[T]\) 表示最终割完，与 \(x\) 同一集合的左部点点集为 \([S]\)，右部点点集为 \([T]\)，那么该最小割方案的花费可以表示为

\[\sum_{i\notin [S]}a_i+\sum_{i\in [T]}b_i+|[S]|(m-|[T]|) \]

根据我们的前置条件，我们可以化简式子：

\[\begin{aligned} (*)&=\sum_{i=k+1}^n a_i+\sum_{i\in [T]} b_i+k(m-|[T]|) \\ &=\sum_{i=k+1}^na_i+\sum_{i\in [T]}b_i+\sum_{i\notin [T]}k \end{aligned} \]

后面两项可以看成是，将某些 \(b_i\) 换成了 \(k\). 由于我们想要最小割，所以我们肯定将那些大于 \(k\) 的换掉，所以，存在不等式

\[(*)\ge \sum_{i=k+1}^n a_i+\sum_{i=1}^m \min(b_i,k) \]

由于 \([T]\) 是我们自己设定的，所以我们可以构造 \([T]\) 使得 \(b_i\ge k\) 的点都不在 \([T]\) 中，便达到了下界，同时，最小割有

\[mincut=\min_{k=1}^n\set{\sum_{i=k+1}^n a_i+\sum_{i=1}^m \min(b_i,k)} \]

显然，原图是二部可图，当且仅当

\[maxflow=mincut\ge\sum_{i=1}^n a_i \]

这就是说，对于任意 \(k\in[1,n]\)，都有这个不等式成立，即

\[\begin{aligned} \forall& k\in [1,n],\sum_{i=k+1}^n a_i+\sum_{i=1}^m \min(b_i,k)\ge \sum_{i=1}^n a_i\;\text{holds} \\ \Rightarrow \forall& k\in [1,n],\sum_{i=1}^k a_i\le \sum _{i=1}^m \min(b_i,k)&\square \end{aligned} \]

叁、关于标程 ¶

#include <bits/stdc++.h>
using namespace std;
 
// # define USING_STDIN
// # define NDEBUG
// # define NCHECK
#include <cassert>
 
namespace Elaina {

#define rep(i, l, r) for(int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define drep(i, l, r) for(int i = (l), i##_end_ = (r); i >= i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define whole(v) ((v).begin()), ((v).end())
#define bitcnt(s) (__builtin_popcount(s))
#ifdef NCHECK
# define iputs(Content) ((void)0)
# define iprintf(Content, argvs...) ((void)0)
#else
# define iputs(Content) fprintf(stderr, Content)
# define iprintf(Content, argvs...) fprintf(stderr, Content, argvs)
#endif
 
    typedef unsigned int uint;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair <int, int> pii;
    typedef pair <ll, ll> pll;
    
    template <class T> inline T fab(T x) { return x < 0 ? -x : x; }
    template <class T> inline void getmin(T& x, const T rhs) { x = min(x, rhs); }
    template <class T> inline void getmax(T& x, const T rhs) { x = max(x, rhs); }
 
#ifndef USING_STDIN
    inline char freaGET() {
# define BUFFERSIZE 1 << 17
        static char BUF[BUFFERSIZE], *p1 = BUF, *p2 = BUF;
        return p1 == p2 && (p2 = (p1 = BUF) + fread(BUF, 1, BUFFERSIZE, stdin), p1 == p2) ? EOF : *p1++;
# undef BUFFERSIZE
    }
# define CHARGET freaGET()
#else
# define CHARGET getchar()
#endif
    template <class T> inline T readret(T x) {
        x=0; int f = 0; char c;
        while((c = CHARGET) < '0' || '9' < c) if(c == '-') f = 1;
        for(x = (c^48); '0' <= (c = CHARGET) && c <= '9'; x = (x << 1) + (x << 3) + (c ^ 48));
        return f ? -x : x;
    }
    template <class T> inline void readin(T& x) { x = readret(T(1)); }
    template <class T, class... Args> inline void readin(T& x, Args&... args) {
        readin(x), readin(args...);
    }

    template <class T> inline void writc(T x, char s='\n') {
        static int fwri_sta[55], fwri_ed = 0;
        if(x < 0) putchar('-'), x = -x;
        do fwri_sta[++fwri_ed] = x % 10, x /= 10; while(x);
        while(putchar(fwri_sta[fwri_ed--] ^ 48), fwri_ed);
        putchar(s);
    }

} using namespace Elaina;

const int maxn = 250000;

int n, m, q;
int a[maxn + 5], b[maxn + 5];

inline void input() {
    readin(n, m);
    rep(i, 1, n) readin(a[i]);
    rep(i, 1, m) readin(b[i]);
}

int cnt[maxn + 5], tmp[maxn + 5], revTmp[maxn + 5];
ll preCnt[maxn + 5], preTmp[maxn + 5];
namespace saya {
    
    ll mn[maxn << 2 ^ 3], tag[maxn << 2 ^ 3];

#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
#define _lhs ls, l, mid
#define _rhs rs, mid + 1, r

    inline void pushup(int i) { mn[i] = min(mn[ls], mn[rs]); }
    inline void add(int i, ll v) { mn[i] += v, tag[i] += v; }
    inline void pushdown(int i) {
        if(!tag[i]) return;
        add(ls, tag[i]), add(rs, tag[i]), tag[i] = 0;
    }
    void build(int i = 1, int l = 1, int r = n) {
        tag[i] = 0;
        if(l == r) return mn[i] = preCnt[l] - preTmp[l], void();
        build(_lhs), build(_rhs), pushup(i);
    }
    void modify(int ql, int qr, ll v, int i = 1, int l = 1, int r = n) {
        if(ql > qr || qr < l || r < ql) return;
        if(ql <= l && r <= qr) return add(i, v);
        pushdown(i);
        if(ql <= mid) modify(ql, qr, v, _lhs);
        if(mid < qr) modify(ql, qr, v, _rhs);
        pushup(i);
    }

#undef ls
#undef rs
#undef mid
#undef _lhs
#undef _rhs

} // using namespace saya;
inline void prelude() {
    rep(i, 1, m) ++cnt[b[i]];
    // lawks! upper limit should be @p maxn
    for(int i = maxn; i; --i) cnt[i] += cnt[i + 1];
    memcpy(tmp + 1, a + 1, n << 2);
    sort(tmp + 1, tmp + n + 1, [](const int x, const int y) { return x > y; });
    memcpy(revTmp + 1, tmp + 1, n << 2);
    reverse(revTmp + 1, revTmp + n + 1);
    for(int i = 1; i <= n; ++i) {
        preCnt[i] = preCnt[i - 1] + cnt[i];
        preTmp[i] = preTmp[i - 1] + tmp[i];
    }
    saya::build();
}

inline void work() {
    int q, op, id, pos;
    readin(q);
    while(q--) {
        readin(op, id);
        if(op == 2) {
            pos = lower_bound(revTmp + 1, revTmp + n + 1, a[id]) - revTmp;
            --revTmp[pos], --a[id];
            saya::modify(n - pos + 1, n, 1);
        }
        else if(op == 1) {
            pos = upper_bound(revTmp + 1, revTmp + n + 1, a[id]) - revTmp - 1;
            ++revTmp[pos], ++a[id];
            saya::modify(n - pos + 1, n, -1);
        }
        else if(op == 4) saya::modify(b[id], n, -1), --b[id];
        else ++b[id], saya::modify(b[id], n, 1);
        writc((int)(saya::mn[1] >= 0));
    }
}

signed main() {
    // freopen("problem.in", "r", stdin);
    // freopen("problem.out", "w", stdout);
    input();
    prelude();
    work();
    return 0;
}

肆、关键 の 地方 ¶

就是 \(\rm Gale-Ryser\) 定理咯~~~~

这篇关于[噼昂!]problem(Pending)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！