QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405579#7901. Basic Substring StructureRikku_eqWA 31ms21292kbC++144.1kb2024-05-06 07:41:582024-05-06 07:42:00

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 07:42:00]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:21292kb
  • [2024-05-06 07:41:58]
  • 提交

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'