2016多校训练Contest5：1010 Prefix

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5790

题目翻译

有N个串，强制在线询问 l ~ r 个串之间有多少个不同的前缀。

题解

首先，我们需要建立一颗字典树来给所有前缀编号。
我们先看单个询问 [ l , r ]，我们假装只有字符串 1 ~ r ，我们把一个前缀交给最右边的那个拥有它的字符串，这样一来我们只需要建立一颗线段树统计 [ l , r ] 区间之间的拥有前缀数量就可以了。
所以对于 n 个字符串，我们只需要建立 n 颗线段树，记录 1 ~ ri 的字符串的如上前缀掌握情况。于是，我们可以使用主席树解决这一问题。

代码

/*
  Author : WNJXYK
  Problem : 1010
  Blog : http://wnjxyk.cn
  Date : 2016
*/
#include <bits/stdc++.h>
using namespace std;
const int Maxn=100000;
int n,m;
char str[Maxn+5];
struct Btree{
    int lx,rx;
    int sum;
};
Btree tree[Maxn*40+5];
int Root[Maxn+5];
int nume;
void build(int &x,int left,int right){
    x=++nume;
    tree[x].sum=tree[x].rx=tree[x].lx=0;
    if (left==right){
    }else{
        int mid=(left+right)/2;
        build(tree[x].lx,left,mid);
        build(tree[x].rx,mid+1,right);
    }
}
inline void update(int x){
    tree[x].sum=tree[tree[x].lx].sum+tree[tree[x].rx].sum;
}
void modify(int &x,int px,int pos,int val,int left,int right){
    x=++nume;
    tree[x].lx=tree[px].lx;
    tree[x].rx=tree[px].rx;
    tree[x].sum=tree[px].sum;
    if (left==right){
        tree[x].sum+=val;
    }else{
        int mid=(left+right)/2;
        if (pos<=mid) modify(tree[x].lx,tree[px].lx,pos,val,left,mid);
        if (mid+1<=pos) modify(tree[x].rx,tree[px].rx,pos,val,mid+1,right);
        update(x);
    }
}
int query(int x,int l,int r,int left,int right){
    if (x==0) return 0;
    if (l<=left && right<=r) return tree[x].sum;
    int mid=(left+right)/2;
    int ret=0;
    if (l<=mid) ret+=query(tree[x].lx,l,r,left,mid);
    if (mid+1<=r) ret+=query(tree[x].rx,l,r,mid+1,right);
    return ret;
}
int nxt[Maxn+10][26];
int pre[Maxn+10];
int CRoot,CNume;
int len;
int CT;
void insertStr(int &x,int pos){
    if (!x) {
        x=++CNume;
        for (int i=0;i<26;i++) nxt[x][i]=0;
    }
    if (pos<len){
        insertStr(nxt[x][str[pos]-'a'],pos+1);
        //cout<<"Mv "<<"# "<<nxt[x][str[pos]-'a']<<" From "<< pre[nxt[x][str[pos]-'a']]<<" TO "<<CT<<endl;
        //Update
        if (pre[nxt[x][str[pos]-'a']]==0){
            modify(Root[CT],Root[CT],CT,1,1,n);
            pre[nxt[x][str[pos]-'a']]=CT;
        }else{
            modify(Root[CT],Root[CT],pre[nxt[x][str[pos]-'a']],-1,1,n);
            modify(Root[CT],Root[CT],CT,1,1,n);
            pre[nxt[x][str[pos]-'a']]=CT;
        }
        //cout<<str[pos]<<" "<<nxt[x][str[pos]-'a']<<endl;
    }
}
inline void solve(){
    //Init
    CRoot=CNume=0;
    nume=0;
    build(Root[0],1,n);
    memset(pre,0,sizeof(pre));
    //Build
    for (int i=1;i<=n;i++){
        scanf("%s",str);
        len=strlen(str);
        //cout<<"Insert "<<str<<endl;
        Root[i]=Root[i-1];
        CT=i;
        insertStr(CRoot,0);
    }
    //Query
    int LastAns=0;
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+LastAns)%n+1;r=(r+LastAns)%n+1;
        if (l>r) swap(l,r);
        LastAns=query(Root[r],l,r,1,n);
        printf("%d\n",LastAns);
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF) solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

