NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #200503 | #2422. 名字 | xiaopangfeiyu | 100 | 407ms | 16032kb | C++11 | 5.5kb | 2024-01-04 10:28:26 | 2024-01-04 12:07:13 |
answer
/*
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/_/_/_/ _/ _/_/_/_/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/ _/_/_/_/_/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
#include <bits/stdc++.h>
#define REN 1000
#define REA 26
#define RES 100000
#define MAXN (REN+5)
#define MAXA (REA+5)
#define MAXS (RES+5)
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') {f=-1;} c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
return x*f;
}
void write(int x)
{
if(x<0) {putchar('-');x=-x;}
if(x>9) {write(x/10);}
putchar(x%10+'0');
}
int n,m;
string c[MAXN];
/// @brief Edge
struct edge {int to,next;} e[MAXS*2];
int tot,head[MAXS];
void add(int x,int y) {tot++;e[tot].to=y;e[tot].next=head[x];head[x]=tot;}
int dfn[MAXS],siz[MAXS],dfx;
void dfs(int x,int fa)
{
dfn[x]=++dfx;
siz[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;if(v==fa) {continue;}
dfs(v,x);
siz[x]+=siz[v];
}
}
/// @brief Trie
struct Trie
{
int son[MAXA];
int ed,fail;
}t[MAXS];
int ED[MAXN];
int cnt;
void add(int x)
{
int now=0,l=c[x].size();
for(int i=0;i<l;i++)
{
if(t[now].son[c[x][i]-'a']) {now=t[now].son[c[x][i]-'a'];}
else {now=t[now].son[c[x][i]-'a']=++cnt;}
}
t[now].ed++;
ED[x]=now;
}
void build()
{
queue<int>q;
for(int i=0;i<REA;i++) {if(t[0].son[i]) {q.push(t[0].son[i]);}}
while(!q.empty())
{
int x=q.front();q.pop();add(t[x].fail,x);
for(int i=0;i<REA;i++)
{
if(t[x].son[i]) {t[t[x].son[i]].fail=t[t[x].fail].son[i];q.push(t[x].son[i]);}
else {t[x].son[i]=t[t[x].fail].son[i];}
}
}
}
/// @brief Bit
struct Bit
{
int a[MAXS];
int lowbit(int x) {return x&-x;}
void add(int x,int k) {while(x<=RES) {a[x]+=k;x+=lowbit(x);}}
int ask(int x) {int res=0;while(x) {res+=a[x];x-=lowbit(x);} return res;}
}Bit;
/// @brief Calc
void ins(int x)
{
int now=0,l=c[x].size();
for(int i=0;i<l;i++) {now=t[now].son[c[x][i]-'a'];Bit.add(dfn[now],1);}
}
void era(int x)
{
int now=0,l=c[x].size();
for(int i=0;i<l;i++) {now=t[now].son[c[x][i]-'a'];Bit.add(dfn[now],-1);}
}
int query(int x) {return Bit.ask(dfn[x]+siz[x]-1)-Bit.ask(dfn[x]-1);}
int p[MAXN][MAXN];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
time_t st=clock();
int i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++) {cin>>c[i];add(i);}
build();
dfs(0,-1);
for(i=1;i<=n;i++)
{
ins(i);
for(j=1;j<=n;j++) {p[i][j]=query(ED[j]);}
era(i);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
p[i][j]+=p[i-1][j];
}
}
while(m--)
{
int l=read(),r=read(),x=read();
cout<<p[r][x]-p[l-1][x]<<'\n';
}
time_t ed=clock();
double ret=double(ed-st)/CLOCKS_PER_SEC;
cerr<<endl<<ret<<'s';
return 0;
}
/*
_/ _/
_/ _/
_/ _/
_/ _/
_/ _/ _/
_/ _/_/_/ _/ _/ _/_/_/ _/
_/_/_/_/_/ _/_/ _/ _/ _/ _/_/_/ _/_/_/_/_/ _/_/ _/ _/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/_/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/
_/_/_/_/_/ _/ _/ _/ _/ _/_/_/ _/ _/ _/_/_/_/ _/_/_/ _/_/_/ _/
_/
_/
_/
_/
_/
_/
*/
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1448kb
input:
10 100 bc a aaa aaaccaaaca caaabacbcaaaaccaaaaaccaaacaccaaaa aaabacacbccbccaaabacbc accaaaa aaaccaaa...
output:
12 0 1 48 7 0 56 1 15 3 1 1 49 46 11 18 4 5 13 45 1 4 32 18 1 1 7 10 0 18 1 5 1 1 1 4 53 55 1 24 4 1...
result:
ok 100 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1428kb
input:
5 100 ejmljknnjeldejmljknje ldejmljknnjeldejmljknnjfldejmlj jmkjknjeld fldejmljknnjeldejmljknjeldejm...
output:
6 5 1 7 10 5 8 2 6 6 3 8 4 5 4 1 5 4 9 5 7 3 6 5 4 9 5 4 5 3 5 9 9 8 10 5 1 4 3 2 8 4 4 1 1 8 7 5 4 ...
result:
ok 100 lines
Test #3:
score: 10
Accepted
time: 0ms
memory: 1712kb
input:
50 1000 aaacaaaabaaaaaaa a aaaacaaaabaaaaaaaabaaaa aaaaaaaaacaaaabaaaaaaaabaaaaaaaaaaa acbbaaabacaaa...
output:
129 77 0 21 274 11 72 109 26 7 284 18 173 19 349 8 15 5 27 6 51 311 39 371 1 3 44 6 12 492 323 346 3...
result:
ok 1000 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 1636kb
input:
30 1000 mgenjcfodhnmgenjcfodhnm genjcfodhnmgenjcfodhnmgenjcfodhnmenjcfodhnmgenjcfodhnmenjcfodhnmgenj...
output:
23 10 77 28 11 25 40 8 56 41 15 0 2 39 2 52 79 4 60 4 10 40 20 84 82 8 0 4 42 24 6 68 23 3 7 10 77 4...
result:
ok 1000 lines
Test #5:
score: 10
Accepted
time: 50ms
memory: 11732kb
input:
500 100000 bcabcbbbcacaabccbccacaccbcacbccccbbaaabbabcbcccaababccbcabcbbbcacaabccbccacaccbcacb cccbb...
output:
14 3954 226 633 528 2614 257 53 440 148 2144 768 268 17 284 185 234 30 481 495 202 0 1338 1694 4910 ...
result:
ok 100000 lines
Test #6:
score: 10
Accepted
time: 45ms
memory: 13184kb
input:
500 100000 ehecbhadefejeehecehecbhadefejeehecehecbhadefejeehecehecbhadefejeehecehecbhadefejeehecehec...
output:
251 669 335 2013 1080 23 196 450 4697 1291 35 32 1332 9 45 877 723 1340 327 138 225 218 376 194 48 1...
result:
ok 100000 lines
Test #7:
score: 10
Accepted
time: 51ms
memory: 15064kb
input:
200 100000 cefdicgefchdcbbfabajbdhcga efchcgacfahcgacfaaicfbhihciadedhacafcefdicgefchcgacfahcgacfaai...
output:
6 150 1 380 125 482 75 560 7 180 13 0 134 41 5 599 299 6 23 108 0 171 212 220 39 136 9 62 100 132 8 ...
result:
ok 100000 lines
Test #8:
score: 10
Accepted
time: 90ms
memory: 12900kb
input:
500 100000 qhyovpqmdmxzpedsswqrydaogpfjitkxfowgmxglflchcnxzjkcfqhylvpqmdmxzpedsswqrydaogpfjitkxfowgm...
output:
206 393 721 78 191 1162 84 3302 1404 918 31 57 62 234 27 150 2744 1260 88 71 193 208 1437 853 2093 4...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 87ms
memory: 16032kb
input:
200 100000 jjidrjrmjjhkrxsraaaqduplrcznisidrjrmjjidxjrmjjrxsraaaqaaqduslrcznisidrjrmjjidrjrmjjhkrxsr...
output:
6 390 975 291 3 136 6 264 160 125 98 1794 1 17 493 0 2 310 40 1589 11 3 81 146 13 450 5 216 11 66 43...
result:
ok 100000 lines
Test #10:
score: 10
Accepted
time: 84ms
memory: 12216kb
input:
1000 100000 cbabbcbbbbcbbbccacbabbcbbbbcbbbccacbabbcbbbbcbbbccacbabbcbbbbcbbbccacbabbcbb bccacb babb...
output:
23 3036 159 187 11472 909 2 257 173 96 1070 21215 459 920 2680 7901 17396 513 3992 1460 31684 4245 2...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed
