Rockdu's Blog

题目描述

The Trains of Colour Parade begins tomorrow in Byteotia.

Intense preparations are already in progress at the station's auxiliary tracks. There are $n$ parallel tracks at the station, numbered from $1$ to $n$ . The train no. $i$ occupies the i^{th}ith track.

Every train consists of $l$ cars and each car is painted with one of 26 colours (denoted by non-capital letters of the English alphabet).

We say that two trains look the same, if their corresponding cars are painted the same colour.

Throughout the parade a crane will switch places of certain pairs of cars. The real parade, however, will take place tomorrow.

Today the train dispatcher, Byteasar, watched the general rehearsal closely. He even wrote down the sequence of car swaps.

Byteasar particularly dislikes many trains looking the same.

For each train $p$ he would like to calculate the maximum number of trains that at some moment look the same as the train $p$ at the very same moment.

Task

Write a programme that:

• reads descriptions of the trains occupying tracks and the sequence of car swaps,

• for each train determines the maximum number of trains that look the same as it at certain moment,

• writes out the result.

给出n个字符串，长度均为len；

有m次操作，每次将两个字符交换；

求每个字符串在任何时点上，与相同的它最多的字符串个数；

输入输出格式

输入格式：

The first line of the input contains three integers $n$ , $l$ and $m$ ( $2\le n\le 1000$ , $1\le l\le 100$ , $0\le m\le 100000$ ), denoting respectively the number of trains, their common length and the number of car swaps. The following $n$ lines contain descriptions of the trains on successive tracks. The

k^{th}kth line consists of $l$ small letters of the English alphabet denoting the colours of successive cars of the k^{th}kth train. Then $m$ lines describing the car swaps follow, in the order of the swaps. The r^{th}rth line contains four integers p_1p1​ , w_1w1​ , p_2p2​ , w_2w2​ ( 1 \le p_1, p_2, \le n1≤p1​,p2​,≤n , 1 \le w_1, w_2 \le l1≤w1​,w2​≤l , p_1 \ne p_2p1​≠p2​ or w_1 \ne w_2w1​≠w2​ ) denoting the r^{th}rth car swap-the car no. w_1w1​ of the train no. p_1p1​ is swapped with the car no. w_2w2​ of the train no. p_2p2​ .

输出格式：

Your programme should write out exactly $n$ lines. The $k^[th}$ line should contain one integer-the number of trains looking the same as the train no. $k$ at certain moment.

输入输出样例

5 6 7
ababbd
abbbbd
aaabad
caabbd
cabaad
2 3 5 4
5 3 5 5
3 5 2 2
1 2 4 3
2 2 5 1
1 1 3 3
4 1 5 6

3
3
3
2
3

说明

The figure presents the successive car swaps:

track 1:  ababbd    ababbd    ababbd    ababbd    aaabbd    aaabbd    aaabbd    aaabbd
track 2:  abbbbd    ababbd    ababbd    aaabbd    aaabbd    acabbd    acabbd    acabbd
track 3:  aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd
track 4:  caabbd    caabbd    caabbd    caabbd    cabbbd    cabbbd    cabbbd    dabbbd
track 5:  cabaad    cabbad    caabbd    caabbd    caabbd    aaabbd    aaabbd    aaabbc
           (0)       (1)       (2)       (3)       (4)       (5)       (6)       (7)

The number of trains looking the same as either of the trains no. 1, 2 or 3 was maximal at time (4) (when all three looked the same). The number of trains looking the same as the train no. 5 was maximal at time (5) and (6). The number of trains looking the same as the train no. 4 was maximal at time (2).

一眼就知道怎么做但是代码十分Dark的数据结构题目。

首先每个串哈希掉，然后每有一个新哈希值，新开一个动态开点线段树记录当前哈希值在每一个时间点上的变化，也可以用平衡树维护。这样我们每一次在一个字符串被修改的时候统计：从它出现在这个哈希值的时间开始一直到当前时间点，该哈希值的最大字符串个数是多少。我们只需要在线段树上记录每一个变更时间点，每一次查询直接查出现时间在线段树中的前驱就行了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#define LL unsigned long long
using namespace std;
const int base = 233, inf = 0x7fffffff;
const int maxn = 1e3 + 5, maxl = 1e2 + 5, maxm = 1e5 + 5;
LL pow[maxn], hsh[maxn], lhsa, lhsb;
char s[maxn][maxn];
int n, m, l, ans[maxn];
int a, b, c, d, intime[maxn];
map<LL, int > tot;

