F NIO with String Game

题意：

给你一个字符串$ss$和$nn$个字符串$tt$,要求你支持$q(1\le q\le 2\times 10^5)q(1\backslash leq\; q\backslash leq\; 2\backslash times\; 10^5)$次操作：

1. 挑选($1\le i\le n1\backslash leq\; i\backslash leq\; n$),在字符串$t_{i}t\_i$后面新增一个字符$chch$
2. 删除字符串$ss$的最后$pp$个字符$(\mathrm{\mid }s\mathrm{\mid }>p)(|s|>p)$
3. 在字符串$ss$后面添加$kk$个字符$ch(1\le k\le 10^9)ch(1\backslash leq\; k\backslash leq10^\{9\})$
4. 统计有多少个字符串$tt$在字典序上严格小于字符串$ss$

所有对串的操作都是永久性的

初始时$\mathrm{\mid }s\mathrm{\mid }\le 2\times 10^5,{\sum }_{i=1}^n{t}_i\le 2\times 10^5|s|\backslash leq\; 2\backslash times10^5,\backslash sum\_\{i=1\}^\{n\}t\_i\backslash leq2\backslash times10^5$

前置知识：字典树

思路：

我们发现，初始最多有$2\times 10^{5}2\backslash times\; 10^5$种不同的字符串，而每次操作只可能会生成一个新的字符串，那么$qq$次操作后，我们的字符串种类最多不会超过$4\times 10^{5}4\backslash times\; 10^5$

如果我们对这所有可能出现的$4040$万个字符串离线排序掉，在配合上树状数组，把$nn$个字符串$tt$都扔到树状数组内，然后对于每个操作$44$找到当前状态下字符串$ss$在树状数组的位置$pospos$，查询小于$pospos$的数有多少个对每个询问直接输出答案，是不是就解决了这题

现在的问题

1. 字符串排序的时间复杂度并不像对整数排序那样，时间复杂度受每个字符串大小影响会很大
2. 如果我们对一个长度为$2020$万的字符串在后面一直加字符，新字符串会和原字符串有极长的公共前缀，如何生成新字符串和进行排序，我们的时间，空间复杂度都会炸掉
3. 字符串$ss$的长度增加能一次加$10^{9}10^9$级别，如何处理是个大问题

解决方案

1. 解决$10^{9}10^9$级别的空间复杂度：压缩字符串，我们自己写一个结构体，配合vector即可实现让一个字符串长度不超过$4\times 10^{5}4\backslash times\; 10^5$

struct my_string
{
    //当前节点的字符串字符为now
    char now;
    //now字符重复出现了total次
    ll total;
};
vector<my_string> s;

但我们有$4\times 10^{5}4\backslash times\; 10^5$个字符串，空间复杂度仍然炸裂

2. 时间复杂度+剩余的空间复杂度：$\backslash \backslash$ 此时我们发现这些特别长的字符串都有非常长的公共前缀，字典树在储存多个有公共前缀字符串时，公共前缀只会占用一次空间，于是我们考虑用字典树写：

字典树的键值部分：

struct my_string
{
    //当前节点的字符串字符为now,下一个字符种类为next
    char now, next;
    // 特别的当next为0时表示一个字符串结束
    // now字符重复出现了total次
    ll total;
    bool operator<(const my_string other) const //自定义排序规则方便我们使用map存储
    {
        if (now < other.now)
            return true;
        if (now > other.now)
            return false;
        if (total == other.total)
            return next < other.next;
        if (total < other.total)
            return next < other.now;
        return now < other.next;
    }
};

字典树实现部分：

struct string_tree
{
    map<my_string, int> mp;
    //将字典树的my_string看作一条边，指向字典树的下一个节点
    int back;//记录来到该节点的字典树位置
} tree[maxm];

inline int tree_next(int pos, char now, char next, int total)
{
    // 查找字典树的节点pos是否已经存在指向{now, next, total}的编号
    int NEXT_POS = tree[pos].mp[{now, next, total}];
    if (NEXT_POS != 0) // 已经存在
        return NEXT_POS;
    // 不存在
    tree[pos].mp[{now, next, total}] = ++tot;
    // 记录新创建的节点tot是从pos指向的
    tree[tot].back = pos;
    return NEXT_POS = tot;
}

这里记录$backback$是为了方便我们在后面进行字符串删除字符的操作

如何通过这个特殊的字典树去实现题目要求的字符串操作

1. 离线询问，记录一个字符串会被修改几次，每次是如何修改的

    for (int i = 1; i <= q; i++)
    {
        Que[i][0] = read(); // Que[i][0/1/2]表示第i次询问的内容
        if (Que[i][0] == 1)
        {
            int x = read();
            scanf(" %c", &ch);
            Modify_t[x].push_back(ch); // 字符串t[x]后面要新增一个字符ch
            Que[i][1] = x;
            Que[i][2] = ch;
        }
        else if (Que[i][0] == 2)
        {
            int p = read();
            Modify_s[++s_now] = {2, p, 0}; // 字符串s要删除最后p个字符
            Que[i][1] = p;
        }
        else if (Que[i][0] == 3)
        {
            int k = read();
            scanf(" %c", &ch);
            Modify_s[++s_now] = {3, k, ch}; // 字符串s后面要新增k个字符ch
            Que[i][1] = k;
            Que[i][2] = ch;
        }
    }

2. 对于一个字符串和它所有后续修改，我们一次搞完，我们记录它在字典树上的结束指针，然后一直在它结束指针上面乱跳直到解决有关这个字符串的所有修改

2.1 将一个字符串表示成压缩了连续字符的vector<>形式

vector<pair<char, ll>> str; // 当前的字符串
inline int Make_to(const char *s)
{
    str.clear();
    for (int i = 1; s[i]; i++)
    {
        char ch = s[i];
        int j = i + 1;
        while (s[j] && s[j] == ch)
            j++;
        str.push_back({ch, j - i});
        i = j - 1;
    }
    int pos = 1; //从字典树的根节点开始跳
    for (int i = 0, N = str.size(); i < N; i++)
    {
        auto [now_ch, total] = str[i];
        char next_ch = 0;
        if (i + 1 < N)
            next_ch = str[i + 1].first;
        pos = tree_next(pos, now_ch, next_ch, total);
    }
    return pos;
}

2.2处理字符串s和t和有关当前字符串的修改(S和T[]存的都是字符串s，t的在字典树的位置)

inline void build(int &pos, int op, int x, int ch)// [op ,x ,ch] 为操作类型
{
    // 先从结束节点回到上一个节点
    pos = tree[pos].back;
    if (op == 2) // 删除最后 x 个字符
    {
        ll last_num;
        while ((last_num = str.end()[-1].second) <= x)
        {
            x -= last_num;
            str.pop_back();
            pos = tree[pos].back;
        }
        str.end()[-1].second -= x;
    }
    else // 新增字符
    {
        if (str.end()[-1].first == ch) //尾部字符相同
        {
            str.end()[-1].second += x;
        }
        else //尾部字符不同
        {
            pos = tree_next(pos, str.end()[-1].first, ch, str.end()[-1].second);
            str.push_back({ch, x});
        }
    }
    // 完成操作后回到空节点
    pos = tree_next(pos, str.end()[-1].first, 0, str.end()[-1].second);
}

    int pos = Make_to(s);
    S[0] = pos;
    for (int i = 1; i <= s_now; i++)
    {
        auto [op, x, ch] = Modify_s[i];
        build(pos, op, x, ch);
        S[i] = pos;
    }

    for (int i = 1; i <= n; i++)
    {
        pos = Make_to(t[i].c_str());
        T[i].push_back(pos);
        for (auto ch : Modify_t[i])
        {
            build(pos, 3, 1, ch);
            T[i].push_back(pos);
        }
    }

2.3排序所有可能出现的字符串

int Sort_num = 0;
int string_rank[maxm], string_sort[maxm];
// string_rank[i]表示第i小的字符串在字典树上终止坐标为string_rank[i]
//因为string_rank[]储存的值最大不会超过字典树的大小，用桶映射下即可
// string_sort[i]就是记在字典树上终止坐标为i的点在所有字符串中排名为string_sort[i]
inline void Sort_for_tree(int pos)
{
    for (auto &[a, b] : tree[pos].mp) // map自动按字典序从小到大排序
    {
        if (a.next == 0) //字符串终止了
        {
            string_rank[++Sort_num] = b;
        }
        else //继续递归
        {
            Sort_for_tree(b);
        }
    }
}

    Sort_for_tree(1);

    for (int i = 1; i <= Sort_num; i++)
    {
        string_sort[string_rank[i]] = i;
    }

树状数组板子

template <class T>
struct BIT
{
    T c[maxm];
    int sz;
    inline void remake(int new_sz, int to = 0)
    {
        sz = new_sz;
        for (int i = 0; i <= sz; i++)
            c[i] = 0;
    }
    inline void modify(int x, T d)
    {
        // x == 0 时会死循环!
        for (; x <= sz; x += x & (-x))
            c[x] += d;
    }
    inline T query(int x)
    {
        T sum = 0;
        for (; x; x -= x & (-x))
            sum += c[x];
        return sum;
    }
};
BIT<int> c;

统计答案

    c.remake(tot);
    for (int i = 1; i <= n; i++)
    {
        c.modify(string_sort[T[i][0]], 1);
    }

    int S_now = 0;
    static int T_now[maxn] = {};
    for (int i = 1; i <= q; i++)
    {
        if (Que[i][0] == 1)
        {
            int x = Que[i][1];
            //删除修改前串的贡献
            c.modify(string_sort[T[x][T_now[x]]], -1);
            //统计修改后串的贡献
            ++T_now[x];
            c.modify(string_sort[T[x][T_now[x]]], 1);
        }
        else if (Que[i][0] == 2 || Que[i][0] == 3)
        {
            //串s指向下一个状态
            S_now++;
        }
        else
        {
            cout << c.query(string_sort[S[S_now]] - 1) << endl;
        }
    }

