注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3879]SvT  

2015-01-28 09:07:05|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3879: SvT

比较水
log2打成log了……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5e5+100;
const int M = 3E6+100;
const ll MOD = 23333333333333333;
int n,m,len,data[M],Sa[N],hei[N];
int st[22][N],two[50],tmph[M];
char str[N];
int ask(int l,int r){
int k = log2(r-l+1);
return min(st[k][l] , st[k][r-two[k]+1]);
}
namespace Suf{
int tmp[2][N*2],cot[N],tl[N];
void sort(int n,char s[],int sa[]){
int i,j,p=0,m='z'+1,*x=tmp[0],*y=tmp[1];
for(i=0;i<m;i++)cot[i]=0;
for(i=0;i<n;i++)cot[x[i]=s[i]]++;
for(i=1;i<m;i++)cot[i] += cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[x[i]]] = i;
for(j=1;j<n&&p<n;j+=j,m=p){
//sort 2
for(p=0,i=n-j;i<n;i++)y[p++] = i;
for(i=0;i<n;i++)if(sa[i] - j>=0)y[p++] = sa[i] - j;
for(i=0;i<n;i++)tl[i] = x[y[i]];
//sort 1
for(i=0;i<m;i++)cot[i]=0;
for(i=0;i<n;i++)cot[tl[i]]++;
for(i=1;i<m;i++)cot[i] += cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[tl[i]]] = y[i];
//calc x
swap(x,y);x[sa[0]] = 0;p = 1;
for(i=1;i<n;i++)
if((sa[i]+j<n)^(sa[i-1]+j<n))x[sa[i]]=p++;
else x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++;
}
}
void geth(int n,char s[],int sa[],int h[]){
int i,j,k=0,*rk=tmp[0];
for(i=0;i<n;i++)rk[sa[i]] = i;
for(i=0;i<n;h[rk[i++]]=k)
if(rk[i]-1>=0)for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
else k=0;
}
void getst(int n){
int i,j,lgn = log2(n-1)+1;
for(i=0;i<n;i++)st[0][i] = hei[i];
for(j=1;j<=lgn;j++)
for(i=1;i+two[j-1]<n;i++)
st[j][i] = min(st[j-1][i] , st[j-1][i+two[j-1]]);
}
}
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
bool cmp(int a,int b){return Suf::tmp[0][a] < Suf::tmp[0][b];}
struct Node{Node(int a=0,ll b=0){i=a;d=b;}int i;ll d;};
deque<int>dui;
void print(){
int i,j;
printf("%s\n",str);
for(i=0;i<len;i++){
printf("[%d %d]%s\n",hei[i],Sa[i],str+Sa[i]);
}
}
bool better(int a,int b){return b<=a;}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
for(two[0]=1,i=1;i<=30;i++)two[i] = two[i-1]*2;
scanf("%d%d",&len,&m);
scanf("%s",str);
Suf::sort(len,str,Sa);
Suf::geth(len,str,Sa,hei);
Suf::getst(len);
//print();
int *rk = Suf::tmp[0];
while(m--){
scanf("%d",&n);for(i=1;i<=n;i++)data[i] = scan()-1;
sort(data+1,data+1+n,cmp);
n = unique(data+1,data+1+n)-data-1;
ll ans = 0,nans = 0;
dui.clear();//dui.push_back(Node());
dui.push_back(1);
for(i=2;i<=n;i++){
tmph[i] = ask(rk[data[i-1]]+1,rk[data[i]]);
while((j=dui.size())>1 && better(tmph[dui.back()],tmph[i])){
nans = (nans - (ll)tmph[dui[j-1]]*(dui[j-1] - dui[j-2]))%MOD;
dui.pop_back();
}
nans = (nans + (ll)tmph[i] * (i - dui[j-1]))%MOD;
dui.push_back(i);
ans = (ans + nans)%MOD;
}
//printf("\n");
if(ans < 0)ans += MOD;
printf("%lld\n",ans);
}
return 0;
}

题解:
后缀数组+单调队列
题目里都说出来后缀什么的必然是用后缀xxx - -|||
然后对于每次询问先把后缀排序(一开始预处理出rank)
然后问题就变成了Σ所有区间[l,r]min h[ ] ,单调队列扫一遍就行了
  评论这张
 
阅读(54)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017