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是魔术师,他可以使用n种魔法,数字从1到n。 我们使用字符串Si来描述魔法i。魔法Si将造成Wi点伤害。 请注意,Wi可能会随时间而变化。
Kim obey the following rules to use magic:
Kim遵守以下规则来使用魔法:
Each turn, he picks out one magic, suppose that is magic Sk, then Kim will use all the magic i satisfying the following condition:
每回合,他挑出一个魔法,假设那是魔法Sk,那么Kim将使用所有魔法我满足以下条件:
1. Wi<=Wk
2. Sk is a suffix of Si.
Sk是Si的后缀。
Now Kim wondering how many magic will he use each turn.
现在Kim想知道他每回合会使用多少魔法。
Note that all the strings are considered as a suffix of itself.
请注意,所有字符串都被视为自身的后缀。
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.
For each query, output the answer.
1 5 abracadabra 2 adbra 1 bra 3 abr 3 br 2 5 2 3 2 5 1 2 5 2 3 2 2
3 1 2 1
给你n个字符串且有权值wi。两种操作:1. 修改单个字符串的权值,2. 询问有多少个字符串有第k个字符串为后缀且其权值小于等于第k个字符串的权值。
解法一:Hash+预处理
解法二:字典树+树状数组
Hash解法
#include<cstdio>
#include<cstring>
#include <vector>
#include<algorithm>
#define lowbit(x) (x)&(-(x))
#define lson rt<<1
#define rson rt<<1|1
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = 1000+7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const uLL base = 99959;
const int MOD = 1000000007;
char ar[N][N];
int w[N], n, Len[N];
vector<int> son[N];//n个桶
uLL hs[N][N], pw[N];
void HASH(){//预处理每个字符串的hash值,uLL自然溢出
pw[0]=1;
for(int i=0;i<=1000;++i)pw[i]=pw[i-1]*base;
for(int i=1;i<=n;++i){
hs[i][0]=0;int len = Len[i];
for(int j = 1; j <= len; ++j){
hs[i][j]=(hs[i][j-1]*base+ar[i][len+1-j]-'a');
}
}
}
LL get(int k,int l,int r){//求第k个字符串l到r的hash值
return (hs[k][r] - hs[k][l-1]*pw[r-l+1]);
}
void init(){//预处理每个桶
for(int i = 1; i <= n; ++i){
son[i].push_back(i);
for(int j = i + 1; j <= n; ++j){
if(Len[i] == Len[j]&&hs[i][Len[i]] == hs[j][Len[j]]){
son[i].push_back(j);
son[j].push_back(i);
}else if(Len[i] > Len[j]&&hs[j][Len[j]]==get(i,1,Len[j])){
son[j].push_back(i);
}else if(Len[j]>Len[i]&&hs[i][Len[i]]==get(j,1,Len[i])){
son[i].push_back(j);
}
}
}
}
int main(){
int tim;
scanf("%d", &tim);
while(tim--){
scanf("%d", &n);
for(int i=1, u; i <= n; ++i){
son[i].clear();
scanf("%s%d", ar[i]+1, &u);
w[i] = u;Len[i]=strlen(ar[i]+1);
}
HASH();
init();
int m;scanf("%d", &m);
while(m--){
int op,x,y;
scanf("%d%d",&op, &x);
if(op==1){
scanf("%d",&y);
w[x] = y;
}else{
int cnt=0;
for(int i=0;i<son[x].size();++i){//暴力查询即可
int v = son[x][i];
if(w[v]<=w[x])cnt++;
}
printf("%d\n", cnt);
}
}
}
return 0;
}
字典树解法
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x)&(-(x))
#define lson rt<<1
#define rson rt<<1|1
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 1000+7;
const int MX = 1000+7;
const int MXM = 3e5+7;
const int MOD = 1000000007;
char ar[N][N];
int w[N], id[N*10], n, bit[N][N];
int Len[N],End[N];
struct lp{
int id, len;
}cw[N];
struct node{
int nex[26];
void init(){
memset(nex,-1,sizeof(nex));
}
}tr[MX*10];
int le, root;
void add(int k,int x,int c){
while(x <= 1000){
bit[k][x] += c;x += lowbit(x);
}
}
int query(int k,int x){
int sum = 0;
while(x){
sum += bit[k][x];x -= lowbit(x);
}
return sum;
}
void insert(int k, char *s,int slen){
int now = root;
for(int i = slen - 1; i >= 0; --i){
int x = s[i] - 'a';
if(tr[now].nex[x] == -1){
tr[le].init();
tr[now].nex[x] = le++;
}
now = tr[now].nex[x];
if(id[now]){//id[now]这个字符串是k的后缀
add(id[now], w[k], 1);
}
}
if(!id[now]){//新字符串??加!
id[now] = k;
add(k, w[k], 1);
}
End[k]=id[now];//同样的字符串统一一个编号咯
}
void update(int k, char *s, int v,int slen){//操作一修改权值
int now = root;
for(int i = slen - 1;i >= 0; --i){
int x = s[i] - 'a';
now = tr[now].nex[x];
if(id[now]){//相当于换一个权值嘛!!对吧
add(id[now], w[k], -1);
add(id[now], v, 1);
}
}
w[k] = v;
}
bool cmp(const lp &a, const lp &b){
return a.len < b.len;
}
void Trie_dele(){
for(int i = 1; i < N; ++i){
tr[i].init();
}
}
int main(){
int tim;
scanf("%d", &tim);
while(tim--){
scanf("%d", &n);
root = 0;le = 1;tr[0].init();
mme(id, 0);mme(bit, 0);
for(int i=1, u; i <= n; ++i){
scanf("%s%d", ar[i], &u);
cw[i].id = i; cw[i].len = strlen(ar[i]);
w[i] = u;Len[i] = cw[i].len;
}
sort(cw+1,cw+n+1,cmp);
for(int i = 1; i <= n; ++i){//按长度插入
insert(cw[i].id,ar[cw[i].id],cw[i].len);
}
int m;
scanf("%d", &m);
while(m--){
int op, k, v;;scanf("%d", &op);
if(op == 1){
scanf("%d%d", &k, &v);
update(k, ar[k], v, Len[k]);
}else{
scanf("%d", &k);
printf("%d\n", query(End[k], w[k]));
}
}
Trie_dele();
}
return 0;
}
谢谢阅读。