QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#79553 | #5014. 复读程度 | NATURAL6 | 0 | 1045ms | 168212kb | C++14 | 8.0kb | 2023-02-20 13:30:09 | 2023-02-20 13:30:10 |
Judging History
answer
// xtqqwq
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T 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=900;
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 lst,cnt,ncnt,p,np;
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 ins(int c){
len[np=++cnt]=len[p=lst]+1,siz[lst=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];
}
}T[2];
void init(){
for(int i=1;i<=T[0].cnt;i+=B) lf[++m]=i,rg[m]=min(i+B-1,T[0].cnt);
for(int i=1;i<=m;i++) for(int j=lf[i];j<=rg[i];j++) bl[j]=i;
}
namespace sub2{
vector<node> qry[2][200005];
void work(){
for(int i=1;i<=bcnt;i++){
for(int k=0;k<2;k++){
bit::timer++;
sort(qry[k][i].begin(),qry[k][i].end());
int now=(int)qry[k][i].size()-1;
while(now>=0&&qry[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(T[k^1].dfn[r],k==0?vl[r]:vr[r]);
while(now>=0&&vec[k^1][i].size()-j-1==qry[k][i][now].x){
node nd=qry[k][i][now];
ans[nd.id]+=occ[i]*nd.w*bit::ask(nd.y);
now--;
}
}
}
}
}
}
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+n;i+=B) lf[++m]=i,rg[m]=min(i+B-1,n+n);
for(int i=1;i<=m;i++) for(int j=lf[i];j<=rg[i];j++) bl[j]=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==0?vr[vec[l][i][j]]:vl[vec[l][i][j]];
}
for(int i=1;i<=T[l^1].cnt;i++){
int u=T[l^1].rnk[i];
int bel=T[l^1].tag[u];
int L=vec[l][bel].size()-T[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=T[l].rnk[j],dis=0;
int bo=T[l].tag[v];
dis=T[l].len[rt[l][bo]]-T[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();
T[0].cnt=T[0].lst=T[1].cnt=T[1].lst=1;
for(int i=1;i<=n;i++) T[0].ins(s[i]-'a'),T[0].rg[T[0].ed[i]=T[0].lst]=i;
for(int i=n;i>=1;i--) T[1].ins(s[i]-'a'),T[1].rg[T[1].ed[i]=T[1].lst]=i;
T[0].init();
T[1].init();
for(int i=2;i<=T[0].cnt;i++){
int u=T[0].A[i];
int L=T[0].rg[u]-T[0].len[u]+1,R=T[0].rg[u];
int id=T[1].find(T[1].ed[L],R-L+1);
if(T[1].len[id]==R-L+1){
T[0].tag[u]=T[1].tag[id]=++bcnt;
rt[0][bcnt]=u,rt[1][bcnt]=id;
occ[bcnt]=T[0].siz[u];
}
}
for(int i=0;i<2;i++){
for(int j=T[i].cnt;j>=2;j--){
int u=T[i].A[j];
if(!T[i].tag[u])for(int k=0;k<26;k++) if(T[i].ch[u][k]) T[i].tag[u]=T[i].tag[T[i].ch[u][k]];
vec[i][T[i].tag[u]].pb(u);
}
}
for(int i=bcnt;i;i--){
for(auto r:vec[0][i]){
for(auto v:T[0].adj[r]) vr[r]+=vr[v];
if(T[0].len[r]==T[0].rg[r]) vr[r]+=wr[T[0].rg[r]];
}
for(auto r:vec[1][i]){
for(auto v:T[1].adj[r]) vl[r]+=vl[v];
if(T[1].len[r]==n-T[1].rg[r]+1) vl[r]+=wl[T[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=T[1].find(T[1].ed[x1],y1-x1+1);
int p0=T[0].find(T[0].ed[y2],y2-x2+1);
int l1=T[0].dfn[p0],r1=T[0].dfn[p0]+T[0].sz[p0]-1;
int l2=T[1].dfn[p1],r2=T[1].dfn[p1]+T[1].sz[p1]-1;
if(T[1].tag[p1]==T[0].tag[p0]){
int len=T[0].len[rt[0][T[1].tag[p1]]]-(T[1].rg[p1]-T[1].rg[rt[1][T[1].tag[p1]]]+T[0].rg[rt[0][T[1].tag[p1]]]-T[0].rg[p0]);
if(T[0].num[p0]-1>=T[1].rg[p1]-T[1].rg[rt[1][T[1].tag[p1]]]&&(y1-x1+1>len||y2-x2+1>len)) ans[i]-=occ[T[1].tag[p1]]*vl[p1]*vr[p0];
}
else{
sub2::qry[0][T[0].tag[p0]].pb(node(T[0].len[p0]-(y2-x2),r2,i,-vr[p0]));
sub2::qry[0][T[0].tag[p0]].pb(node(T[0].num[p0],r2,i,vr[p0]));
sub2::qry[0][T[0].tag[p0]].pb(node(T[0].len[p0]-(y2-x2),l2-1,i,vr[p0]));
sub2::qry[0][T[0].tag[p0]].pb(node(T[0].num[p0],l2-1,i,-vr[p0]));
sub2::qry[1][T[1].tag[p1]].pb(node(T[1].len[p1]-(y1-x1),r1,i,-vl[p1]));
sub2::qry[1][T[1].tag[p1]].pb(node(T[1].num[p1],r1,i,vl[p1]));
sub2::qry[1][T[1].tag[p1]].pb(node(T[1].len[p1]-(y1-x1),l1-1,i,vl[p1]));
sub2::qry[1][T[1].tag[p1]].pb(node(T[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));
}
init();
sub2::work();
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: 10ms
memory: 41960kb
input:
500 500 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
15684812251943096724 6238062835513588043 2650819674667932599 15363331807929279863 12432116844389017331 5930884701573437681 13308606485715577996 18120587083204373754 10115500153590798132 10378469268004772228 6477775347902512596 174248041887487186 5414757901969109248 883762801052165866 114455430029211...
result:
wrong answer 1st lines differ - expected: '15720454042420499810', found: '15684812251943096724'
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: 1045ms
memory: 168212kb
input:
100000 100000 zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
4758451521627630019 6317977285640306202 2515615007391117277 10258390208398592090 2420680467965525356 2241842638676820870 16124608149153951318 14073055445940096863 9161814903109214738 3784526005034855261 15652374215943763975 10901891393722244637 56161877198334162 5632801252358379773 24676463842231608...
result:
wrong answer 1st lines differ - expected: '16102224067619618967', found: '4758451521627630019'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%