CF1743F Intersection and Union

You are given $ n $ segments on the coordinate axis. The $ i $ -th segment is $ [l_i, r_i] $ . Let's denote the set of all integer points belonging to the $ i $ -th segment as $ S_i $ . Let $ A \cup B $ be the union of two sets $ A $ and $ B $ , $ A \cap B $ be the intersection of two sets $ A $ and $ B $ , and $ A \oplus B $ be the symmetric difference of $ A $ and $ B $ (a set which contains all elements of $ A $ and all elements of $ B $ , except for the ones that belong to both sets). Let $ [\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}] $ be an array where each element is either $ \cup $ , $ \oplus $ , or $ \cap $ . Over all $ 3^{n-1} $ ways to choose this array, calculate the sum of the following values: $ $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n| $ $

In this expression, $ |S| $ denotes the size of the set $ S$$$.

N/A

N/A