【后缀数组 线段树】2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest H. Can You Solve the Harder Problem
2021-10-06 20:40:00 # ACM

题链

题目解析

求所有本质不同的子区间的 f 值的总和，f 值为该区间的最大值；
本质不同指的是子区间长度不同，当长度相同时则存在一个位置他们的权值不同；

  后缀数组可以得到所有本质不同的子区间，可以通过单调栈求比当前值大的下一个值的位置 nxt[i] 以及从后往前递推求得以 i 为左区间 j∈[i+1,n] 为右区间的最大值的总和 val[i]；

对于 sa[i] 和 sa[i−1] 相比，重复的部分就是 height[i]；

  考虑一个子问题：求以 i 为左区间，j∈[t,n] 为右区间的区间最大值总和；
解法可以线段树维护求得 [i,t−1] 的最大值 mxw 和最大值的位置 pos，下一个比 mxw 大的值的位置为 nxt[pos]，这样就可以将 [t,n] 分为两段，那么 [t,nxt[pos]−1] 的区间最大值都是 mxw，[nxt[pos],n] 的贡献就是 val[nxt[pos]]，和起来就是这个子问题的答案；

那么对于每一个后缀 sa[i] 都是解决这个子问题；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ULL unsigned long long
	#define Pair pair<LL ,LL >
	#define ls rt<<1
	#define rs rt<<1|1
	#define PI acos(-1.0)
	#define eps 1e-8
	#define MAXN 9e18
	#define ll long long
	#define MS 2000009
	#define mod 1000000007
const int N=1000009;

int n,m,k;
int a[N],nxt[N];
LL val[N];
stack<int > sta;
struct node{
	int mxw;
	int pos;
}p[N];
int wa[N],wb[N],wv[N],wss[N],rak[N],height[N],cal[N],sa[N];
int cmp(int *r,int a,int b,int l){
	return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int M) {
     int i,j,p,*x=wa,*y=wb,*t;
     for(i=0;i<M;i++) wss[i]=0;
     for(i=0;i<n;i++) wss[x[i]=r[i]]++;
     for(i=1;i<M;i++) wss[i]+=wss[i-1];
     for(i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
     for(j=1,p=1;p<n;j*=2,M=p) {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<M;i++) wss[i]=0;
        for(i=0;i<n;i++) wss[wv[i]]++;
        for(i=1;i<M;i++) wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
     }
     return;
}
void calheight(int *r,int *sa,int n) {
     int i,j,k=0;
     for(i=1;i<=n;i++) rak[sa[i]]=i;
     for(i=0;i<n;height[rak[i++]]=k)
     for(k?k--:0,j=sa[rak[i]-1];r[i+k]==r[j+k];k++);
     for(int i=n;i;i--)rak[i]=rak[i-1],sa[i]++;
}
void calnxt(){
	while(!sta.empty()) sta.pop();
	a[n+1] = 2e9;
	for(int i=1;i<=n+1;i++){
		if(sta.empty()) sta.push(i);
		else{
			while(!sta.empty() && a[sta.top()] < a[i]){
				int t = sta.top(); sta.pop();
				nxt[t] = i;
			}
			sta.push(i);
		}
	}
}
void calval(){
	val[n+1] = 0;
	for(int i=n;i>=1;i--){
		val[i] = 1LL*a[i]*(nxt[i]-i) + val[nxt[i]];
	}
}
node push_up(node t1, node t2){
	if(t1.mxw >= t2.mxw) return t1;
	else return t2;
}
void build(int l,int r,int rt){
	if(l == r){
		p[rt] = {a[l],l};
		return;
	}
	int m = l+r>>1;
	build(l,m,ls); build(m+1,r,rs);
	p[rt] = push_up(p[ls],p[rs]);
}
node calpos(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R) return p[rt];
	int m = l+r>>1;
	node ans = {0,0};
	if(m >= L) ans = push_up(ans,calpos(L,R,l,m,ls));
	if(m <  R) ans = push_up(ans,calpos(L,R,m+1,r,rs));
	return ans;
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cal[i] = a[i]; cal[n+1] = 0;
	da(cal+1,sa,n+1,1000009);
	calheight(cal+1,sa,n);
	calnxt();
	calval();
	build(1,n,1);
	LL ans = 0;
	for(int i=1;i<=n;i++){
		if(height[i] == 0) ans += val[sa[i]];
		else{
			int l = sa[i]+height[i];
			node t = calpos(sa[i],l-1,1,n,1);
			int pos = nxt[t.pos];
			ans += 1LL*t.mxw*(pos-l) + val[pos];
		}
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	int ce = 1;
	cin >> ce;
	while(ce--) {
		solve();
	}

	return 0;
}
Prev
2021-10-06 20:40:00 # ACM
Next