QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354601 | #5541. Substring Sort | SolitaryDream# | TL | 1ms | 5628kb | C++14 | 2.6kb | 2024-03-15 18:31:46 | 2024-03-15 18:31:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1e3+7;
const int P=(1ll<<61)-1,bs=13131;
string s[3];
int n;
int pw[N];
int add(int a,int b)
{
return a+b>=P?a+b-P:a+b;
}
int mul(int a,int b)
{
return (__int128)a*b%P;
}
struct T{
int l,r,ls,rs,sz;
array<int,3> ha,tag;
}t[N*2+1];
void update(int x)
{
for(int i=0;i<3;i++)
t[x].ha[i]=add(mul(t[t[x].ls].ha[i],pw[t[t[x].rs].sz]),t[t[x].rs].ha[i]);
}
void app(int x,array<int,3> v)
{
array<int,3> nh,nt;
for(int i=0;i<3;i++)
nh[i]=t[x].ha[v[i]],nt[i]=t[x].tag[v[i]];
t[x].ha=nh,t[x].tag=nt;
}
void pushdown(int x)
{
app(t[x].ls,t[x].tag);
app(t[x].rs,t[x].tag);
for(int i=0;i<3;i++)
t[x].tag[i]=i;
}
int cnt;
int build(int l,int r)
{
int x=++cnt;
t[x].l=l,t[x].r=r;
for(int i=0;i<3;i++)
t[x].tag[i]=i;
t[x].sz=r-l+1;
if(l==r)
{
for(int i=0;i<3;i++)
t[x].ha[i]=s[i][l];
return x;
}
int mid=(l+r)>>1;
t[x].ls=build(l,mid);
t[x].rs=build(mid+1,r);
update(x);
return x;
}
int cmpt(int x,int l,int r,int u,int v)
{
if(l<=t[x].l&&t[x].r<=r)
{
if(t[x].ha[u]==t[x].ha[v])
return 0;
if(t[x].l==t[x].r)
return t[x].ha[u]<t[x].ha[v]?-1:1;
}
pushdown(x);
int mid=(t[x].l+t[x].r)>>1;
int ret=0;
if(l<=mid)
ret=cmpt(t[x].ls,l,r,u,v);
if(ret)
return ret;
return cmpt(t[x].rs,l,r,u,v);
}
void change(int x,int l,int r,array<int,3> v)
{
if(l<=t[x].l&&t[x].r<=r)
{
app(x,v);
return;
}
int mid=(t[x].l+t[x].r)>>1;
pushdown(x);
if(l<=mid)
change(t[x].ls,l,r,v);
if(r>mid)
change(t[x].rs,l,r,v);
update(x);
}
int L,R;
bool cmp(int u,int v)
{
return cmpt(1,L,R,u,v)==-1;
}
void dfs(int u,int x)
{
if(t[x].l==t[x].r)
{
cout<<(char)t[x].ha[u];
return;
}
pushdown(x);
dfs(u,t[x].ls);
dfs(u,t[x].rs);
}
int q;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
pw[0]=1;
for(int i=1;i<=n;i++)
pw[i]=mul(pw[i-1],bs);
for(int i=0;i<3;i++)
{
cin>>s[i];
s[i]=' '+s[i];
}
build(1,n);
while(q--)
{
int l,r;
cin>>l>>r;
array<int,3> f;
iota(f.begin(),f.end(),0);
L=l,R=r;
sort(f.begin(),f.end(),cmp);
change(1,l,r,f);
}
for(int i=0;i<3;i++)
dfs(i,1),cout<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3568kb
input:
5 2 icpca siaja karta 2 4 1 5
output:
iarta kiaja scpca
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
6 6 aabbcc bcacab cbcaba 1 1 2 2 3 3 4 4 5 5 6 6
output:
aaaaaa bbbbbb cccccc
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 1 aba aab aac 1 3
output:
aab aac aba
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
1 1 z y x 1 1
output:
x y z
result:
ok 3 lines
Test #5:
score: -100
Time Limit Exceeded
input:
100000 100000 llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...