QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750892 | #9406. Triangle | eastcloud | WA | 3ms | 38712kb | C++17 | 5.3kb | 2024-11-15 16:15:19 | 2024-11-15 16:15:19 |
Judging History
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(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;
cerr<<begin<<' '<<len<<endl;
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: 38712kb
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: 38692kb
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 11099
result:
wrong answer 14th lines differ - expected: '11081', found: '11099'