BZOJ2795:[Poi2012]A Horrible Poem 暴力+hash(&&BZOJ2890)
BZOJ3876:[Ahoi2014]支线剧情 有上下界网络流

BZOJ2119:股市的预测 分治+后缀数组

shinbokuow posted @ 10 年前 in BZOJ with tags 分治 后缀数组 , 1428 阅读

思路:

一种分治的神做法.建议去看原论文[2011年集训队作业]

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 50010
  
int n,lim;
  
int len[N];
inline void pre(int n){
    for(int i=2;i<=n;++i)len[i]=len[i>>1]+1;
}
  
int Read[N],s[N],ss[N],v[N],nv[N],q[N],c[N];
inline bool cmp(int x,int y,int hl,int n){
    return v[x]==v[y]&&((x+hl>n&&y+hl>n)||(x+hl<=n&&y+hl<=n&&v[x+hl]==v[y+hl]));
}
struct SuffixArray{
    int rk[N],h[N],sa[N],rmqh[N][16];
    inline void Init(int s[],int n,int m){
        int i,j,k,hl,id;
        for(i=1;i<=m;++i)c[i]=0;
        for(i=1;i<=n;++i)++c[v[i]=s[i]];
        for(i=2;i<=m;++i)c[i]+=c[i-1];
        for(i=n;i>=1;--i)sa[c[v[i]]--]=i;
        for(int d=1;;++d){
            for(hl=1<<(d-1),id=0,i=n-hl+1;i<=n;++i)q[++id]=i;
            for(i=1;i<=n;++i)if(sa[i]>hl)q[++id]=sa[i]-hl;
            for(i=1;i<=m;++i)c[i]=0;
            for(i=1;i<=n;++i)++c[v[q[i]]];
            for(i=2;i<=m;++i)c[i]+=c[i-1];
            for(i=n;i>=1;--i)sa[c[v[q[i]]]--]=q[i];
            for(i=m=1;i<=n;++m,i=j+1){
                for(j=i;j!=n&&cmp(sa[j],sa[j+1],hl,n);++j);
                for(k=i;k<=j;++k)nv[sa[k]]=m;
            }
            if(--m==n)break;
            for(i=1;i<=n;++i)v[i]=nv[i];
        }
          
        for(i=1;i<=n;++i)rk[sa[i]]=i;
        for(i=1;i<=n;++i){
            if(rk[i]==1)continue;
            j=max(0,h[rk[i-1]]-1);
            while(i+j<=n&&sa[rk[i]-1]+j<=n&&s[i+j]==s[sa[rk[i]-1]+j])++j;
            h[rk[i]]=j;
        }
        for(i=1;i<=n;++i)rmqh[i][0]=h[i];
        for(j=1;j<=15;++j)for(i=1;i+(1<<j)-1<=n;++i)rmqh[i][j]=min(rmqh[i][j-1],rmqh[i+(1<<(j-1))][j-1]);
    }
    inline int askrmq(int l,int r){
        return min(rmqh[l][len[r-l+1]],rmqh[r-(1<<len[r-l+1])+1][len[r-l+1]]);
    }
    inline int getlcp(int x,int y){
        int lins=min(rk[x],rk[y]),rins=max(rk[x],rk[y]);
        if(lins==rins)return n-x+1;
        else return askrmq(lins+1,rins);
    }
}Steins,revSteins;
  
inline int lcp(int x,int y){
    return Steins.getlcp(x,y);
}
inline int lcs(int x,int y){
    return revSteins.getlcp(n-x+1,n-y+1);
}
inline bool same(int l1,int l2,int len){
    return lcp(l1,l2)>=len;
}
  
map<int,int>M;int sav[N];
  
long long res;
inline void SteinsGate(int l,int r){
    if(r-l+1<lim+2)return;
    int mid=(l+r)>>1;
    SteinsGate(l,mid),SteinsGate(mid+1,r);
    int prelen,suflen,insl,insr,nowlen;
    for(prelen=0;prelen<lim;++prelen){
        suflen=lim-1-prelen;
        insl=mid-prelen,insr=mid+suflen;
        if(insl>=l&&insr<=r)
            for(nowlen=1;insl-nowlen>=l&&insr+nowlen<=r;++nowlen)if(same(insl-nowlen,insr+1,nowlen))++res;
    }
    int lins,rins,anotherins,Lcp,Lcs,up,down;
    for(anotherins=l;anotherins<=r;++anotherins){
        if((anotherins>mid&&anotherins-mid-1>=lim)||(mid>anotherins&&mid-anotherins-1>=lim)){
            lins=min(mid,anotherins),rins=max(mid,anotherins);
            Lcp=lcp(lins,rins),Lcs=lcs(lins,rins);
            down=-INF,up=INF;
            down=max(down,rins-Lcs-lim+1);//rins-(x+m-1)<=lcs
            up=min(up,lins+Lcp);//x-lins<=lcp
            down=max(down,l-lim+rins-lins);//lins-(rins-(x+m-1))+1>=l
            up=min(up,r+1+lins-rins);//rins+(x-lins)-1<=r
            down=max(down,lins+1),up=min(up,rins-1);//lins<=x<=rins
            down=max(down,lins+2-lim),up=min(up,rins-lim);//lins<=x+m-1<=rins
            if(down<=up){
                res+=up-down+1;
                if(anotherins<mid&&down==anotherins+1)--res;
            }
        }
    }
}
  
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    scanf("%d%d",&n,&lim);register int i;
    for(i=0;i<n;++i)scanf("%d",&Read[i]);
    for(--n,i=1;i<=n;++i)s[i]=Read[i]-Read[i-1];
      
    for(i=1;i<=n;++i)sav[i]=s[i];sort(sav+1,sav+n+1);
    int id=0;for(sav[0]=-INF,i=1;i<=n;++i)if(sav[i]!=sav[i-1])M[sav[i]]=++id;
    for(i=1;i<=n;++i)s[i]=M[s[i]];
    for(i=n;i>=1;--i)ss[i]=s[n+1-i];
      
    pre(n),Steins.Init(s,n,id),revSteins.Init(ss,n,id);
      
    SteinsGate(1,n);
      
    cout<<res<<endl;
      
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter