WA 80PTS

RT 调了一晚上，把萌新的OI热情磨没了

题目

可以过这题的弱化版（只是数据范围变小，正常来讲也不应该WA吧）

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 2e3 + 5;
const ll MOD = 1e9 + 7;

int T, n;
char str[MAXN];
ll num[MAXN], fac[MAXN];
int f1[MAXN], f2[MAXN];
int nexn[MAXN], lasn[MAXN];

class SegmentTree
{

#define sn segTree[node]

    struct TreeNode {
        int l, r;
        int lson, rson;
        int data;
    } segTree[MAXN << 2];

    void pushdown(int node)
    {
        if (sn.data)
        {
            segTree[sn.lson].data = max(segTree[sn.lson].data, sn.data);
            segTree[sn.rson].data = max(segTree[sn.rson].data, sn.data);
            sn.data = 0;
        }
    }

public:

    void build(int node, int l, int r)
    {
        sn.l = l;
        sn.r = r;
        sn.data = 0;
        if (l != r)
        {
            sn.lson = node << 1;
            sn.rson = node << 1 | 1;
            int mid = (l + r) >> 1;
            build(sn.lson, l, mid);
            build(sn.rson, mid + 1, r);
        }
    }

    int ask(int node, int pos)
    {
        if (sn.l == sn.r)
            return sn.data;
        pushdown(node);
        int mid = (sn.l + sn.r) >> 1;
        if (pos <= mid)
            return ask(sn.lson, pos);
        else return ask(sn.rson, pos);
    }

    void change(int node, int l, int r, int val)
    {
        if (l > sn.r || r < sn.l)
            return;
        if (l <= sn.l && r >= sn.r)
            sn.data = max(sn.data, val);
        else {
            pushdown(node);
            change(sn.lson, l, r, val);
            change(sn.rson, l, r, val);
        }
    }
} stree;

inline bool equal(int st1, int st2, int len) 
{
    int ed1 = st1 + len - 1, ed2 = st2 + len - 1;
    return (num[ed1] - fac[len] * num[st1 - 1] % MOD + MOD) % MOD == (num[ed2] - fac[len] * num[st2 - 1] % MOD + MOD) % MOD;
}

bool comp(int l, int m, int r)
{
    int st1 = l, ed1 = m - 1;
    int st2 = m, ed2 = r;
    st1 = nexn[st1];
    st2 = nexn[st2];
    int len1 = ed1 - st1 + 1, len2 = ed2 - st2 + 1;
    if (len2 <= 0)
        return 0;
    if (len1 <= 0)
        return 1;
    if (len1 != len2)
        return len1 < len2;
    int le = 0, ri = len1 - 1, res = -1;
    while (le <= ri)
    {
        int mid = (le + ri) >> 1;
        if (equal(st1, st2, mid))
        {
            res = mid;
            le = mid + 1;
        }
        else ri = mid - 1;
    }
    return str[st1 + res] < str[st2 + res];
}

void pre_pow()
{
    fac[0] = 1LL;
    for (int i = 1; i <= 2000; i++)
        fac[i] = 1LL * fac[i - 1] * 10 % MOD;
}

void pre_hash()
{
    num[0] = 0;
    for (int i = 1; i <= n; i++)
        num[i] = (1LL * num[i - 1] * 10 + str[i] - '0') % MOD;
}

void deal_zero()
{
    for (int i = n, j = n + 1; i >= 1; i--)
    {
        if (str[i] != '0')
            j = i;
        nexn[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++)
    {
        if (str[i] != '0')
            j = i;
        lasn[i] = j;
    }
}

int main()
{
    // freopen("P2282.in", "r", stdin);
    // freopen("P2282.out", "w", stdout);
    pre_pow();
    while (scanf("%s", str + 1) != EOF)
    {
        n = strlen(str + 1);
        pre_hash();
        deal_zero();
        stree.build(1, 1, n);
        stree.change(1, 1, n, 1);
        f1[1] = 1;
        // cout << 1 << " ";
        for (int i = 2; i <= n; i++)
        {
            int nex = nexn[i] + (i - nexn[f1[i - 1]]) - 1;
            if (!comp(f1[i - 1], i, nex))
                nex++;
            stree.change(1, nex, n, i);
            f1[i] = stree.ask(1, i);
            // cout << f1[i] << " ";
        }
        // for (int i = 1; i <= n; i++)
        //     printf("d %d %d\n", i, f1[i]);
        // cout << endl;
        int las = lasn[f1[n] - 1];
        stree.build(1, 1, n);
        stree.change(1, las + 1, n, n);
        f2[n] = n;
        for (int i = n - 1; i >= 1; i--)
        {
            f2[i] = max(i, stree.ask(1, i));
            int fir = i - (f2[i + 1] - nexn[i + 1]);
            if (!comp(fir, i + 1, f2[i + 1]))
                fir++;
            fir = lasn[fir - 1] + 1;
            if (fir < 1) fir = 1;
            stree.change(1, fir, i - 1, i);
            // printf("%d ", f2[i]);
        }
        
        for (int i = 1; i <= n; i++)
        {
            int j = i;
            while (j <= f2[i] && j <= n)
                putchar(str[j++]);
            i = j - 1;
            if (i != n) putchar(',');
        }
        putchar('\n');
    }
    return 0;
}