QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#807694 | #7901. Basic Substring Structure | juan_123 | WA | 38ms | 24520kb | C++14 | 3.9kb | 2024-12-10 10:28:34 | 2024-12-10 10:28:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
#define int long long
#define ull unsigned long long
const ull base = 998244353;
int p[200005];
int n;
int a[200005];
int k[200005],b[200005],c[200005];
int ans[200005];
//答案表示为 ki+b
int r[200005],pos[200005],rr[200005];
ull pre[200005],pw[200005];
vector<pair<int,int> >s[200005];
//从 i 位置开始匹配能到哪里
//第一个不一样的位置
//不考虑第一个不一样的位置后能匹配到哪里
ull calc(int l,int r,int pos =0){
if(l>r)return 0;
if(!pos)return pre[r]-pre[l-1]*pw[r-l+1];
if(l<=pos and pos<=r){
ull x1 = calc(l,pos-1),x2 = calc(pos+1,r);
ull x = (x1*base+a[pos])*pw[r-pos]+x2;
return x;
}
return calc(l,r);
}
void add(int l,int r,int K,int C,int id){
if(l>r)return;
// if(l<=3 and r>=3)cout << l << " " << r << " " << id << " " << K << " " << C << endl;
k[l]+=K,k[r+1]-=K;
c[l]+=C,c[r+1]-=C;
}
int query(int pos,int c,int i){
int l =i,r = n;
// cout << " " << pos << " " << c << " " << i << endl;
swap(a[pos],c);
// cout << a[pos] << endl;
while(l<r){
int mid = l+r+1>>1;
int len = mid-i+1;
// cout << len << " " << calc(1,len,pos) << " " << calc(i,mid,pos) << endl;
if(calc(1,len,pos) == calc(i,mid,pos))l = mid;
else r = mid-1;
}
swap(a[pos],c);
return l;
}
void solve(){
cin >> n;
for(int i = 1;i<=n;i++)p[i] = i;random_shuffle(p+1,p+1+n);
for(int i = 1;i<=n;i++)cin >> a[i];
for(int i = 1;i<=n;i++)a[i] = p[a[i]];
for(int i =0;i<=n+1;i++)s[i].clear(),k[i]=b[i]=c[i]=0;
for(int i = 1;i<=n;i++)pre[i] = pre[i-1]*base+a[i];
r[1]=n,pos[1]=n+1,rr[1]=n;
for(int i = 2;i<=n;i++){
int* xx = r;
int l = 0,r = n-i+1;
while(l<r){
int mid = l+r+1>>1;
if(calc(1,mid) == calc(i,i+mid-1)){
l = mid;
}else r = mid-1;
}
xx[i] = i+l-1;
// cout << " " << r;
pos[i] = i+l;
if(pos[i]>=n){
rr[i] = n;
continue;
}
// cout << " " << pos[i] << " " << a[l+1] << endl;
rr[i] = query(pos[i],a[l+1],i);
}
// cout << endl;
// for(int i = 1;i<=n;i++)cout << r[i] << " ";cout << endl;
c[1]=n;
// for(int i = 1;i<=n;i++)cout << " " << r[i] << " " << pos[i] << " " << rr[i] << endl;
for(int i = 2;i<=n;i++){
//如果在前面改则原串有可能发生变化
// [L,R]
// 在 [1,R-L+1] 改一个
// 如果 R-L+1>=R 则后面的串也会被改
// 对 1 特判
// 然后就是在 [1,min(L-1,R-L+1)] 改一个,贡献是 i-1
// 在 [R-L+2,L-1] 改一个,贡献是 R-L+1
// 如果在 R-L+2 改了一个,答案会增加当且仅当 R-L+2 < L
// 如果把 a_{R-L+2} 变成 a_{R+1} 答案增大 rri-ri
// 在 [L,R] 改一个,贡献是 i-L+1
// 在 [R+1,n] 改一个贡献是 R-L+1
// 如果在 R+1 改了一个
// 如果把 a_{R+1} 变成 a_{R-L+2} 答案增大 rri-ri
int L = i,R = r[i];
add(1,min(L-1,R-L+1),1,-1,i);
add(R-L+2,L-1,0,R-L+1,i);
if(R-L+2<=L-1)s[R-L+2].push_back({a[R+1],query(R-L+2,a[R+1],i)-r[i]});
add(L,R,1,-L,i);
add(R+1,n,0,R-L+1,i);
s[R+1].push_back({a[R-L+2],query(R+1,a[R-L+2],i)-r[i]});
}
for(int i = 1;i<=n;i++){
int mx =0;
sort(s[i].begin(),s[i].end());
int lst = 0;
ans[i] = 0;
for(auto x:s[i]){
if(lst!=x.first){
mx = x.second,lst = x.first;
}else mx += x.second;
ans[i] = max(ans[i],mx);
}
k[i]+=k[i-1],c[i]+=c[i-1];
for(auto x:s[i]){
// cout << x.first << " " << x.second << endl;
}
// cout << " " << ans[i] << " " << k[i] << " " << c[i] << endl;
ans[i] += k[i]*i+c[i];
}
int res = 0;
for(int i = 1;i<=n;i++)res+=ans[i]^i;
// for(int i = 1;i<=n;i++)cout << " " << ans[i];cout << endl;
cout << res << endl;
}
signed main(){
srand(time(0));
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
pw[0] = 1;for(int i = 1;i<=200000;i++)pw[i]=pw[i-1]*base;
int t;cin >> t;
while(t--)solve();
return 0;
}/*
1
15
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
2
4
2 1 1 2
1
12
1 1 4 5 1 4 1 9 1 9 8 10
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 24016kb
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: 0
Accepted
time: 18ms
memory: 24520kb
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 114 58 348 225 3 335 364 377 316 3 19 122 66 15 83 36 258 11 63 28 90 85 103 252 191 21 48 303 63 102 20 24 68 316 362 266 309 355 281 326 281 231 312 3 330 54 328 3 69 32 147 322 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:
ok 10000 lines
Test #3:
score: -100
Wrong Answer
time: 38ms
memory: 23644kb
input:
10000 17 1 2 2 2 2 2 2 2 1 1 2 2 1 2 1 2 2 17 2 1 1 1 1 2 2 2 1 1 1 1 1 2 2 2 2 13 2 2 2 1 2 2 2 2 1 1 1 1 1 12 2 2 1 2 1 2 2 1 1 1 1 1 13 2 2 2 1 1 1 1 2 2 2 2 1 1 20 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 1 2 1 1 13 1 2 1 2 2 2 1 2 1 2 1 1 1 20 2 1 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2 12 2 1 2 1 1 2 2 1 2...
output:
392 434 308 252 302 895 343 846 282 249 717 194 252 350 230 427 439 279 340 384 380 292 218 312 271 810 275 211 460 388 365 342 773 203 238 857 720 497 514 443 618 777 372 242 337 232 324 837 289 480 366 681 358 281 320 529 451 309 250 326 315 744 307 841 133 214 411 788 332 365 488 157 760 278 421 ...
result:
wrong answer 8th lines differ - expected: '867', found: '846'