求助，string导致了MLE
- 板块CF587F Duff is Mad
- 楼主abruce
- 当前回复3
- 已保存回复3
- 发布时间2021/1/11 18:58
- 上次更新2023/11/5 04:55:28
查看原帖
被骇客银狼阻止的越权访问保存失败
求助，string导致了MLE
这是两份代码，一个WA on 53，一个直接 MLE on 7，在学校的OJ上面过了，请问是什么问题？
#include<bits/stdc++.h>
#define lc id<<1
#define rc id<<1|1
using namespace std;
inline int read() {
int __x=0,__f=1;
char __c=getchar();
while(__c<'0'||__c>'9') {
if(__c=='-')__f=-1;
__c=getchar();
}
while(__c>='0'&&__c<='9') {
__x=__x*10+__c-'0';
__c=getchar();
}
return __x*__f;
}
char __F[200];
inline void write(int __x) {
if(__x<0) {
putchar('-');
__x=-__x;
}
if(__x>=10)write(__x/10);
putchar(__x%10+'0');
}
inline string readstr() {
char __ch=getchar();
string __st1="";
while (!((__ch>='a')&&(__ch<='z')))
__ch=getchar();
while ((__ch>='a')&&(__ch<='z'))
__st1+=__ch,__ch=getchar();
return __st1;
}
const int maxn=1e5+5,maxm=1.4e6+5;
struct edge {
int next,to;
} e[maxn];
struct tree {
int l,r,mid,rt;
} t[maxn*4];
int tr[maxm][26],fail[maxm],v[maxm],n,m,tot=1,sn,sc,book[maxn],a[maxn][166],h[maxn],bj[maxn],c[maxn],cnt;
string s[maxn],ls[166];
queue<int> q;
void addedge(int x,int y) {
e[++cnt].next=h[x];
e[cnt].to=y;
h[x]=cnt;
}
void insertrie(string &s,int rot,int u) {
int root=rot,y,len=s.length();
for(register int i=0; i<len; i++) {
y=s[i]-'a';
if(!tr[root][y]) {
tr[root][y]=++tot;
}
root=tr[root][y];
}
v[root]++;
if(rot==1)bj[u]=root;
}
void getfail(int rot) {
for(register int i=0; i<26; i++) {
tr[0][i]=rot;
}
q.push(rot);
while(!q.empty()) {
int u=q.front(),f=fail[u];
q.pop();
v[u]+=v[f];
for(register int i=0; i<26; i++) {
int &j=tr[u][i];
if(!j) {
j=tr[f][i];
continue;
}
fail[j]=tr[f][i];
q.push(j);
}
}
}
void build(int id,int l,int r) {
t[id].l=l,t[id].r=r,t[id].mid=(l+r)/2;
t[id].rt=++tot;
if(l==r) {
return;
}
int mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
}
void insert(int id,int v) {
insertrie(s[v],t[id].rt,v);
if(t[id].l==t[id].r) {
return;
}
if(v<=t[id].mid)insert(lc,v);
else insert(rc,v);
}
void pre(int id) {
getfail(t[id].rt);
if(t[id].l==t[id].r) {
return;
}
pre(lc);
pre(rc);
}
int query1(int id,int l,int r,int k) {
if(t[id].l>=l&&t[id].r<=r) {
int u=t[id].rt,len=s[k].length(),sum=0;
for(register int j=0; j<len; j++) {
u=tr[u][s[k][j]-'a'];
sum+=v[u];
}
return sum;
}
int sum=0;
if(l<=t[id].mid)sum+=query1(lc,l,r,k);
if(r>t[id].mid)sum+=query1(rc,l,r,k);
return sum;
}
void dfs(int u) {
for(register int i=h[u]; i; i=e[i].next) {
int j=e[i].to;
dfs(j);
c[u]+=c[j];
}
}
int main() {
int x,y,z;
n=read(),m=read();
sn=330;
for(register int i=1; i<=n; i++) {
s[i]=readstr();
insertrie(s[i],1,i);
if(s[i].length()>=sn) {
book[i]=++sc;
ls[sc]=s[i];
//cout<<ls[sc]<<endl;
}
}
getfail(1);
//cout<<sn<<endl;
for(register int i=2; i<=tot; i++) {
addedge(fail[i],i);
}
for(register int i=1; i<=sc; i++) {
int u=1,len=ls[i].length();
memset(c,0,sizeof(c));
for(register int j=0; j<len; j++) {
u=tr[u][ls[i][j]-'a'];
c[u]++;
}
dfs(1);
for(register int j=1; j<=n; j++) {
a[j][i]=a[j-1][i]+c[bj[j]];
}
}
build(1,1,n);
for(register int i=1; i<=n; i++) {
insert(1,i);
}
pre(1);
while(m--) {
x=read(),y=read(),z=read();
write(book[z]?a[y][book[z]]-a[x-1][book[z]]:query1(1,x,y,z));
putchar('\n');
}
return 0;
}
这份代码MLE。
#include<bits/stdc++.h>
#define lc id<<1
#define rc id<<1|1
using namespace std;
char __buf[1<<20],*__p1,*__p2;
//#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<20,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
inline int read() {
int __x=0,__f=1;
char __c=getchar();
while(__c<'0'||__c>'9') {
if(__c=='-')__f=-1;
__c=getchar();
}
while(__c>='0'&&__c<='9') {
__x=__x*10+__c-'0';
__c=getchar();
}
return __x*__f;
}
char __F[200];
inline void write(int __x) {
if(__x<0) {
putchar('-');
__x=-__x;
}
if(__x>=10)write(__x/10);
putchar(__x%10+'0');
}
inline string readstr() {
char __ch=getchar();
string __st1="";
while (!((__ch>='a')&&(__ch<='z')))
__ch=getchar();
while ((__ch>='a')&&(__ch<='z'))
__st1+=__ch,__ch=getchar();
return __st1;
}
const int maxn=1e5+5,maxm=1.4e6+5;
struct tree {
int l,r,mid,rt;
} t[maxn*4];
int tr[maxm][26],fail[maxm],v[maxm],n,m,tot,sn,sc,book[maxn],a[maxn][201],h[maxm],bj[maxm];
string s[maxn],ls[201];
queue<int> q;
void insertrie(string &s,int rot,int u) {
int root=rot,y,len=s.length();
for(register int i=0; i<len; i++) {
y=s[i]-'a';
if(!tr[root][y]) {
tr[root][y]=++tot;
}
root=tr[root][y];
}
v[root]++;
bj[root]=u;
}
void getfail(int rot) {
for(register int i=0; i<26; i++) {
tr[0][i]=rot;
}
q.push(rot);
while(!q.empty()) {
int u=q.front(),f=fail[u];
q.pop();
v[u]+=v[f];
for(register int i=0; i<26; i++) {
int &j=tr[u][i];
if(!j) {
j=tr[f][i];
continue;
}
fail[j]=tr[f][i];
q.push(j);
}
}
}
void build(int id,int l,int r) {
t[id].l=l,t[id].r=r,t[id].mid=(l+r)/2;
t[id].rt=++tot;
if(l==r) {
return;
}
int mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
}
void insert(int id,int v) {
insertrie(s[v],t[id].rt,v);
if(t[id].l==t[id].r) {
return;
}
if(v<=t[id].mid)insert(lc,v);
else insert(rc,v);
}
void pre(int id) {
getfail(t[id].rt);
if(t[id].l==t[id].r) {
return;
}
pre(lc);
pre(rc);
}
int query1(int id,int l,int r,int k) {
if(t[id].l>=l&&t[id].r<=r) {
int u=t[id].rt,len=s[k].length(),sum=0;
for(register int j=0; j<len; j++) {
u=tr[u][s[k][j]-'a'];
sum+=v[u];
}
return sum;
}
int sum=0;
if(l<=t[id].mid)sum+=query1(lc,l,r,k);
if(r>t[id].mid)sum+=query1(rc,l,r,k);
return sum;
}
int main() {
int x,y,z;
n=read(),m=read();
build(1,1,n);
for(register int i=1; i<=n; i++) {
s[i]=readstr();
insert(1,i);
}
//cout<<sn<<endl;
sn=330;
for(register int i=1; i<=n; i++) {
if(s[i].length()>=sn) {
book[i]=++sc;
ls[sc]=s[i];
//cout<<ls[sc]<<endl;
}
}
pre(1);
for(register int i=1; i<=sc; i++) {
int u=t[1].rt,len=ls[i].length(),y,k;
for(register int j=0; j<len; j++) {
y=ls[i][j]-'a';
k=tr[u][y];
while(k>t[1].rt) {
if(bj[k])a[bj[k]][i]++;
k=fail[k];
}
u=tr[u][y];
}
}
for(register int i=1; i<=n; i++) {
for(register int j=1; j<=sc; j++) {
a[i][j]+=a[i-1][j];
}
}
while(m--) {
x=read(),y=read(),z=read();
write(book[z]?a[y][book[z]]-a[x-1][book[z]]:query1(1,x,y,z));
putchar('\n');
}
return 0;
}
这份代码没有MLE
加载中...