QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405579 | #7901. Basic Substring Structure | Rikku_eq | WA | 31ms | 21292kb | C++14 | 4.1kb | 2024-05-06 07:41:58 | 2024-05-06 07:42:00 |
Judging History
answer
#include <bits/stdc++.h>
#define N 200005
#define mod 1000000007998244353
#define Base 1000000003
using namespace std;
typedef long long ll;
int T;
int s[N+1];
int n, len[N];
ll tgsum[N], tgcnt[N], rec[N];
vector <int> vec0[N], vec1[N];
ll bit[N], pwBS[N];
inline void addmod (ll &a, ll b) { (a+=b)%=mod; }
void upd (int x, ll num) { while (x<=n) { addmod(bit[x], num); x+=(x&(-x)); } }
ll qry (int x) { ll res=0; while (x) { addmod(res, bit[x]); x-=(x&(-x)); } return res; }
int lcp (int i, int j)
{
if (i>j) { swap(i, j); }
int l=0, r=n-j+1, res=0;
ll qi=qry(i-1), qj=qry(j-1);
while (l<=r) {
int md=(l+r)/2;
ll res1=(__int128)(qry(i+md-1)-qi)*pwBS[j-i]%mod;
ll res2=(qry(j+md-1)-qj);
res1=(res1+mod)%mod;
res2=(res2+mod)%mod;
if (res1==res2) { res=md; l=md+1; }
else { r=md-1; }
}
return res;
}
void add (int l, int r, ll num)
{
tgsum[l]+=num; tgsum[r+1]-=num;
tgcnt[l]++; tgcnt[r+1]--;
}
void clr ()
{
for (int i=1; i<=n*2+3; i++) { tgsum[i]=0; tgcnt[i]=0; }
for (int i=1; i<=n*2+3; i++) { bit[i]=0; }
for (int i=1; i<=n*2+3; i++) { len[i]=0; }
for (int i=1; i<=n*2+3; i++) { vec0[i].clear(); vec1[i].clear(); rec[i]=0; s[i]=0; }
}
void solve ()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) { scanf("%d", &s[i]); }
s[n+1]=0;
// for (int i=1; i<=n; i++) { s[i]=rand()%2+1; }
for (int i=1; i<=n; i++) { upd(i, (__int128)s[i]*pwBS[i-1]%mod); }
for (int i=1; i<=n; i++) { len[i]=lcp(1, i); }
ll res=0;
for (int i=1; i<=n; i++) { res+=len[i]; }
for (int i=2; i<=n; i++) {
int lpre=1, rpre=len[i];
int lsuf=i, rsuf=i+len[i]-1;
rpre=min(rpre, lsuf-1);
add(lpre, rpre, len[i]);
add(lsuf, rsuf, i+len[i]-1);
vec0[i+len[i]].push_back(i);
if (len[i]+1>rsuf || len[i]+1<lsuf) { vec1[len[i]+1].push_back(i); }
}
ll prt=0, psum=0, pcnt=0;
for (int i=1; i<=n; i++) {
psum+=tgsum[i]; pcnt+=tgcnt[i];
ll mxRec=0;
int org=s[i];
for (int j=0; j<(int)vec0[i].size(); j++) {
int id=vec0[i][j];
if (s[len[id]+1]==org) { continue; }
upd(i, (__int128)(s[len[id]+1]-s[i])*pwBS[i-1] %mod );
rec[s[len[id]+1]]+=lcp(1, id)-len[id];
// cout<<i<<" "<<id<<" "<<len[id]<<" "<<lcp(1, id)<<endl;
mxRec=max(mxRec, rec[s[len[id]+1]]);
s[i]=s[len[id]+1];
}
for (int j=0; j<(int)vec1[i].size(); j++) {
int id=vec1[i][j];
if (s[id+len[id]]==org) { continue; }
upd(i, (__int128)(s[id+len[id]]-s[i])*pwBS[i-1] %mod );
rec[s[id+len[id]]]+=lcp(1, id)-len[id];
// cout<<i<<" "<<id<<" "<<len[id]<<" "<<lcp(1, id)<<endl;
mxRec=max(mxRec, rec[s[id+len[id]]]);
s[i]=s[id+len[id]];
}
ll ans=res+mxRec-(psum-pcnt*(i-1));
// ll tmp=0;
// upd(i, (__int128)((org==1 ? 2 : 1)-s[i])*pwBS[i-1] %mod );
// s[i]=(org==1 ? 2 : 1);
// for (int j=1; j<=n; j++) { cout<<s[j]<<" "; } cout<<endl;
// for (int j=1; j<=n; j++) {
// tmp+=lcp(1, j);
// }
// cout<<ans<<" "<<tmp<<endl;
prt+=(ans^i);
// cout<<res<<" "<<mxRec<<" "<<psum-pcnt*(i-1)<<endl;
upd(i, (__int128)(org-s[i])*pwBS[i-1] %mod );
s[i]=org;
for (int j=0; j<(int)vec0[i].size(); j++) {
int id=vec0[i][j];
if (s[len[id]+1]==org) { continue; }
rec[s[len[id]+1]]=0;
}
for (int j=0; j<(int)vec1[i].size(); j++) {
int id=vec1[i][j];
if (s[id+len[id]]==org) { continue; }
rec[s[id+len[id]]]=0;
}
}
printf("%lld\n", prt);
clr();
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
pwBS[0]=1; for (int i=1; i<=200000; i++) { pwBS[i]=(__int128)pwBS[i-1]*Base%mod; }
scanf("%d", &T);
while (T--) { solve(); }
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 21292kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 31ms
memory: 20924kb
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 128 347 3 211 9 265 363 278 15 95 111 58 348 225 3 335 364 377 317 3 19 122 66 15 83 36 258 11 63 28 90 85 103 252 191 21 48 303 63 102 20 24 66 316 362 266 310 355 281 326 281 231 312 3 318 54 328 3 70 32 147 310 39 338 90 242 3 165 346 245 20 155 3 404 393 392 81 269 360 20 54 21 279 3 17 351 3...
result:
wrong answer 12th lines differ - expected: '114', found: '111'