【2019.8.13】纪中Day13

T1:rank

桶拍

T2:seek

Kmp

不断用头尾匹配


1
2
3
4
5
6
7
8
9
10
11
12
j=0;
for(i=2;i<=la;i++)
{
    while(a[i]!=a[j+1]&&j!=0) j=q[j];
    if(a[i]==a[j+1]) j++;
    q[i]=j;
}
while(la>0)
{
    s[++t]=q[la];
    la=q[la];
}

T3:pot

线段树求区间最大/小值


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void updata(int root,int l,int r,int x,int k)
{
    if(r<x||x<l) return;
    if(l==r&&l==x)
    {
        Tree[root].sum=Tree[root].lma=Tree[root].lmi=Tree[root].ma=Tree[root].mi=Tree[root].rma=Tree[root].rmi=k;
        return;
    }
    int mid=(l+r)>>1,rr=root<<1;
    updata(rr,l,mid,x,k);
    updata(rr+1,mid+1,r,x,k);
    Tree[root].sum=Tree[rr].sum+Tree[rr+1].sum;
    Tree[root].lma=max(Tree[rr].lma,Tree[rr].sum+Tree[rr+1].lma);
    Tree[root].lmi=min(Tree[rr].lmi,Tree[rr].sum+Tree[rr+1].lmi);
    Tree[root].rma=max(Tree[rr+1].rma,Tree[rr+1].sum+Tree[rr].rma);
    Tree[root].rmi=min(Tree[rr+1].rmi,Tree[rr+1].sum+Tree[rr].rmi);
    Tree[root].ma=max(max(Tree[rr].ma,Tree[rr+1].ma),Tree[rr].rma+Tree[rr+1].lma);
    Tree[root].mi=min(min(Tree[rr].mi,Tree[rr+1].mi),Tree[rr].rmi+Tree[rr+1].lmi);
}

T4:show

不会

发表评论

电子邮件地址不会被公开。 必填项已用*标注