Author : WNJXYK

Problem : 1010

Blog : http://wnjxyk.cn

Date : 2016

#include <bits/stdc++.h>

using namespace std;

const int Maxn=100000;

int n,m;

char str[Maxn+5];

struct Btree{

int lx,rx;

int sum;

};

Btree tree[Maxn*40+5];

int Root[Maxn+5];

int nume;

void build(int &x,int left,int right){

x=++nume;

tree[x].sum=tree[x].rx=tree[x].lx=0;

if (left==right){

}else{

int mid=(left+right)/2;

build(tree[x].lx,left,mid);

build(tree[x].rx,mid+1,right);

}

inline void update(int x){

tree[x].sum=tree[tree[x].lx].sum+tree[tree[x].rx].sum;

}

void modify(int &x,int px,int pos,int val,int left,int right){

x=++nume;

tree[x].lx=tree[px].lx;

tree[x].rx=tree[px].rx;

tree[x].sum=tree[px].sum;

if (left==right){

tree[x].sum+=val;

}else{

int mid=(left+right)/2;

if (pos<=mid) modify(tree[x].lx,tree[px].lx,pos,val,left,mid);

if (mid+1<=pos) modify(tree[x].rx,tree[px].rx,pos,val,mid+1,right);

update(x);

}

int query(int x,int l,int r,int left,int right){

if (x==0) return 0;

if (l<=left && right<=r) return tree[x].sum;

int mid=(left+right)/2;

int ret=0;

if (l<=mid) ret+=query(tree[x].lx,l,r,left,mid);

if (mid+1<=r) ret+=query(tree[x].rx,l,r,mid+1,right);

return ret;

}

int nxt[Maxn+10][26];

int pre[Maxn+10];

int CRoot,CNume;

int len;

int CT;

void insertStr(int &x,int pos){

if (!x) {

x=++CNume;

for (int i=0;i<26;i++) nxt[x][i]=0;

}

if (pos<len){

insertStr(nxt[x][str[pos]-'a'],pos+1);

//cout<<"Mv "<<"# "<<nxt[x][str[pos]-'a']<<" From "<< pre[nxt[x][str[pos]-'a']]<<" TO "<<CT<<endl;

//Update

if (pre[nxt[x][str[pos]-'a']]==0){

modify(Root[CT],Root[CT],CT,1,1,n);

pre[nxt[x][str[pos]-'a']]=CT;

}else{

modify(Root[CT],Root[CT],pre[nxt[x][str[pos]-'a']],-1,1,n);

modify(Root[CT],Root[CT],CT,1,1,n);

pre[nxt[x][str[pos]-'a']]=CT;

}

//cout<<str[pos]<<" "<<nxt[x][str[pos]-'a']<<endl;

}

inline void solve(){

//Init

CRoot=CNume=0;

nume=0;

build(Root[0],1,n);

memset(pre,0,sizeof(pre));

//Build

for (int i=1;i<=n;i++){

scanf("%s",str);

len=strlen(str);

//cout<<"Insert "<<str<<endl;

Root[i]=Root[i-1];

CT=i;

insertStr(CRoot,0);

}

//Query

int LastAns=0;

scanf("%d",&m);

for (int i=1;i<=m;i++){

int l,r;

scanf("%d%d",&l,&r);

l=(l+LastAns)%n+1;r=(r+LastAns)%n+1;

if (l>r) swap(l,r);

LastAns=query(Root[r],l,r,1,n);

printf("%d\n",LastAns);

}

int main(){

//freopen("in.txt","r",stdin);

while(scanf("%d",&n)!=EOF) solve();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