题意简述

有一条由 $n$ 个单位组成的直线，每个单位上生长着一种甜味的草（甜味编号 $1 \sim n$）。有 $m$ 头奶牛，每头奶牛有一个喜欢的甜味 $f$ 和能吃掉的单位数量上限 $h$（即最多连续吃掉 $h$ 个单位的该种甜味的草）。
奶牛从左右两端进入：左边进入的奶牛从左向右吃，右边进入的奶牛从右向左吃。每种甜味的草最多被两头奶牛吃（左边来一头，右边来一头）。每个位置的草只能被一头奶牛吃掉。
求最多能让多少头奶牛吃到喜欢的草，并求出达到该最大值的方案数（对 $10^9+7$ 取模）。

思路分析

核心观察

1. 每种甜味的草最多被两头奶牛吃掉（左边一头，右边一头）。
2. 每个位置只有一种甜味的草，因此每个位置最多被一头奶牛占领，且吃掉它的奶牛的甜味必须与该位置草甜味一致。
3. 必然会存在一个分界点 $i$，使得左边进入的奶牛恰好走到第 $i$ 个位置，右边进入的奶牛最多走到第 $i+1$ 个位置。枚举这个 $i$，可以避免重复计数。

预处理

• s[i]：第 $i$ 个位置的草甜味。
• num[f][h]：喜欢吃甜味 $f$ 且能吃至少 $h$ 个单位草的奶牛数量（通过前缀和预处理为 num[f][h] = 数量）。
• slm[flavor]：在当前位置 $i$ 左侧（包含 $i$）甜味为 flavor 的草的数量。
• srm[flavor]：在当前位置 $i$ 右侧（不包含 $i$）甜味为 flavor 的草的数量。

枚举分界点 $i$

对于每个 $i$（$0 \le i \le n$，$i=0$ 表示左边无奶牛），计算当前分界下的方案数。

1. 处理甜味为 $s[i]$ 的草（$i \ge 1$）

   • 左边该甜味的草数量：sl = slm[s[i]]
   • 右边该甜味的草数量：sr = srm[s[i]]
   • 左边能吃掉恰好 sl 个该甜味草的奶牛数量：
     sl_cnt = num[s[i]][sl] - num[s[i]][sl-1]（即恰好拥有该数量的奶牛）
   • 右边能吃掉至少 sr 个该甜味草的奶牛数量：
     sr_cnt = num[s[i]][sr]，但如果 $sr \ge sl$，右边会多算一头可能被左边选中的奶牛，需要减去 (sr >= sl)。
   • 若 sl_cnt == 0，则此分界无效。
   • 若 sr_cnt > 0，则该甜味贡献两头奶牛：方案数乘 sl_cnt * sr_cnt，奶牛数加 2。
     否则只贡献一头：方案数乘 sl_cnt，奶牛数加 1。

2. 处理其他甜味 $j \neq s[i]$

   • 左边能吃掉不超过 slm[j] 个甜味 $j$ 草的奶牛数：sl = num[j][slm[j]]
   • 右边能吃掉不超过 srm[j] 个甜味 $j$ 草的奶牛数：sr = num[j][srm[j]]
   • 分类讨论：
     • 若 sl == 0 && sr == 0：无贡献，跳过。
     • 若 sl == 0 || sr == 0：只能从一边选，方案数乘 sl + sr，奶牛数加 1。
     • 若 sl == 1 && sr == 1：左右两边可能是同一头奶牛（因为恰好能吃 1 个单位的奶牛只有一头），这头奶牛可以选择从左边或右边进入，方案数乘 2，奶牛数加 1。
     • 否则：左右两边可独立选择，但不能选同一头奶牛，方案数乘 sl * sr - min(sl, sr)，奶牛数加 2。

答案更新

记录最大奶牛数 ansnum 及对应方案数 anssum。
若当前 testnum > ansnum，则更新；若相等则累加方案数。

边界情况

当 ansnum == 0 时，即没有奶牛能被安排，此时方案数为 1（什么都不做）。

时间复杂度

• 枚举分界点 $O(n)$
• 每种甜味 $O(n)$ 处理
• 总复杂度 $O(n^2)$，对于 $n \le 5000$ 可接受。

AC 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;

template<typename T> void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c - '0');
    x *= f;
}
template<typename T> void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x / 10) write(x / 10);
    putchar(x % 10 + '0');
}

const ll mod = 1000000007;
ll mo(ll a) { return a >= mod ? a - mod : a; }
const int maxn = 5005;

int num[maxn][maxn];   // num[f][h] 前缀和
int slm[maxn], srm[maxn], s[maxn];

int main() {
    int n, m;
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(s[i]);
        ++srm[s[i]];
    }
    for (int i = 1; i <= m; ++i) {
        int f, h;
        read(f), read(h);
        ++num[f][h];
    }
    // 前缀和：num[f][h] 变成 >=h 的数量？实际代码中是 <=h 的累计
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            num[i][j] += num[i][j - 1];

    ll anssum = 1, ansnum = 0;

    for (int i = 0; i <= n; ++i) {
        if (i) ++slm[s[i]], --srm[s[i]];

        ll testsum = 1, testnum = 0;
        int sl, sr;

        // 处理甜味 s[i] 的草（i >= 1）
        if (i) {
            sl = slm[s[i]], sr = srm[s[i]];
            sr = num[s[i]][sr] - (sr >= sl);
            sl = num[s[i]][sl] - num[s[i]][sl - 1];
            if (!sl) continue;  // 左边没有符合条件的奶牛，此分界无效
            if (sr) {
                testsum = testsum * sl % mod * sr % mod;
                testnum += 2;
            } else {
                testsum = testsum * sl % mod;
                testnum++;
            }
        }

        // 处理其他甜味
        for (int j = 1; j <= n; ++j) {
            if (j == s[i]) continue;
            sl = slm[j], sr = srm[j];
            sr = num[j][sr];
            sl = num[j][sl];
            if (!sl && !sr) continue;
            if (!sl || !sr) {
                testsum = testsum * (sl + sr) % mod;
                testnum++;
            } else if (sr == 1 && sl == 1) {
                testsum = testsum * 2 % mod;
                testnum++;
            } else {
                testsum = testsum * (1ll * sl * sr - min(sl, sr)) % mod;
                testnum += 2;
            }
        }

        if (testnum > ansnum) {
            ansnum = testnum;
            anssum = testsum;
        } else if (testnum == ansnum) {
            anssum = mo(anssum + testsum);
        }
    }

    write(ansnum), putchar(' ');
    if (ansnum) write(anssum), putchar('\n');
    else puts("1");
    return 0;
}