完整代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define lowbit(x) (x & (-x))
//#define mid ((l + r) >> 1)
#define int long long
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5, maxm = 8e5 + 5, mod = 1e9 + 7;
// maxm 保险起见开了 maxn 的 4倍空间，最后这个代码空间最大跑了130mb 
inline int read()
{
    int x = 0, f = 1, ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

template <class T>
struct BIT
{
    T c[maxm];
    int sz;
    inline void remake(int new_sz, int to = 0)
    {
        sz = new_sz;
        for (int i = 0; i <= sz; i++)
            c[i] = 0;
    }
    inline void modify(int x, T d)
    {
        // x == 0 时会死循环!
        for (; x <= sz; x += x & (-x))
            c[x] += d;
    }
    inline T query(int x)
    {
        T sum = 0;
        for (; x; x -= x & (-x))
            sum += c[x];
        return sum;
    }
};
BIT<int> c;

struct my_string
{
    //当前节点的字符串字符为now,下一个字符种类为next
    char now, next;
    // 特别的当next为0时表示一个字符串结束
    // now字符重复出现了total次
    ll total;
    bool operator<(const my_string other) const //自定义排序规则方便我们使用map存储
    {
        if (now < other.now)
            return true;
        if (now > other.now)
            return false;
        if (total == other.total)
            return next < other.next;
        if (total < other.total)
            return next < other.now;
        return now < other.next;
    }
};

struct string_tree
{
    map<my_string, int> mp;
    //将字典树的my_string看作一条边，指向字典树的下一个节点
    int back; //记录来到该节点的字典树位置
} tree[maxm];
int tot = 1;

inline int tree_next(int pos, char now, char next, int total)
{
    // 查找字典树的节点pos是否已经存在指向{now, next, total}的编号
    int NEXT_POS = tree[pos].mp[{now, next, total}];
    if (NEXT_POS != 0) // 已经存在
        return NEXT_POS;
    // 不存在
    tree[pos].mp[{now, next, total}] = ++tot;
    // 记录新创建的节点tot是从pos指向的
    tree[tot].back = pos;
    return NEXT_POS = tot;
}

int n, q;
int S[maxn], s_now;
char s[maxn], temp[maxn];
string t[maxn];
vector<int> T[maxn];

array<int, 3> Que[maxn];
array<int, 3> Modify_s[maxn];
vector<char> Modify_t[maxn];

vector<pair<char, ll>> str; // 当前的字符串
inline int Make_to(const char *s)
{
    str.clear();
    for (int i = 1; s[i]; i++)
    {
        char ch = s[i];
        int j = i + 1;
        while (s[j] && s[j] == ch)
            j++;
        str.push_back({ch, j - i});
        i = j - 1;
    }
    int pos = 1; //从字典树的根节点开始跳
    for (int i = 0, N = str.size(); i < N; i++)
    {
        auto [now_ch, total] = str[i];
        char next_ch = 0;
        if (i + 1 < N)
            next_ch = str[i + 1].first;
        pos = tree_next(pos, now_ch, next_ch, total);
    }
    return pos;
}

inline void build(int &pos, int op, int x, int ch) // [op ,x ,ch] 为操作类型
{
    // 先从结束节点回到上一个节点
    pos = tree[pos].back;
    if (op == 2) // 删除最后 x 个字符
    {
        ll last_num;
        while ((last_num = str.end()[-1].second) <= x)
        {
            x -= last_num;
            str.pop_back();
            pos = tree[pos].back;
        }
        str.end()[-1].second -= x;
    }
    else // 新增字符
    {
        if (str.end()[-1].first == ch) //尾部字符相同
        {
            str.end()[-1].second += x;
        }
        else //尾部字符不同
        {
            pos = tree_next(pos, str.end()[-1].first, ch, str.end()[-1].second);
            str.push_back({ch, x});
        }
    }
    // 完成操作后回到空节点
    pos = tree_next(pos, str.end()[-1].first, 0, str.end()[-1].second);
}

int Sort_num = 0;
int string_rank[maxm], string_sort[maxm];
// string_rank[i]表示第i小的字符串在字典树上终止坐标为string_rank[i]
//因为string_rank[]储存的值最大不会超过字典树的大小，用桶映射下即可
// string_sort[i]就是记在字典树上终止坐标为i的点在所有字符串中排名为string_sort[i]
inline void Sort_for_tree(int pos)
{
    for (auto &[a, b] : tree[pos].mp) // map自动按字典序从小到大排序
    {
        if (a.next == 0) //字符串终止了
        {
            string_rank[++Sort_num] = b;
        }
        else //继续递归
        {
            Sort_for_tree(b);
        }
    }
}

inline void solve()
{
    n = read(), q = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", temp);
        t[i] = " " + string(temp);
    }
    char ch;
    for (int i = 1; i <= q; i++)
    {
        Que[i][0] = read();
        if (Que[i][0] == 1)
        {
            int x = read();
            scanf(" %c", &ch);
            Modify_t[x].push_back(ch);
            Que[i][1] = x;
            Que[i][2] = ch;
        }
        else if (Que[i][0] == 2)
        {
            int p = read();
            Modify_s[++s_now] = {2, p, 0};
            Que[i][1] = p;
        }
        else if (Que[i][0] == 3)
        {
            int k = read();
            scanf(" %c", &ch);
            Modify_s[++s_now] = {3, k, ch};
            Que[i][1] = k;
            Que[i][2] = ch;
        }
    }

    int pos = Make_to(s);
    S[0] = pos;
    for (int i = 1; i <= s_now; i++)
    {
        auto [op, x, ch] = Modify_s[i];
        build(pos, op, x, ch);
        S[i] = pos;
    }

    for (int i = 1; i <= n; i++)
    {
        pos = Make_to(t[i].c_str());
        T[i].push_back(pos);
        for (auto ch : Modify_t[i])
        {
            build(pos, 3, 1, ch);
            T[i].push_back(pos);
        }
    }

    Sort_for_tree(1);

    for (int i = 1; i <= Sort_num; i++)
    {
        string_sort[string_rank[i]] = i;
    }

    c.remake(tot);
    for (int i = 1; i <= n; i++)
    {
        c.modify(string_sort[T[i][0]], 1);
    }

    int S_now = 0;
    static int T_now[maxn] = {};
    for (int i = 1; i <= q; i++)
    {
        if (Que[i][0] == 1)
        {
            int x = Que[i][1];
            //删除修改前串的贡献
            c.modify(string_sort[T[x][T_now[x]]], -1);
            //统计修改后串的贡献
            ++T_now[x];
            c.modify(string_sort[T[x][T_now[x]]], 1);
        }
        else if (Que[i][0] == 2 || Que[i][0] == 3)
        {
            //串s指向下一个状态
            S_now++;
        }
        else
        {
            cout << c.query(string_sort[S[S_now]] - 1) << endl;
        }
    }
}

signed main()
{
    int t = 1;
    // t = read();
    while (t--)
    {
        solve();
    }
#ifdef sunyuheng365
    system("pause");
#endif
}

——————————————————————————————————————

字典树开26倍字符然后链接权值为total的边好像也是可行的，但我还是觉得map搭配上这种写法，对所有排序更简单一些，最后还是写的map 时间复杂度为O((n+q)(log n+log q))(反正不会比这个差)交上去运行时间是300ms