fork(1) download
copy 
  1.     #include <bits/stdc++.h>
  2.     using namespace std;
  3.  
  4.     #define F first
  5.     #define S second
  6.  
  7.     const int N = 1e6+10;
  8.     const int logN = 20;
  9.     int str[N], floorlog[N]; 
  10.     int _rank[N], pos[N];
  11.     int cnt[N], _next[N];
  12.     bool bh[N], b2h[N];
  13.  
  14.     bool smaller_first_char(int a, int b){
  15.         return str[a] < str[b];
  16.     }
  17.  
  18.     void suffixSort(int n){
  19.         for (int i=0; i<n; ++i){
  20.             pos[i] = i;
  21.         }
  22.         sort(pos, pos + n, smaller_first_char);
  23.  
  24.         for (int i=0; i<n; ++i){
  25.             bh[i] = i == 0 || str[pos[i]] != str[pos[i-1]];
  26.             b2h[i] = false;
  27.         }
  28.  
  29.         for (int h = 1; h < n; h <<= 1){
  30.             int buckets = 0;
  31.             for (int i=0, j; i < n; i = j){
  32.                 j = i + 1;
  33.                 while (j < n && !bh[j]) j++;
  34.                 _next[i] = j;
  35.                 buckets++;
  36.             }
  37.             if (buckets == n) break; // We are done! Lucky bastards!
  38.  
  39.             for (int i = 0; i < n; i = _next[i]){
  40.                 cnt[i] = 0;
  41.                 for (int j = i; j < _next[i]; ++j){
  42.                     _rank[pos[j]] = i;
  43.                 }
  44.             }
  45.  
  46.             cnt[_rank[n - h]]++;
  47.             b2h[_rank[n - h]] = true;
  48.             for (int i = 0; i < n; i = _next[i]){
  49.                 for (int j = i; j < _next[i]; ++j){
  50.                     int s = pos[j] - h;
  51.                     if (s >= 0){
  52.                         int head = _rank[s];
  53.                         _rank[s] = head + cnt[head]++;
  54.                         b2h[_rank[s]] = true;
  55.                     }
  56.                 }
  57.                 for (int j = i; j < _next[i]; ++j){
  58.                     int s = pos[j] - h;
  59.                     if (s >= 0 && b2h[_rank[s]]){
  60.                         for (int k = _rank[s]+1; !bh[k] && b2h[k]; k++) b2h[k] = false;
  61.                     }
  62.                 }
  63.             }
  64.             for (int i=0; i<n; ++i){
  65.                 pos[_rank[i]] = i;
  66.                 bh[i] |= b2h[i];
  67.             }
  68.         }
  69.         for (int i=0; i<n; ++i){
  70.             _rank[pos[i]] = i;
  71.         }
  72.     }
  73.  
  74.  
  75.     int height[N];
  76.     // height[i] = length of the longest common prefix of suffix pos[i] and suffix pos[i+1]
  77.     void getHeight(int n){
  78.       for (int i=0; i<n; ++i) _rank[pos[i]] = i;
  79.       height[0] = 0;
  80.       for (int i=0, h=0; i<n; ++i){
  81.         if (_rank[i] > 0){
  82.           int j = pos[_rank[i]-1];
  83.           while (i + h < n && j + h < n && str[i+h] == str[j+h]) h++;
  84.           height[_rank[i]] = h;
  85.           if (h > 0) h--;
  86.         }
  87.       }
  88.       for(int i = 0;i<n-1;i++)
  89.         height[i] = height[i+1]; 
  90.         height[n-1] = 0;
  91.     }
  92.  
  93.     int n, m;
  94.     int getInd(int i, int j){
  95.     	return i * m + j;	
  96.     }
  97.     int col = 0;
  98.  
  99.     bool cmp(int i,int j){
  100.     	return _rank[getInd(i, col)] < _rank[getInd(j, col)];
  101.     }
  102.  
  103.     vector<int> vec;
  104.  
  105.     long long ans = 0;
  106.  
  107.     int arr[logN][N];
  108.     struct sparse_table{
  109.     	int n;
  110.     	sparse_table(int _n){
  111.     		n = _n;
  112.     	}
  113.  
  114.     	void storefloorlog(){
  115.     		for(int i = 0; (1 << i) < N; i++){
  116.     			for(int j = (1 << i); j < (1 << (i + 1)) && j < N; j++)
  117.     				floorlog[j] = i;
  118.     		}
  119.     	}
  120.  
  121.     	int func(int x, int y){
  122.     		return min(x, y);
  123.     	}
  124.  
  125.     	void make(int A[], int n){
  126.     		for(int i = n - 1; i >= 0; i--){
  127.     			arr[0][i] = A[i];
  128.     			for(int j = 1; i + (1 << j) - 1 <= n; j++){
  129.     				arr[j][i] = func(arr[j - 1][i], arr[j - 1][i + (1 << (j - 1))]);
  130.     			}
  131.     		}
  132.     	}
  133.  
  134.     	int get(int i, int j){
  135.     		int k = floorlog[j - i + 1];
  136.     		return func(arr[k][i], arr[k][j - (1 << k) + 1]);
  137.     	}
  138.  
  139.     	inline int lcp(int i, int j){
  140.     		if(i == j) return n * m - i;
  141.     		i = _rank[i]; j = _rank[j];
  142.     		if(i > j) swap(i, j);
  143.     		return get(i, j - 1);
  144.     	}
  145.     };
  146.  
  147.     map<int, vector<int>> mp;
  148.  
  149.     long long bad[N];
  150.     long long currans;
  151.     int par[N];
  152.     long long f(int i){
  153.     	return (i * 1ll * (i + 1)) >> 1;
  154.     }
  155.     set<int> positions[N];
  156.  
  157.     void init(){
  158.     	currans = 0;
  159.     	for(int j = 0; j < n; j++){
  160.     		bad[j] = f(j) + f(n - j - 1);
  161.     		currans += (j + 1) * 1ll * (n - j);
  162.     		positions[j].clear();
  163.     		positions[j].insert(j);
  164.     		par[j] = j;
  165.     	}
  166.     }
  167.  
  168.     int root(int i){
  169.     	return par[i] == i ? i : (par[i] =root(par[i]));
  170.     }
  171.  
  172.     void _insert(int i, int v){
  173.     	auto it = positions[i].upper_bound(v);
  174.     	int hi = (it == positions[i].end() ? n : *it);
  175.     	int lo = (it == positions[i].begin() ? -1 : *(--it));
  176.     	bad[i] -= f(hi - lo - 1);
  177.     	bad[i] += f(hi - v - 1) + f(v - lo - 1);
  178.     	positions[i].insert(v);
  179.     }
  180.  
  181.     void merge(int i, int j){
  182.     	i = root(i); j = root(j);
  183.     	if(i == j) return;
  184.     	if(positions[i].size() < positions[j].size()) swap(i, j);
  185.     	par[j] = i;
  186.     	currans += bad[i];
  187.     	currans -= (f(n) - bad[j]);
  188.     	for(auto it : positions[j]) _insert(i, it);
  189.     	positions[j].clear();
  190.     	currans -= bad[i];
  191.     }
  192.  
  193.     // O(n * m * log^2(n))
  194.     int s[N];
  195.  
  196.     int main(){
  197.     	scanf("%d %d", &n, &m);
  198.     	int ind = 0;
  199.     	for(int i = 0; i < n; i++){
  200.     		vec.push_back(i);
  201.     		for(int j = 0; j < m; j++){
  202.     			scanf("%d", s + j);
  203.     			str[ind++] = s[j];
  204.     		}
  205.     	}
  206.  
  207.     	suffixSort(n * m);
  208.     	getHeight(n * m);
  209.     	sparse_table st = sparse_table(n * m);
  210.     	st.storefloorlog();
  211.     	st.make(height, n * m);
  212.     	for(col = 0; col < m; col++){
  213.     		sort(vec.begin(), vec.end(), cmp);
  214.     		mp.clear();
  215.     		for(int i = 0; i < vec.size() - 1; i++){
  216.     			int L = st.lcp(getInd(vec[i], col), getInd(vec[i + 1], col));
  217.     			mp[-min(m - 1, (col + L - 1))].push_back(i);
  218.  
  219.     		}	
  220.     		init();
  221.     		int curr = m - 1;
  222.     		for(auto it : mp){
  223.     			int newpos = -it.F;
  224.     			ans += (curr - newpos) * 1ll * currans;
  225.     			for(auto it2 : it.S) merge(vec[it2], vec[it2 + 1]);
  226.     			curr = newpos;
  227.     		}
  228.     		ans += (curr - col + 1) * 1ll * currans;
  229.     	}
  230.     	printf("%lld\n", ans);
  231.     }
Success #stdin #stdout 0.02s 185152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HZQOgU
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!