HackerRank/randomness_partial.cpp at master · Study404/HackerRank · GitHub

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
//randomness_partial.cpp
//Randomness
//Daily Challenges - Week 1
//Author: derekhh

/*
	Complexity: O(QN\logN), pass the first 8 test cases.
*/

#include<cstdio>
#include<iostream>
#include<algorithm>
usingnamespacestd;

#definenb nexta
#definehead height
#definerank b

constint maxn = 75000;
char s[maxn];
int n, id[maxn], height[maxn], b[maxn], nexta[maxn];

boolcmp(constint& i, constint& j)
{
return s[i] < s[j];
}

voidSuffixSort()
{
int i, j, k, h;
for (i = 0; i < n; i++) id[i] = i;
sort(id, id + n, cmp);
for (i = 0; i < n; i++)
	{
if (i == 0 || s[id[i]] != s[id[i - 1]])
 b[id[i]] = i;
else b[id[i]] = b[id[i - 1]];
	}
for (h = 1; h < n; h <<= 1)
	{
for (i = 0; i < n; i++)
 head[i] = nexta[i] = -1;
for (i = n - 1; i >= 0; i--)
 {
if (id[i])
 {
 j = id[i] - h;
if (j < 0) j += n;
 nexta[j] = head[b[j]];
 head[b[j]] = j;
 }
 }
 j = n - h;
 nexta[j] = head[b[j]];
 head[b[j]] = j;
for (i = k = 0; i < n; i++)
if (head[i] >= 0)
for (j = head[i]; j >= 0; j = nexta[j])
 id[k++] = j;
for (i = 0; i < n; i++)
if (i>0 && id[i] + h < n&&id[i - 1] + h < n&&b[id[i]] == b[id[i - 1]] && b[id[i] + h] == b[id[i - 1] + h])
 nb[id[i]] = nb[id[i - 1]];
else
 nb[id[i]] = i;
for (i = 0; i < n; i++)
 b[i] = nb[i];
	}
}

voidGetHeight()
{
int i, j, h; height[0] = 0;
for (i = 0; i < n; i++)
 rank[id[i]] = i;
for (h = 0, i = 0; i < n;i++)
if (rank[i]>0)
 {
 j = id[rank[i] - 1];
while (s[i + h] == s[j + h])++h;
 height[rank[i]] = h;
if (h>0) --h;
 }
}

intmain()
{
int q;
scanf("%d%d", &n, &q);
getchar();
scanf("%s", s);
longlong tot = (n + 1) * (longlong)n / 2;
while (q--)
	{
int p;
char ch;
getchar();
scanf("%d %c", &p, &ch);
 s[p - 1] = ch;
SuffixSort();
GetHeight();
longlong sum = 0;
for (int i = 0; i < n; i++)
 sum += height[i];
 cout << tot - sum << endl;
	}
return0;
}