FZU 2280 Magic（字典树+树状数组维护）

 Problem 2280 Magic

Accept: 126    Submit: 430
Time Limit: 2000 mSec    Memory Limit : 262144 KB

 Problem Description

Kim is a magician, he can use n kinds of magic, number from 1 to n. We use string Si to describe magic i. Magic Si will make Wi points of damage. Note that Wi may change over time.

Kim obey the following rules to use magic:

Each turn, he picks out one magic, suppose that is magic Sk, then Kim will use all the magic i satisfying the following condition:

1. Wi<=Wk

2. Sk is a suffix of Si.

Now Kim wondering how many magic will he use each turn.

Note that all the strings are considered as a suffix of itself.

 Input

First line the number of test case T. (T<=6)

For each case, first line an integer n (1<=n<=1000) stand for the number of magic.

Next n lines, each line a string Si (Length of Si<=1000) and an integer Wi (1<=Wi<=1000), stand for magic i and it’s damage Wi.

Next line an integer Q (1<=Q<=80000), stand for there are Q operations. There are two kinds of operation.

“1 x y” means Wx is changed to y.

“2 x” means Kim has picked out magic x, and you should tell him how many magic he will use in this turn.

Note that different Si can be the same.

 Output

For each query, output the answer.

 Sample Input

15abracadabra 2adbra 1bra 3abr 3br 252 32 51 2 52 32 2

 Sample Output

3121

 Source

第八届福建省大学生程序设计竞赛-重现赛（感谢承办方厦门理工学院）

题意：给n个长度<=1000的字符串S[i](仅由小写字母构成)，每个字符串有权值w[i]
      有两种操作
      2 k 选中第k个字符串，问你有多少个字符串满足 w[i]<=w[k] 而且 S[k]是S[i]的后缀
      1 k y 把第k个字符串的权值修改为y
用树状数组维护权值出现的个数，因为要满足后缀关系，所以用字典树反向插入，在节点位置标记，使得之后插入的字符串到达该节点时，更新个数，
插入的顺序是长度从小到大，因为有相同字符串存在，所以为每个字符串标记一下在字典树中最后到达的节点上的值（也就是第一个相同串的序号），这样就能统一处理了。

代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1e6+7;

int trie[maxn][27], tot = 0, bit[1005][1005], val[maxn], End[maxn], w[maxn], vec[maxn], le[maxn];
//trie 存放字典树， tot表示字典树的节点， bit[i][j] 表示以最长i开头的字符串
//val[i]表示从根到i结点的字符串是哪个，用于在更新长字符串时表示第val[root]是当前字符串的后缀
//End[k]表示是辅助bit表示第bit[End[k]] 那一行是以k为后缀的权值;
//w[i]表示i的权值；
//vec表示存放字符串长度升顺，le[i]表示字符串i的长度；
string L[maxn];

bool cmp(int a, int b) {
    return le[a] < le[b];
}


int lowbit(int t)
{
    return t&(-t);
}


void add(int k, int x, int d) {
    for(int i = x; i <= 1000; i += lowbit(i)) bit[k][i] += d;
}


int getsum(int k, int x) {
    int ans = 0;
    for(int i = x; i > 0; i -= lowbit(i)) ans += bit[k][i];
    return ans;
}


void rinsert(int k, string s)
{
    int len = s.length(), root = 0;
    for(int i = len - 1; i >= 0; i--) {
        int id = s[i] - 'a';
        if(!trie[root][id])
            trie[root][id] = ++tot;
        root = trie[root][id];
        if(val[root]) add(val[root], w[k], 1);
    }
    if(!val[root]) {
        val[root] = k;
        add(k, w[k], 1);
    }
    End[k] = val[root];
}

void update(int k, string s, int v) {
    int len = s.length(), root = 0;
    for(int i = len - 1; i >= 0; i--) {
        int id = s[i] - 'a';
        root = trie[root][id];
        if(val[root]) {
            add(val[root], w[k], -1);
            add(val[root], v, 1);
        }
    }
    w[k] = v;
}






int main()
{
    int n, t, q, k, v, r;
    scanf("%d",&t);
    while(t--) {
        tot = 0;
        memset(trie, 0, sizeof(trie));
        memset(bit, 0, sizeof(bit));
        memset(val, 0, sizeof(val));
        memset(vec, 0, sizeof(vec));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            cin >> L[i] >> w[i];
            le[i] = L[i].length();
            vec[i] = i;
        }
        sort(vec+1, vec+1+n, cmp);
        for(int i = 1; i <= n; i++) {
            rinsert(vec[i], L[vec[i]]);
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d", &k);
            if(k == 1) {
                cin >> r >> v;
                update(r, L[r], v);
            } else if(k == 2){
                cin >> r;
                cout << getsum(End[r], w[r]) << endl;
            }
        }
    }
    return 0;
}