QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750896#9406. TriangleeastcloudWA 3ms38660kbC++175.3kb2024-11-15 16:16:052024-11-15 16:16:07

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 16:16:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:38660kb
  • [2024-11-15 16:16:05]
  • 提交

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline

using namespace std;

#define N 2020005

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

char s[N],t[N];
int buc[N],rk[N],ork[N],id[N],R[N],ht[N],ed[N],sa[N];

void get_SA(int n){
    int m=(1<<7),p=0;
    mset(buc,0,max(m+1,n+1));
    for(int i=1;i<=n;i++)buc[rk[i]=t[i]]++;
    for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
    for(int i=n;i>=1;i--)sa[buc[rk[i]]--]=i;
    for(int i=1;i<=n;i++)cerr<<t[i];cerr<<endl;
    for(int w=1;;w<<=1,m=p,p=0){
        for(int i=n;i>n-w;i--)id[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]-w>=1)id[++p]=sa[i]-w;
        mset(buc,0,m+1);
        for(int i=1;i<=n;i++)buc[R[i]=rk[id[i]]]++;
        for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
        for(int i=n;i>=1;i--)sa[buc[R[i]]--]=id[i];
        cpy(ork,rk,n+1);p=0;
        for(int i=1;i<=n;i++){
            rk[sa[i]]=(ork[sa[i]]==ork[sa[i-1]] && ork[sa[i]+w]==ork[sa[i-1]+w]?p:++p);
        }
        if(p==n)break;
    }
}

int cnt[N],nex[N][27],suf[N],tot=1;
int insert(int len){
    int p=1;
    for(int i=1;i<=len;i++){
        int it=s[i]-'a'+1;
        if(!nex[p][it])nex[p][it]=++tot;
        p=nex[p][it];
    }
    cnt[p]++;
    if(cnt[p]>=2)return 0;
    return p;
}

struct BIT{
    int K[N];
    int lowbit(int x){return x&(-x);}
    void add(int x,int val){while(x<N){K[x]+=val;x+=lowbit(x);}}
    int ask(int x){int ans=0;while(x){ans+=K[x];x-=lowbit(x);}return ans;}
}T,G;

struct node{
    int ti,l,r,coef;
    node(int ti=0,int l=0,int r=0,int coef=0):ti(ti),l(l),r(r),coef(coef){}
};
vector<node> P;
struct qry{
    int t,p,coef;
    qry(int t=0,int p=0,int coef=0):t(t),p(p),coef(coef){}
};
vector<qry> Q;

pi I[N];
int sum[N];

void solve(){
    int m=0,idx=0;int n=read();
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);ed[i]=m+1;int len=strlen(s+1);
        int pos=0;if(i==14)cout<<(s+1)<<endl;
        if(pos=insert(len)){
            for(int j=1;j<=len;j++)t[++m]=s[j];
            t[++m]='@';suf[pos]=ed[i];
            I[++idx]=mp(ed[i],len);
        }
        
    }
    get_SA(m);
    for(int i=1;i<=tot;i++)if(cnt[i])sum[rk[suf[i]]]+=cnt[i],T.add(rk[suf[i]],cnt[i]);
    for(int i=1;i<=m;i++)sum[i]+=sum[i-1];
    int res=0;
    for(int i=1;i<=idx;i++){
        int begin=I[i].fi,len=I[i].se,p=1;
        auto trs=[&](int l,int r){
            p=1;
            for(int k=l;k<=r;k++){
                int it=t[k]-'a'+1;
                p=nex[p][it];
            }
        };
        trs(begin,begin+len-1);
        if(cnt[p]>=2){
            int les=sum[rk[suf[p]]-1];
            res+=(cnt[p]*(cnt[p]-1))/2*les;
        }
        if(cnt[p]>=3)res+=(cnt[p]*(cnt[p]-1)*(cnt[p]-2))/6;
        int coef=cnt[p];p=1;

        

        int subtot=0;
        for(int k=begin;k<=begin+len-1;k++){
            int it=t[k]-'a'+1;p=nex[p][it];
            if(k==begin+len-1)break;
            if(!cnt[p])continue;
            int Bst=k+1;int L=rk[Bst]+1,R=rk[begin]-1;
            if(L>R)continue;
            int num=(T.ask(R)-T.ask(L-1));
            //cerr<<begin<<' '<<len<<' '<<k<<' '<<L<<' '<<R<<' '<<rk[suf[p]]<<' '<<num<<endl;
            if(rk[suf[p]]>=L && rk[suf[p]]<=R)res+=coef*(cnt[p]*(cnt[p]-1))/2,num-=cnt[p],subtot+=cnt[p]*cnt[p];
            res+=cnt[p]*coef*num;

            Q.eb(qry(R,rk[suf[p]],1*cnt[p]));Q.eb(qry(L-1,rk[suf[p]],-1*cnt[p]));
            P.eb(node(rk[suf[p]],L,R,cnt[p]));

            G.add(L,cnt[p]);
        }
        sort(Q.begin(),Q.end(),[](qry A,qry B){return A.t<B.t;});
        sort(P.begin(),P.end(),[](node A,node B){return A.ti<B.ti;});
        int pos=-1;
        for(auto [t,l,r,co]:P){
            while(pos+1<Q.size() && Q[pos+1].t<t)pos++,subtot-=Q[pos].coef*G.ask(Q[pos].p);
            G.add(l,co);G.add(r+1,-co);
        }
        while(pos+1<Q.size())pos++,subtot-=Q[pos].coef*G.ask(Q[pos].p);
        for(auto [t,l,r,co]:P)G.add(l,-co),G.add(r+1,co);
        //cerr<<subtot<<endl;
        res+=subtot/2*coef;P.clear();Q.clear();
        //cerr<<res<<endl;
    }
    for(int i=1;i<=tot;i++)if(cnt[i])T.add(rk[suf[i]],-cnt[i]);
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=26;j++)nex[i][j]=0;
        cnt[i]=suf[i]=0;
    }
    mset(sum,0,m+1);mset(sa,0,m+1);mset(rk,0,m+1);
    write(res);putchar('\n');
    tot=0;
}

//把所有字符串插到 trie 里,相同的只在后缀数组里保留一个
//遍历每个字符串,算以他为最长边的时候的方案
//遍历每个前缀,先统一加到树状数组里,在 SA 里找比自己小,比主串小,比后缀大的合法的区间,计数
//自己重复两遍如果没加要加上

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #endif

    int T=read();while(T--)solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 38660kb

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

16
0
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 38584kb

input:

14
1
lfpbavjsm
2
pdtlkfwn
mbd
3
dvqksg
dvqksg
uhbhpyhj
4
ombwb
ombwb
ombwb
ombwb
5
oztclz
oztclz
oztclz
oztclz
kul
6
vco
vco
vco
dtktsqtinm
vco
vco
7
tb
tb
kowbsu
ygkfphcij
tb
uvei
tb
8
vxxtxssht
abnsxbf
bydaae
bydaae
udalyvmcef
bydaae
bydaae
bydaae
9
aaze
zvyonw
qjfv
mmhkef
qjfv
qjfv
qjfv
mmhkef
qj...

output:

0
0
0
4
10
20
10
20
41
14
63
74
18
vgxod
11099

result:

wrong answer 14th lines differ - expected: '11081', found: 'vgxod'