1111随记

灰的积雨云 · 2023-11-10 23:28:38 · 个人记录

T1 简单字符串

题意

给定n个长度为m的序列，m \in \left[1, 26 \right]，有q个修改操作，将编号为id点序列中\left [ l, r \right]的对应序列全改为c。求每次操作完成后有多少个不同的序列。1e5级别

SOLUTION

区间修改想到线段树。要O(1)查询，用字符串Hash的方式可以判断。

在线段树中，不妨求出对应段区间的Hash值，pushup利用Hash特性，乘BASE ^ {len}可以得到对应段值。对于pushdown,预处理出m \in \left[1, 26 \right]中m,mm,mmm \dots的Hash值, 存于hc，看子区间长度与tag直接赋值即可。最后可以用map存每个线段树根节点Hash，进而得到有多少个不同的

WRONG

• 由于n, m都不知道，要用动态开点才可以满足空间复杂度

• hc中取的这个子区间长度为r(ls) - l(ls)，不可以加1

CODE

/*======================Header Template======================*/
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef double db;
const int M = 5e5 + 5;
const int P = 1e9 + 5;
const int logM = 80;
const int N = 1e5 + 5;
const int CH = 30;
const int BASE = 233;
char a[M];
ll hc[CH][M];
ll frac[M];
map<ll, int> mp;
void Mod(ll &x) {(x >= P) && (x -= P);}
struct SGT {
    struct Node {
        int ls, rs;
        int l, r;
        ll hs; int tag;
        #define l(x) sgt[x].l
        #define r(x) sgt[x].r
        #define hs(x) sgt[x].hs
        #define tag(x) sgt[x].tag
        #define ls(x) sgt[x].ls
        #define rs(x) sgt[x].rs
    } sgt[M * logM];
    int tot, rt[M];

    void init(int n) {
        lfor(i, 1, n) rt[i] = ++ tot;
    }

    void pushup(int p) {
        hs(p) = hs(ls(p)) * frac[r(rs(p)) - l(rs(p)) + 1] % P + hs(rs(p)); Mod(hs(p));
    }

    void pushdown(int p) {
        if (!tag(p)) return;
        tag(ls(p)) = tag(rs(p)) = tag(p);
        hs(ls(p)) = hc[tag(p)][r(ls(p)) - l(ls(p))];//TODO
        hs(rs(p)) = hc[tag(p)][r(rs(p)) - l(rs(p))];//TODO
        tag(p) = 0;
    }

    void build(int p, int l, int r) {
        l(p) = l, r(p) = r;
        if (l == r) {hs(p) = (a[l] - 'a' + 1); return;}
        if (!ls(p)) ls(p) = ++ tot;
        if (!rs(p)) rs(p) = ++ tot;
        int mid = (l + r) >> 1;
        build(ls(p), l, mid), build(rs(p), mid + 1, r);
        pushup(p);
    }

    void change(int p, int l, int r, int c) {
        if (l <= l(p) && r >= r(p)) {tag(p) = c; hs(p) = hc[c][r(p) - l(p)]; return;}
        pushdown(p);
        int mid = (l(p) + r(p)) >> 1;
        if (l <= mid) change(ls(p), l, r, c); 
        if (r > mid) change(rs(p), l, r, c);
        pushup(p);
    }

} T;

/*======================Define Area======================*/

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    int n, m, q; cin >> n >> m >> q;
    frac[0] = 1; lfor(i, 1, m) frac[i] = frac[i - 1] * BASE % P;
    lfor(i, 1, 28) hc[i][0] = i;
    lfor(i, 1, 28) lfor(j, 1, m) hc[i][j] = hc[i][j - 1] * BASE % P + i, Mod(hc[i][j]);
    T.init(n); 
    lfor(i, 1, n) cin >> (a + 1), T.build(T.rt[i], 1, m), mp[T.sgt[T.rt[i]].hs] += 1;
    lfor(i, 1, q) {
        int id, l, r; string c; cin >> id >> l >> r >> c;
        mp[T.sgt[T.rt[id]].hs] -= 1;
        if (mp[T.sgt[T.rt[id]].hs] == 0) mp.erase(T.sgt[T.rt[id]].hs);
        T.change(T.rt[id], l, r, c[0] - 'a' + 1);
        mp[T.sgt[T.rt[id]].hs] += 1;
        cout << mp.size() << endl;
    }
    return 0;
}

T2 七里香

题意

给定两个序列，长度为n、m，用s、t表示。求s的一个子串，长度尽可能小，左端点尽可能小，且满足为t的子传。输出对应在s的左右端点。无解输出-1

SOLUTION

先O(n)DP判断有无解。枚举左端点，建立一个序列，表示右端点为r时，目前已经匹配了几位，如果全匹配了，对应答案求最优。

• TRICK 左端点尽可能小，倒序枚举l

• TRICK 序列可以这么建，下标表示匹配了几位，值存储的则是右端点。如果当前位可以为右端点，更新。若当前位在t中匹配x，对应只能从x + 1转移，故其r则是x + 1的r。

CODE

/*======================Header Template======================*/
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef double db;
const int N = 2e6 + 5;
const int MAX = 1e6;
const int P = 1e9 + 5;
int n, m;
int s[N], t[N], mp[N];
int f[N];

/*======================Define Area======================*/
void Mod(int &x) {(x >= P) && (x -= P);}

bool check() {
    int f = 1;
    lfor(i, 1, n) {
        if (s[i] == t[f]) ++ f;
        if (f == m + 1) return true;
    }
    return false;
}

void work() {
    read(n, m);
    lfor(i, 1, n) read(s[i]); lfor(i, 1, m) read(t[i]), mp[t[i]] = i, f[i] = P;
    if (!check()) {puts("-1"); return;}
    int ansl = 0, ansr = P;
    rfor(i, n, 1) {
        int x = (s[i] > MAX) ? 0 : mp[s[i]];    
        if (x) {
            if (x == m) f[m] = i;
            else f[x] = min(f[x], f[x + 1]);
        }
        if (ansr - ansl + 1 >= f[1] - i + 1) ansl = i, ansr = f[1];
    }
    cout << ansl << " " << ansr << endl;
    lfor(i, 1, m) mp[i] = 0;
}

int main() {
    freopen("qlx.in", "r", stdin); freopen("qlx.out", "w", stdout);
    int T; read(T);
    while (T --) work();
    return 0;
}