namespace SGT {
    #define L 0
    #define R 1
    struct node{int mx, h, ch[2];}
    tree[(maxm << 6)];
    int cnt;
    map<LL, int> root;
    void push_up(int rt) {
        tree[rt].mx = max(tree[tree[rt].ch[0]].mx, tree[tree[rt].ch[1]].mx);
        tree[rt].h = max(tree[tree[rt].ch[0]].h, tree[tree[rt].ch[1]].h);
    }
    void ins(int & rt, int pos, int dt, int tl = 0, int tr = m + 1) {
        if(!rt) rt = ++cnt;
        if(tl == tr) return tree[rt].h = pos, tree[rt].mx = dt, void();
        int mid = tl + tr >> 1;
        if(pos <= mid) ins(tree[rt].ch[L], pos, dt, tl, mid);
        else ins(tree[rt].ch[R], pos, dt, mid + 1, tr);
        push_up(rt);
    }
    int Qmx(int l, int r, int rt, int tl = 0, int tr = m + 1) {
        if(!rt) return 0;
        if(tl == l && tr == r) return tree[rt].mx;
        int mid = tl + tr >> 1;
        if(r <= mid) return Qmx(l, r, tree[rt].ch[L], tl, mid);
        else if(l > mid) return Qmx(l, r, tree[rt].ch[R], mid + 1, tr);
        else return max(Qmx(l, mid, tree[rt].ch[L], tl, mid), Qmx(mid + 1, r, tree[rt].ch[R], mid + 1, tr));
    }
    int Qpre(int l, int r, int rt, int tl = 0, int tr = m + 1) {
        if(!rt) return 0;
        if(l == tl && r == tr) return tree[rt].h;
        int mid = tl + tr >> 1;
        if(r <= mid) return Qpre(l, r, tree[rt].ch[L], tl, mid);
        else if(l > mid) return Qpre(l, r, tree[rt].ch[R], mid + 1, tr);
        else return max(Qpre(l, mid, tree[rt].ch[L], tl, mid), Qpre(mid + 1, r, tree[rt].ch[R], mid + 1, tr));
    }
}

LL Ghsh(char * s, int len) {
    LL ans = 0;
    for(register int i = 0; i < len; ++i)
        ans = ans + pow[i] * s[i];
    return ans;
}

void edit(int a, int b, int c, int d) {
    hsh[a] = hsh[a] - pow[c] * s[a][c];
    hsh[b] = hsh[b] - pow[d] * s[b][d];
    swap(s[a][c], s[b][d]);
    hsh[a] = hsh[a] + pow[c] * s[a][c];
    hsh[b] = hsh[b] + pow[d] * s[b][d];
}

int main() {
    //freopen("tst.in", "r", stdin);
    //freopen("my.out", "w", stdout);
    pow[0] = 1;
    scanf("%d%d%d", &n, &l, &m);
    for(register int i = 1; i <= 1000; ++i) 
        pow[i] = pow[i - 1] * base;
    for(register int i = 1; i <= n; ++i) {
        scanf("%s", s[i]), hsh[i] = Ghsh(s[i], l);
        ++tot[hsh[i]];
    }
    for(register int i = 1; i <= n; ++i) {
        SGT::ins(SGT::root[hsh[i]], 0, tot[hsh[i]]);
    }
    for(register int i = 1; i <= m; ++i) {
        using namespace SGT;
        scanf("%d%d%d%d", &a, &c, &b, &d), --c, --d;
        if(a == b) {
            //cerr << Qpre(0, intime[a], root[hsh[a]]) << endl;
            ans[a] = max(ans[a], Qmx(Qpre(0, intime[a], root[hsh[a]]), i, root[hsh[a]]));
            lhsa = hsh[a], lhsb = hsh[b];
            edit(a, b, c, d);
            if(lhsa != hsh[a]) {
                --tot[lhsa];
                ins(root[lhsa], i, tot[lhsa]);
                ++tot[hsh[a]], intime[a] = i;
                ins(root[hsh[a]], i, tot[hsh[a]]);
            }
            continue;
        }
        lhsa = hsh[a], lhsb = hsh[b];
        ans[a] = max(ans[a], Qmx(Qpre(0, intime[a], root[lhsa]), i, root[lhsa]));
        ans[b] = max(ans[b], Qmx(Qpre(0, intime[b], root[lhsb]), i, root[lhsb]));
        edit(a, b, c, d);
        if(hsh[a] != lhsa) {
            --tot[lhsa], ++tot[hsh[a]];
            ins(root[lhsa], i, tot[lhsa]);
            intime[a] = i;
            ins(root[hsh[a]], i, tot[hsh[a]]);
        }
        if(hsh[b] != lhsb) {
            --tot[lhsb], ++tot[hsh[b]];
            ins(root[lhsb], i, tot[lhsb]);
            intime[b] = i;
            ins(root[hsh[b]], i, tot[hsh[b]]);
        }
    }
    for(register int i = 1; i <= n; ++i) {
        ans[i] = max(ans[i], SGT::Qmx(SGT::Qpre(0, intime[i], SGT::root[hsh[i]]), m, SGT::root[hsh[i]]));
        printf("%d\n", ans[i]);
    }
    return 0;
}