线性数据结构（一）

单调队列

单调队列问题常常与双指针一起出现
比如求一段序列中，长度不超过$m$ 的连续子序列和的最大值

$\textbf{algorithm}$
最小化$\min \{S[i]-S[j]\}$
此时目标序列是$[j+1, i]$，满足$i-j \leqslant m$
对于$\forall j < i$，即求$S[i] - \max_{j < i} S[j]$

• 算法分析
  对于确定的$i, \ \forall j < i$
  如果$j_1 < j_2$ 并且有$S[j_1] \geqslant S[j_2]$，那么$j_1$ 舍掉
  （因为$j_2$ 同样满足，并且它距离$i$ 更近，更容易满足$\leqslant m$ 这个条件）
  下标值用单调队列存起来，队列中的元素一定满足严格单调增
  即$S[q_1] < S[q_2] < \cdots < S[q_i] < \cdots$

• 算法实现

  • 初始化单调队列，一般取$q_1 = 0$ 作为哨兵
  • 排除队头不合法决策
    $\textbf{while}: l \leqslant r \ \textbf{and} \ i-q[l] > m \Rightarrow l++$
  • 取队头作为最优决策更新答案
  • 当前扫描的点进入队列，并且维护队列单调性
    $\textbf{while}: l \leqslant r \ \textbf{and} \ S[q_r] \geqslant S[i] \Rightarrow r--$
    $q[++r] \leftarrow i$

Acwing135

const int maxn = 300000 + 10;
const int inf = 0x3f3f3f3f;
int n, m, S[maxn], q[maxn];

void solve() {
    int l = 1, r = 1, ans = -inf;
    q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && i - q[l] > m) l++;
        ans = max(ans, S[i] - S[q[l]]);
        while (l <= r && S[q[r]] >= S[i]) r--;
        q[++r] = i;
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i-1] + x;
    }

    solve();
}

取整函数

取整函数有一些常用的性质

$$\begin{gathered} \lfloor -x \rfloor = -\lceil x \rceil \\ \lceil -x \rceil = -\lfloor x \rfloor \end{gathered}$$

$$\begin{gathered} C + \lfloor x \rfloor = \lfloor C + x \rfloor && C \in \mathbb{Z} \\ C - \lfloor x \rfloor = C + \lceil -x \rceil = \lceil C-x \rceil && C \in \mathbb{Z} \\ C - \lceil x \rceil = \lfloor C-x \rfloor && C \in \mathbb{Z} \end{gathered}$$

$$\begin{gathered} \left \lfloor \sqrt{ \lfloor x \rfloor } \right \rfloor = \left \lfloor \sqrt{x} \right \rfloor && \text{实数} x \geqslant 0 \end{gathered}$$

$$\begin{gathered} \left \lfloor \frac{x+m}{n} \right \rfloor = \left \lfloor \frac{ \lfloor x \rfloor + m}{n} \right \rfloor \\ \left \lceil \frac{x+m}{n} \right \rceil = \left \lceil \frac{\lceil x \rceil + m}{n} \right \rceil \\ m, n \ \text{为整数并且分母} \ n > 0 \end{gathered}$$

线性模型

讲到取整函数，不得不说一种模型叫偏差模型
经常出现在诸如时间$t$ 这样的线性结构中
比如某一时刻的偏移量满足

$$\Delta = T_0 + kt$$

Acwing133
这种问题很显然是线性模型
在初识时刻长度为$Q_0$，$t$ 时刻过后，长度增加为

$$Q_0 + q\cdot t$$

const int maxn = 100000 + 10;
int n, m, q, u, v, t, a[maxn];
#define p u/v

queue<ll> v0, v1, v2;
int cmp(int a, int b) { return a > b; }

ll calc(int t) {
    ll mx, x0 = -1, x1 = -1, x2 = -1;
    if (v0.size()) x0 = v0.front() + q*t;
    if (v1.size()) x1 = v1.front() + q*t;
    if (v2.size()) x2 = v2.front() + q*t;

    mx = max(max(x0, x1), x2);
    if (mx == x0 && v0.size()) v0.pop();
    else if (mx == x1 && v1.size()) v1.pop();
    else if (mx == x2 && v2.size()) v2.pop();

    return mx;
}

