[A](https://codeforces.me/gym/104311/problem/A)↵
↵
<spoiler summary="Editorial">↵
↵
Note $maxp$ as the maximum index of the maximum value in $a$.↵
↵
For $1 \leq k \leq maxp-1$,they do not meet the condition.↵
↵
For $maxp+1 \leq k \leq n$,they all meet the condition.↵
↵
You need to be careful of $k==maxp$,it meet the condition if and only if there is only one maximum value in $a$.↵
↵
</spoiler>↵
↵
[B](https://codeforces.me/gym/104311/problem/B)↵
↵
<spoiler summary="Editorial">↵
↵
Note $a_1$ as the first $\lceil{n/2}\rceil$ numbers of $a$,and $a_2$ as the last $n-\lceil{n/2}\rceil$ numbers of $a$.↵
↵
Through observation,we found that the following processes will be repeated cyclically:↵
↵
- erase the leftmost number of $a_1$↵
↵
- erase the leftmost number of $a_2$↵
↵
- erase the rightmost number of $a_1$↵
↵
- erase the rightmost number of $a_2$↵
↵
In conclusion:↵
↵
- If $|a_1|>|a_2|$(i.e. $n$ is odd),the answer is the number in the middle of $a_1$↵
↵
- If $|a_1|=|a_2|$(i.e. $n$ is even),the answer is the number in the middle of $a_2$↵
↵
</spoiler>↵
↵
[C](https://codeforces.me/gym/104311/problem/C)↵
↵
<spoiler summary="Editorial">↵
↵
We notice we can convert condition $3$ to $c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$.↵
↵
This provides us with convenience: we can independently calculate the left and right value ranges.↵
↵
If two ranges intersect, the answer is $YES$,otherwise the answer is $NO$.↵
↵
Let's calculate the left value ranges.Make all $a_i=0$ to $1$ and $a_i=1$ to $-1$,it is the value range of all subarrays of appropriate length.↵
↵
In fact,we only need to find *max subsegment sum* and *min subsegment sum*.It's a classic problem.↵
↵
You may have already guessed:if $x_1<y_1$,and you get $minsum,maxsum$,the range of values is continuous — $[minsum,maxsum]$.Why?↵
↵
<spoiler summary="Proof">↵
↵
Consider we have get $[L_1,R_1]$ which make $minsum$ and $[L_2,R_2]$ which make $maxsum$.↵
↵
We use continuous transformation to make:$[L_1,R_1]->[L_2,R_2]$.↵
↵
Step1:Length Adjustment↵
↵
For convenience we assume $R_1-L_1+1>R_2-L_2+1$.↵
↵
Transform:$[L_1,R_1]->[L_1+1,R_1]->[L_1+2,R_1]->...->[L_1',R_1]$ $(R_1-L_1'+1=R_2-L_2+1)$↵
↵
Step2:"Creeping"↵
↵
For convenience we assume $R_1<R_2$.↵
↵
Transform:$[L_1',R_1]->[L_1'+1,R_1]->[L_1'+1,R_1+1]->...->[L_2,R_2]$↵
↵
After once length adjustment and several times creeping,we have transformed $[L_1,R_1]$ to $[L_2,R_2]$ continuously and proved the value range is continuous.↵
↵
</spoiler>↵
↵
You also need to be careful of the edge cases that $x_i=y_i(1 \leq i \leq 2)$.↵
↵
</spoiler>↵
↵
[D](https://codeforces.me/gym/104311/problem/D)↵
↵
<spoiler summary="Editorial">↵
↵
We notice we can calculate each bit independently.↵
↵
In other words,note $f(a_i,j)$ as the $j^{th}$ bit under the binary representation of $a_i$,the answer is $\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$.↵
↵
Let's calculate the sum of the $0^{th}$ bit.↵
↵
$a_{i,0}=0,1,0,1,...$ ↵
↵
Note $pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$,then↵
↵
$pre_{i,0}=0,1,1,0,0,1,1,0,...$↵
↵
We noticed that the loop section of this sequence is $4$ and can calculate the total number of $'1'$(note it as $c_1$).The total number of subarrays with xor-value $1$ is $c_1*(n+1-c_1)$.↵
↵
For the $1,2,...30^{th}$ bit,use the similar method to calculate it.↵
↵
</spoiler>↵
↵
[E](https://codeforces.me/gym/104311/problem/E)↵
↵
<spoiler summary="Editorial">↵
↵
Consider an easier problem:for a fixed score $x_1*x_2*...*x_k$($x_i$ is one of the prefix minimum value and note the set of them as $X$),how to calculate the number of schemes?↵
↵
Consider such a sequence construction process: put all $0$'s, all $1$'s, and all $2$'s,...↵
↵
If you want the prefix minimum value of $i$ to appear in $a$, what should you do?We can get:at least one $i$ must be placed at the head of the current sequence.↵
↵
This is actually equivalent to the classical problem: $m_i$ balls are put into $(m_1+...+m_{i-1}+1)$ boxes, the first box must have at least one ball,count the number of schemes.↵
↵
The answer is:↵
↵
$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$.↵
↵
If you want the prefix minimum value of i **not** to appear in $a$, what should you do?We can get:no $i$ must be placed at the head of the sequence.Solve it in a similar way as above.↵
↵
The answer is:↵
↵
$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$.↵
↵
Let's go back to the easier problem.The number of schemes is $\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$.↵
↵
Finally, how to calculate the total score?We can convert the formula into:$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$.↵
↵
<spoiler summary="why?">↵
↵
Consider its extended form. Each item corresponds to a specific set $X$.↵
↵
</spoiler>↵
↵
There's another dp solution:$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$.It's actually do the same thing.↵
↵
</spoiler>↵
↵
[F](https://codeforces.me/gym/104311/problem/F)↵
↵
<spoiler summary="Editorial">↵
↵
coming soon...↵
↵
</spoiler>↵
↵
↵
↵
↵
<spoiler summary="Editorial">↵
↵
Note $maxp$ as the maximum index of the maximum value in $a$.↵
↵
For $1 \leq k \leq maxp-1$,they do not meet the condition.↵
↵
For $maxp+1 \leq k \leq n$,they all meet the condition.↵
↵
You need to be careful of $k==maxp$,it meet the condition if and only if there is only one maximum value in $a$.↵
↵
</spoiler>↵
↵
[B](https://codeforces.me/gym/104311/problem/B)↵
↵
<spoiler summary="Editorial">↵
↵
Note $a_1$ as the first $\lceil{n/2}\rceil$ numbers of $a$,and $a_2$ as the last $n-\lceil{n/2}\rceil$ numbers of $a$.↵
↵
Through observation,we found that the following processes will be repeated cyclically:↵
↵
- erase the leftmost number of $a_1$↵
↵
- erase the leftmost number of $a_2$↵
↵
- erase the rightmost number of $a_1$↵
↵
- erase the rightmost number of $a_2$↵
↵
In conclusion:↵
↵
- If $|a_1|>|a_2|$(i.e. $n$ is odd),the answer is the number in the middle of $a_1$↵
↵
- If $|a_1|=|a_2|$(i.e. $n$ is even),the answer is the number in the middle of $a_2$↵
↵
</spoiler>↵
↵
[C](https://codeforces.me/gym/104311/problem/C)↵
↵
<spoiler summary="Editorial">↵
↵
We notice we can convert condition $3$ to $c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$.↵
↵
This provides us with convenience: we can independently calculate the left and right value ranges.↵
↵
If two ranges intersect, the answer is $YES$,otherwise the answer is $NO$.↵
↵
Let's calculate the left value ranges.Make all $a_i=0$ to $1$ and $a_i=1$ to $-1$,it is the value range of all subarrays of appropriate length.↵
↵
In fact,we only need to find *max subsegment sum* and *min subsegment sum*.It's a classic problem.↵
↵
You may have already guessed:if $x_1<y_1$,and you get $minsum,maxsum$,the range of values is continuous — $[minsum,maxsum]$.Why?↵
↵
<spoiler summary="Proof">↵
↵
Consider we have get $[L_1,R_1]$ which make $minsum$ and $[L_2,R_2]$ which make $maxsum$.↵
↵
We use continuous transformation to make:$[L_1,R_1]->[L_2,R_2]$.↵
↵
Step1:Length Adjustment↵
↵
For convenience we assume $R_1-L_1+1>R_2-L_2+1$.↵
↵
Transform:$[L_1,R_1]->[L_1+1,R_1]->[L_1+2,R_1]->...->[L_1',R_1]$ $(R_1-L_1'+1=R_2-L_2+1)$↵
↵
Step2:"Creeping"↵
↵
For convenience we assume $R_1<R_2$.↵
↵
Transform:$[L_1',R_1]->[L_1'+1,R_1]->[L_1'+1,R_1+1]->...->[L_2,R_2]$↵
↵
After once length adjustment and several times creeping,we have transformed $[L_1,R_1]$ to $[L_2,R_2]$ continuously and proved the value range is continuous.↵
↵
</spoiler>↵
↵
You also need to be careful of the edge cases that $x_i=y_i(1 \leq i \leq 2)$.↵
↵
</spoiler>↵
↵
[D](https://codeforces.me/gym/104311/problem/D)↵
↵
<spoiler summary="Editorial">↵
↵
We notice we can calculate each bit independently.↵
↵
In other words,note $f(a_i,j)$ as the $j^{th}$ bit under the binary representation of $a_i$,the answer is $\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$.↵
↵
Let's calculate the sum of the $0^{th}$ bit.↵
↵
$a_{i,0}=0,1,0,1,...$ ↵
↵
Note $pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$,then↵
↵
$pre_{i,0}=0,1,1,0,0,1,1,0,...$↵
↵
We noticed that the loop section of this sequence is $4$ and can calculate the total number of $'1'$(note it as $c_1$).The total number of subarrays with xor-value $1$ is $c_1*(n+1-c_1)$.↵
↵
For the $1,2,...30^{th}$ bit,use the similar method to calculate it.↵
↵
</spoiler>↵
↵
[E](https://codeforces.me/gym/104311/problem/E)↵
↵
<spoiler summary="Editorial">↵
↵
Consider an easier problem:for a fixed score $x_1*x_2*...*x_k$($x_i$ is one of the prefix minimum value and note the set of them as $X$),how to calculate the number of schemes?↵
↵
Consider such a sequence construction process: put all $0$'s, all $1$'s, and all $2$'s,...↵
↵
If you want the prefix minimum value of $i$ to appear in $a$, what should you do?We can get:at least one $i$ must be placed at the head of the current sequence.↵
↵
This is actually equivalent to the classical problem: $m_i$ balls are put into $(m_1+...+m_{i-1}+1)$ boxes, the first box must have at least one ball,count the number of schemes.↵
↵
The answer is:↵
↵
$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$.↵
↵
If you want the prefix minimum value of i **not** to appear in $a$, what should you do?We can get:no $i$ must be placed at the head of the sequence.Solve it in a similar way as above.↵
↵
The answer is:↵
↵
$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$.↵
↵
Let's go back to the easier problem.The number of schemes is $\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$.↵
↵
Finally, how to calculate the total score?We can convert the formula into:$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$.↵
↵
<spoiler summary="why?">↵
↵
Consider its extended form. Each item corresponds to a specific set $X$.↵
↵
</spoiler>↵
↵
There's another dp solution:$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$.It's actually do the same thing.↵
↵
</spoiler>↵
↵
[F](https://codeforces.me/gym/104311/problem/F)↵
↵
<spoiler summary="Editorial">↵
↵
coming soon...↵
↵
</spoiler>↵
↵
↵
↵
