QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#79933 | #5014. 复读程度 | NATURAL6 | 0 | 617ms | 168824kb | C++14 | 8.0kb | 2023-02-21 13:14:39 | 2023-02-21 13:14:40 |
Judging History
answer
// xtqqwq
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename sa> bool chkmax(sa &x,sa y){return x<y?x=y,1:0;}
template<typename sa> bool chkmin(sa &x,sa y){return x>y?x=y,1:0;}
ull readint(){
ull x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node{
int x,y,id; ull w;
node(int x=0,int y=0,int id=0,ull w=0):x(x),y(y),id(id),w(w){}
bool operator<(const node c)const{return x==c.x?y<c.y:x<c.x;}
};
const int B=400;
int n,m,q,bcnt;
int occ[200005],rt[2][200005],bl[200005],lf[1005],rg[1005];
ull ans[100005],wl[100005],wr[100005],vl[200005],vr[200005];
char s[100005];
vector<int> vec[2][200005];
vector<node> qry;
namespace bit{
int timer;
int mark[200005];
ull val[200005];
void add(int x,ull c){
for(;x<=n+n;x+=(x&(-x))){
if(mark[x]!=timer) mark[x]=timer,val[x]=0;
val[x]+=c;
}
}
ull ask(int x){
ull ret=0;
for(;x;x-=(x&(-x))) ret+=mark[x]==timer?val[x]:0;
return ret;
}
}
struct sam{
int T,cnt,ncnt;
int ch[200005][26],fa[200005],len[200005],siz[200005],tmp[200005],A[200005],rg[200005],tag[200005],ed[100005],sz[200005],son[200005],dfn[200005],rnk[200005],top[200005],num[200005];
vector<int> adj[200005];
void addc(int c){
int p=T,np=++cnt; T=np,len[np]=len[p]+1,siz[np]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) return (void)(fa[np]=1);
int q=ch[p][c];
if(len[q]==len[p]+1) return (void)(fa[np]=q);
int nq=++cnt;
len[nq]=len[p]+1,rg[nq]=rg[q];
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
void dfs(int u){
dfn[u]=++ncnt,rnk[ncnt]=u;
if(son[u]) top[son[u]]=top[u],dfs(son[u]);
for(auto v:adj[u]){
if(v==son[u]) continue;
top[v]=v;
dfs(v);
}
}
void init(){
for(int i=1;i<=cnt;i++) tmp[len[i]]++;
for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
for(int i=cnt;i>=1;i--) A[tmp[len[i]]--]=i;
for(int i=1;i<=cnt;i++) sz[i]=1;
for(int i=cnt;i>=2;i--){
int u=A[i];
adj[fa[u]].pb(u);
siz[fa[u]]+=siz[u];
sz[fa[u]]+=sz[u];
num[u]=len[u]-len[fa[u]];
if(sz[u]>sz[son[fa[u]]]) son[fa[u]]=u;
}
top[1]=1; dfs(1);
}
int find(int x,int d){
while(len[fa[top[x]]]>=d) x=fa[top[x]];
int L=dfn[top[x]],R=dfn[x],res=0;
while(L<=R){
int mid=(L+R)/2;
if(len[rnk[mid]]>=d) res=mid,R=mid-1;
else L=mid+1;
}
return rnk[res];
}
}sa[2];
vector<node> subqry[2][200005];
namespace blo{
int m;
int lf[1005],rg[1005],bl[200005];
ull a[200005],val[200005],tag[1005];
void init(){
for(int i=1;i<=n*2;++i)bl[i]=(i-1)/B+1,rg[bl[i]]=i;
for(int i=n*2;i;--i)lf[bl[i]]=i;
}
void clear(){
for(int i=1;i<=n+n;i++) val[i]=a[i]=0;
for(int i=1;i<=m;i++) tag[i]=0;
}
void add(int l,int r,ull c){
int lb=bl[l],rb=bl[r];
if(lb==rb){
for(int i=l;i<=r;i++) val[i]+=c*a[i];
return;
}
for(int i=l;i<=rg[lb];i++) val[i]+=c*a[i];
for(int i=lf[rb];i<=r;i++) val[i]+=c*a[i];
for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
}
ull ask(int x){
return val[x]+tag[bl[x]]*a[x];
}
}
namespace sub1{
int cnt;
int plq[400005],st[200005];
ull val[800005];
vector<node> qry2[2][200005];
void solve(){
for(int l=0;l<2;l++){
int now=1;
blo::clear();
for(int i=1;i<=bcnt;i++){
st[i]=now;
now+=vec[l][i].size();
for(int j=0;j<vec[l][i].size();j++) blo::a[st[i]+j]=(!l)?vr[vec[l][i][j]]:vl[vec[l][i][j]];
}
for(int i=1;i<=sa[l^1].cnt;i++){
int u=sa[l^1].rnk[i];
int bel=sa[l^1].tag[u];
int L=vec[l][bel].size()-sa[l^1].num[u],R=vec[l][bel].size()-1;
L+=st[bel],R+=st[bel];
blo::add(L,R,occ[bel]*(l==0?vl[u]:vr[u]));
for(auto r:qry2[l][i]){
for(int j=r.x;j<=r.y;j++){
int v=sa[l].rnk[j],dis=0;
int bo=sa[l].tag[v];
dis=sa[l].len[rt[l][bo]]-sa[l].len[v];
val[r.id]+=r.w*blo::ask(st[bo]+vec[l][bo].size()-dis-1);
}
}
}
}
}
void work(){
sort(qry.begin(),qry.end(),[&](node x,node y){
if((x.x-1)/B==(y.x-1)/B) return (x.x-1)/B%2==0?x.y<y.y:x.y>y.y;
return (x.x-1)/B<(y.x-1)/B;
});
int nx=0,ny=0;
for(int i=0;i<qry.size();i++){
node r=qry[i];
if(nx<r.x) qry2[0][ny].pb(node(nx+1,r.x,++cnt,1)),nx=r.x;
if(ny<r.y) qry2[1][nx].pb(node(ny+1,r.y,++cnt,1)),ny=r.y;
if(nx>r.x) qry2[0][ny].pb(node(r.x+1,nx,++cnt,-1)),nx=r.x;
if(ny>r.y) qry2[1][nx].pb(node(r.y+1,ny,++cnt,-1)),ny=r.y;
plq[i]=cnt;
}
blo::init();
solve();
for(int i=1;i<=cnt;i++) val[i]+=val[i-1];
for(int i=0;i<qry.size();i++) ans[qry[i].id]+=qry[i].w*val[plq[i]];
}
}
int main(){
n=readint(); q=readint();
scanf("%s",s+1);
for(int i=1;i<=n;i++) wl[i]=readint();
for(int i=1;i<=n;i++) wr[i]=readint();
sa[0].cnt=sa[0].T=sa[1].cnt=sa[1].T=1;
for(int i=1;i<=n;i++) sa[0].addc(s[i]-'a'),sa[0].rg[sa[0].ed[i]=sa[0].T]=i;
for(int i=n;i>=1;i--) sa[1].addc(s[i]-'a'),sa[1].rg[sa[1].ed[i]=sa[1].T]=i;
sa[0].init();
sa[1].init();
for(int i=2;i<=sa[0].cnt;i++){
int u=sa[0].A[i];
int L=sa[0].rg[u]-sa[0].len[u]+1,R=sa[0].rg[u];
int id=sa[1].find(sa[1].ed[L],R-L+1);
if(sa[1].len[id]==R-L+1){
sa[0].tag[u]=sa[1].tag[id]=++bcnt;
rt[0][bcnt]=u,rt[1][bcnt]=id;
occ[bcnt]=sa[0].siz[u];
}
}
for(int i=0;i<2;i++){
for(int j=sa[i].cnt;j>=2;j--){
int u=sa[i].A[j];
if(sa[i].tag[u]) continue;
for(int k=0;k<26;k++) if(sa[i].ch[u][k]) sa[i].tag[u]=sa[i].tag[sa[i].ch[u][k]];
}
}
for(int i=0;i<2;i++){
for(int j=2;j<=sa[i].cnt;j++){
int u=sa[i].A[j];
vec[i][sa[i].tag[u]].pb(u);
}
}
for(int i=bcnt;i>=1;i--){
for(auto r:vec[0][i]){
for(auto v:sa[0].adj[r]) vr[r]+=vr[v];
if(sa[0].len[r]==sa[0].rg[r]) vr[r]+=wr[sa[0].rg[r]];
}
for(auto r:vec[1][i]){
for(auto v:sa[1].adj[r]) vl[r]+=vl[v];
if(sa[1].len[r]==n-sa[1].rg[r]+1) vl[r]+=wl[sa[1].rg[r]];
}
}
int x1,y1,x2,y2;
for(int i=1;i<=q;i++){
x1=readint(); y1=readint(); x2=readint(); y2=readint();
int p1=sa[1].find(sa[1].ed[x1],y1-x1+1);
int p0=sa[0].find(sa[0].ed[y2],y2-x2+1);
int l1=sa[0].dfn[p0],r1=sa[0].dfn[p0]+sa[0].sz[p0]-1;
int l2=sa[1].dfn[p1],r2=sa[1].dfn[p1]+sa[1].sz[p1]-1;
if(sa[1].tag[p1]==sa[0].tag[p0]){
int len=sa[0].len[rt[0][sa[1].tag[p1]]]-(sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]+sa[0].rg[rt[0][sa[1].tag[p1]]]-sa[0].rg[p0]);
if(sa[0].num[p0]-1>=sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]&&(y1-x1+1>len||y2-x2+1>len)) ans[i]-=occ[sa[1].tag[p1]]*vl[p1]*vr[p0];
}
else{
subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),r2,i,-vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].num[p0],r2,i,vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),l2-1,i,vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].num[p0],l2-1,i,-vr[p0]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),r1,i,-vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].num[p1],r1,i,vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),l1-1,i,vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].num[p1],l1-1,i,-vl[p1]));
}
qry.pb(node(r1,r2,i,1));
qry.pb(node(r1,l2-1,i,-1));
qry.pb(node(l1-1,r2,i,-1));
qry.pb(node(l1-1,l2-1,i,1));
}
for(int i=1;i<=bcnt;i++){
for(int k=0;k<2;k++){
bit::timer++;
sort(subqry[k][i].begin(),subqry[k][i].end());
int now=(int)subqry[k][i].size()-1;
while(now>=0&&subqry[k][i][now].x==vec[k^1][i].size()) now--;
for(int j=0;j<vec[k^1][i].size();j++){
int r=vec[k^1][i][j];
bit::add(sa[k^1].dfn[r],k==0?vl[r]:vr[r]);
while(now>=0&&vec[k^1][i].size()-j-1==subqry[k][i][now].x){
node nd=subqry[k][i][now];
ans[nd.id]+=occ[i]*nd.w*bit::ask(nd.y);
now--;
}
}
}
}
sub1::work();
for(int i=1;i<=q;i++) printf("%llu\n",ans[i]);
puts("-");
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 41848kb
input:
500 500 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
15720454042420499810 4058077030882532408 14651762045124606089 4030024243931986061 18033423360813892607 9470601111824364484 3883374861354698625 16650831689368240202 8339028189650687576 2683289915379600554 13133811958066776394 14181220923901262251 18173739360450512256 13142314545999179754 148925491596...
result:
wrong output format Extra information in the output file
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 617ms
memory: 168824kb
input:
100000 100000 zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
16102224067619618967 2409962914769200003 427496158535942638 17668679206267169316 9612725428377010375 16283030984784184667 14966758574838045581 8108029333542434517 5821899279772898061 7354415533246368927 15016230232022193055 9072126619623269970 5490256818353051548 432088324301719512 13681741566473101...
result:
wrong output format Extra information in the output file
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%