void solve() {
    sort(a+1, a+1+n, cmp);
    _rep(i, 1, n) v0.push(1ll*a[i]);

    for (int i = 1; i <= m; i++) {
        ll res = calc(i-1);
        if (i % t == 0) printf("%lld ", res);

        ll li = res * p;
        ll ri = res - li;
        li -= i*q, ri -= i*q;
        v1.push(li), v2.push(ri);
    }
    printf("\n");

    for (int i = 1; i <= n+m; i++) {
        ll res = calc(m);
        if (i % t == 0) printf("%lld ", res);
    }
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    // get data
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    _rep(i, 1, n) scanf("%d", &a[i]);

    // then solve
    solve();
}

单调性和分段函数

单调性和分段函数问题，往往是先根据数学工具挖掘单调性
但常常得出了单调性结论，却发现编程实现困难
这里给出一些常见的编程实现方式

• 找拐点

  $$\begin{gathered} (last, dir) \quad \text{来描述} \\ last \text{记录上一个段的最末位置，} \ dir \text{记录上一个段的单调趋势，单调增或减} \end{gathered}$$

Acwing134

const int maxn = 200000 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> PII;
PII a[maxn];
int n;

void solve() {
    sort(a, a+n);

    int last = inf, dir = -1, ans = 1;
    for (int i = 0; i < n; ) {
        int j = i;
        while (j+1 < n && a[j].first == a[j+1].first) j++;
        // [i, j] same value

        int minv = a[i].second, maxv = a[j].second;
        if (dir == -1) {
            if (maxv < last) last = minv;
            else last = maxv, dir = -dir;
        }
        else {
            if (minv > last) last = maxv;
            else {
                ans++;
                last = minv;
                dir = -dir;
            }
        }
        i = j+1;
    }
    printf("%d\n", ans);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);

    // get data
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }

    // solve
    solve();
}

链表：数组模拟

链表用数组模拟，需要全局维护两个值

$$\begin{gathered} l(i), r(i) \\ i \ \text{表示数组下标，} l(i), r(i) \ \text{分别表示左，右两个位置} \end{gathered}$$

特别地，可以这么理解数组模拟

$$\begin{gathered} L[p] = q \ \text{看成是一个作用，将} \ p \ \text{这个位置，左边连到 } q \\ R[p] = q \ \text{同理，将 } p \ \text{这个位置，右边连到 } q \end{gathered}$$

void init() {
    for (int i = 1; i <= n; i++) {
        L[i] = i-1, R[i] = i+1;
    }
}
// remove i
for (int i = n; i >= 1; i--) {
    int left = L[i], right = R[i];
    L[right] = left, R[left] = right;
}

Acwing136
链表可以用来求邻值查找问题

$$\min_{1 \leqslant j < i} |A_i - A_j|$$

typedef pair<ll, int> PII;
const int maxn = 100000 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
PII a[maxn], ans[maxn];
int n;

void solve() {
    sort(a+1, a+1+n);
    a[0].first = -inf, a[n+1].first = inf;

    int L[maxn], R[maxn], mp[maxn];
    for (int i = 1; i <= n; i++) {
        L[i] = i-1, R[i] = i+1;
        mp[a[i].second] = i;
    }

    for (int id = n; id > 1; id--) {
        int i = mp[id], left = L[i], right = R[i];
        ll lval = abs(a[left].first - a[i].first);
        ll rval = abs(a[right].first - a[i].first);

        if (lval <= rval) ans[id] = make_pair(lval, a[left].second);
        else ans[id] = make_pair(rval, a[right].second);

        L[right] = left, R[left] = right;
    }

    for (int i = 2; i <= n; i++) printf("%lld %d\n", ans[i].first, ans[i].second);
}


int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i].first);
        a[i].second = i;
    }

    // then solve
    solve();
}