[submission:2812937730848]↵
↵
Firstly, we should divide the resulting string into pieces of length $a+b$. Then let's define four numbers: pl, pr, cl, cr.↵
↵
$pl=(l-1)\ mod\ (a+b)$. It refers to the position of l in its piece.↵
↵
$pr=(r-1)\ mod\ (a+b)$. It refers to the position of r in its piece.↵
↵
$cl=\lfloor(l-1)/(a+b)\rfloor$. It refers to the number of the piece which l is in.↵
↵
$cr=\lfloor(r-1)/(a+b)\rfloor$. It refers to the number of the piece which r is in.↵
↵
1. $b \geq a$↵
------------------↵
### Case 1: $cr-cl>1$↵
The range covers an entire piece, so there are at least $a$ distinctive characters in that piece. According to the problem description, these $a$ characters must be different from previous characters, so the answer is $a+1$. The answer can be achieved by repeating the last character of $a$.↵
↵
### Case 2: $cr-cl=1$↵
l and r are in the adjacent piece, so there are at least $min(pr+1,a)$ distinctivenumbcharacters in the right piece. We can calculate how many distinctive characters are in the left piece: $max(1,a-pl)$. It is at least 1 because characters in the right piece must be different from the last characters in the left. If $[l,r]$ expands to the first $a$ character of the left part, we shouldn't use characters other than them in our $B$ part, because it cannot make the answer better. I mean, if we want some existed characters to appear in the right piece instead of new ones, (e.g. a=2, b=3, bc???bc) we have to write new ones down so the computer won't choose them. Obviously, writing down new ones actually doesn't change the answer. Because of this conclusion, in the following cases we think about the computer's choice first as we cannot "urge" it to write down a certain character to make answer better.↵
So the answer is $min(a,min(pr+1,a)+max(1,a-pl))$. Attention: when $pr+1 \geq a$, answer should be $a+1$, like the previous case that $cr-cl>1$.↵
↵
### Case 3: $cr=cl$↵
The answer is $min(pr-pl+1,max(1,a-pl))$ when we repeat the last character. It cannot be smaller.↵
↵
2. $b<a$↵
------------------↵
Let $m=a-b$, and $M$ denotes the last $m$ characters in part $A$.↵
### Case 1: $cr-cl>2$↵
The range covers two entire pieces. We only consider $a$ characters the computer adds. Because the first $a$ characters in the next piece cannot be the same as the last $m$ characters in part $A$ of current piece, the answer is at least $a+m$. The length of cycle is 2 pieces. To achieve the answer, we simply repeat the last character of $A$. The answer is $a+m$.↵
↵
### Case 2: $cr-cl=2$↵
The range covers one entire piece, so the answer is at least $a$. Also, we only consider part $A$. The first $a-m$ characters are always the same in every part $A$. As for the rightmost part $M$, there are $max(pr+1-a+m,0)$ characters. As for the leftmost, there are $max(0,a-pl)$. And if their sum is larger than $m$, they must intersect each other, and there are at most $m$ distinctive characters. So the answer is $a+max(1,min(m,max(pr+1-a+m,0)+max(0,a-pl)))$. If no other part $M$ is included in range $[l,r]$, the answer should be $a+1$ as proved in 1.1. Attention: if $pl\geq a$ and $pr\geq a-m$, which means the leftmost $M$ part is not included, but the rightmost one is, we should repeat the last character of the rightmost $M$ in part $cl$. Otherwise, we simply repeat the last character of $A$. Under these circumstances, the expression is the same: $a+max(1,min(m,max(pr+1-a+m,0)+max(0,a-pl)))$.↵
↵
### Case 3: $cr-cl=1$↵
On the right piece, there are $min(a,pr+1)$ differentFirst we should calculate the number of same characters in every part $A$-$M$, it is $min(a-m,min(pr+1,a-m)+max(0,a-m-pl))$ (there are at most $a-m$ characters). We only have to consider the $M$ part of the left piece as oThen we consider every part $M$. On the leftmost $M$, therse are the same. The number of distinctive$max(1,min(m,a-pl))$ (at least 1 because we have to fill at least one kind of characters o). On the left piece isrightmost $M$, there are $max(10,min(m,a-pl))$, so thepr+1-a+m))$. So the total answer is $max(1,min(m,a-pl))+min(a,pr+1-m,min(pr+1,a-m)+max(0,a-m-pl))+max(0,min(m,pr+1-a+m))$.↵
↵
### Case 4: $cl=cr$↵
The same as 1.3.↵
↵
EDIT: Thanks to [user:Tima,2017-06-29], Case 2.3 is fixed. Previous version is wrong.
↵
Firstly, we should divide the resulting string into pieces of length $a+b$. Then let's define four numbers: pl, pr, cl, cr.↵
↵
$pl=(l-1)\ mod\ (a+b)$. It refers to the position of l in its piece.↵
↵
$pr=(r-1)\ mod\ (a+b)$. It refers to the position of r in its piece.↵
↵
$cl=\lfloor(l-1)/(a+b)\rfloor$. It refers to the number of the piece which l is in.↵
↵
$cr=\lfloor(r-1)/(a+b)\rfloor$. It refers to the number of the piece which r is in.↵
↵
1. $b \geq a$↵
------------------↵
### Case 1: $cr-cl>1$↵
The range covers an entire piece, so there are at least $a$ distinctive characters in that piece. According to the problem description, these $a$ characters must be different from previous characters, so the answer is $a+1$. The answer can be achieved by repeating the last character of $a$.↵
↵
### Case 2: $cr-cl=1$↵
l and r are in the adjacent piece, so there are at least $min(pr+1,a)$ distinctive
So the answer is $min(a,min(pr+1,a)+max(1,a-pl))$. Attention: when $pr+1 \geq a$, answer should be $a+1$, like the previous case that $cr-cl>1$.↵
↵
### Case 3: $cr=cl$↵
The answer is $min(pr-pl+1,max(1,a-pl))$ when we repeat the last character. It cannot be smaller.↵
↵
2. $b<a$↵
------------------↵
Let $m=a-b$, and $M$ denotes the last $m$ characters in part $A$.↵
### Case 1: $cr-cl>2$↵
The range covers two entire pieces. We only consider $a$ characters the computer adds. Because the first $a$ characters in the next piece cannot be the same as the last $m$ characters in part $A$ of current piece, the answer is at least $a+m$. The length of cycle is 2 pieces. To achieve the answer, we simply repeat the last character of $A$. The answer is $a+m$.↵
↵
### Case 2: $cr-cl=2$↵
The range covers one entire piece, so the answer is at least $a$. Also, we only consider part $A$. The first $a-m$ characters are always the same in every part $A$. As for the rightmost part $M$, there are $max(pr+1-a+m,0)$ characters. As for the leftmost, there are $max(0,a-pl)$. And if their sum is larger than $m$, they must intersect each other, and there are at most $m$ distinctive characters. So the answer is $a+max(1,min(m,max(pr+1-a+m,0)+max(0,a-pl)))$. If no other part $M$ is included in range $[l,r]$, the answer should be $a+1$ as proved in 1.1. Attention: if $pl\geq a$ and $pr\geq a-m$, which means the leftmost $M$ part is not included, but the rightmost one is, we should repeat the last character of the rightmost $M$ in part $cl$. Otherwise, we simply repeat the last character of $A$. Under these circumstances, the expression is the same: $a+max(1,min(m,max(pr+1-a+m,0)+max(0,a-pl)))$.↵
↵
### Case 3: $cr-cl=1$↵
↵
### Case 4: $cl=cr$↵
The same as 1.3.↵
↵
EDIT: Thanks to [user:Tima,2017-06-29], Case 2.3 is fixed. Previous version is wrong.
