fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 100001
  4. #define mod 1000000009
  5. #define ll long long int
  6.  
  7. struct suffix
  8. {
  9.     ll index;
  10.     ll rank[2];
  11. };
  12.  
  13. ll cmp(struct suffix a, struct suffix b)
  14. {
  15.     return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
  16.            (a.rank[0] < b.rank[0] ?1: 0);
  17. }
  18.  
  19. vector<ll> buildSuffixArray(ll txt[], ll n)
  20. {
  21.     struct suffix suffixes[n];
  22.  
  23.     for (ll i = 0; i < n; i++)
  24.     {
  25.         suffixes[i].index = i;
  26.         suffixes[i].rank[0] = txt[i];
  27.         suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1]): -1;
  28.     }
  29.  
  30.     sort(suffixes, suffixes+n, cmp);
  31.  
  32.     ll ind[n];
  33.  
  34.     for (ll k = 4; k < 2*n; k = k*2)
  35.     {
  36.         ll rank = 0;
  37.         ll prev_rank = suffixes[0].rank[0];
  38.         suffixes[0].rank[0] = rank;
  39.         ind[suffixes[0].index] = 0;
  40.  
  41.         for (ll i = 1; i < n; i++)
  42.         {
  43.             if (suffixes[i].rank[0] == prev_rank &&
  44.                     suffixes[i].rank[1] == suffixes[i-1].rank[1])
  45.             {
  46.                 prev_rank = suffixes[i].rank[0];
  47.                 suffixes[i].rank[0] = rank;
  48.             }
  49.             else
  50.             {
  51.                 prev_rank = suffixes[i].rank[0];
  52.                 suffixes[i].rank[0] = ++rank;
  53.             }
  54.             ind[suffixes[i].index] = i;
  55.         }
  56.  
  57.         for (ll i = 0; i < n; i++)
  58.         {
  59.             ll nextindex = suffixes[i].index + k/2;
  60.             suffixes[i].rank[1] = (nextindex < n)?
  61.                                   suffixes[ind[nextindex]].rank[0]: -1;
  62.         }
  63.  
  64.         sort(suffixes, suffixes+n, cmp);
  65.     }
  66.  
  67.     vector<ll>suffixArr;
  68.     for (ll i = 0; i < n; i++)
  69.         suffixArr.push_back(suffixes[i].index);
  70.  
  71.     return  suffixArr;
  72. }
  73.  
  74. vector<ll> kasai(ll txt[], vector<ll> suffixArr)
  75. {
  76.     ll n = suffixArr.size();
  77.  
  78.     vector<ll> lcp(n, 0);
  79.  
  80.     vector<ll> invSuff(n, 0);
  81.  
  82.     for (ll i=0; i < n; i++)
  83.         invSuff[suffixArr[i]] = i;
  84.  
  85.     ll k = 0;
  86.  
  87.     for (ll i=0; i<n; i++)
  88.     {
  89.  
  90.         if (invSuff[i] == n-1)
  91.         {
  92.             k = 0;
  93.             continue;
  94.         }
  95.  
  96.  
  97.         ll j = suffixArr[invSuff[i]+1];
  98.  
  99.         while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
  100.             k++;
  101.  
  102.         lcp[invSuff[i]] = k;  
  103.  
  104.         if (k>0)
  105.             k--;
  106.     }
  107.  
  108.  
  109.     return lcp;
  110. }
  111.  
  112. int main(){
  113. 	ll t, ans, n, heights[maxn];
  114. 	cin >> t;
  115. 	std::vector<ll> suffarr, lcparr;
  116.  
  117. 	while(t--){
  118. 		cin >> n;
  119. 		for (ll i = 0; i < n; ++i)
  120. 		{
  121. 			cin >> heights[i];
  122. 		}
  123. 		for (ll i = 1; i < n; ++i)
  124. 		{
  125. 			heights[i-1] = heights[i] - heights[i-1];
  126. 		}
  127. 		n--;
  128. 		suffarr = buildSuffixArray(heights, n);
  129. 		lcparr = kasai(heights, suffarr);
  130. 		ans = (n- suffarr[0])%mod;
  131. 		for (ll i = 1; i < n; ++i)
  132. 		{
  133. 			ans = (ans + (n-suffarr[i] - lcparr[i-1])%mod)%mod;
  134. 		}
  135. 		/*for (int i = 0; i < n; ++i)
  136. 		{
  137. 			cout << suffarr[i] << " ";
  138. 		}
  139. 		cout << endl;
  140. 		for (int i = 0; i < n; ++i)
  141. 		{
  142. 			cout << lcparr[i] << " ";
  143. 		}
  144. 		cout << endl;*/
  145. 		cout << ans << endl;
  146. 		suffarr.clear();
  147. 		lcparr.clear();
  148. 	}
  149.  
  150.  
  151.  
  152.  
  153.  
  154. 	return 0;
  155. }
Success #stdin #stdout 0s 4140KB
comments (?)
stdin
copy 
3
6
1 2 3 4 5 6
9
0 2 1 2 1 3 0 1 0
7
0 5 -5 5 -5 4 -4
stdout
copy 
5
31
20
https://ideone.com/7KKzqa
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!