解题思路

不难想到用 $dp[i][j]$ 表示放第 $i$ 个题时趣味值为 $j$ 的方案数，然而有一个问题是不好表示前面 $i-1$ 个都选了哪些。因此这里需要用状态压缩 DP（一看题目数量那么小就应该试图往状压那边想了），把我们的 dp 数组中的第一维表示为一种题目选择方案（按二进制压缩成一个数存储），然后就很容易写出转移方程（其中 $i$ 表示当前遍历到的状态，$j$ 和 $k$ 分别为 $[1, n]$ 及 $[0, m]$ 的循环，$cnt$ 为当前状态下的已选题目数量）：

$$dp[i+2^{j-1}][min(k+a[cnt+1][j], m)] += dp[i][k]$$

解题思路

使用费用流求解。首先把题中所有的边都按流量为 1，费用为路径长度加边，这样就保证了每条路只能走一次，且求出来的最小费用就是最短路径长度。之后再把源点到 1 以及 n 到汇点都加一条流量为 2，费用为 0 的边，这是为了支持题目中的往返操作。这样跑一边最小费用最大流即可求出答案。

解题思路

由区间翻转问题接触到 Splay，学会之后这道题就是 Splay 的基本操作了。

题面

题意

给定一个方程，求出 x 的最小正整数解，如果不存在，则输出 -1 。

题面

Garden
Time Limit: 1000MS Memory Limit: 65536K

Description
There are n flowerpots in Daniel's garden. These flowerpots are placed in n positions, and these n positions are numbered from 1 to n. Each flower is assigned an aesthetic value. The aesthetic values vary during different time of a day and different seasons of a year. Naughty Daniel is a happy and hardworking gardener who takes pleasure in exchanging the position of the flowerpots.
Friends of Daniel are great fans of his miniature gardens. Before they visit Daniel's home, they will take their old-fashioned cameras which are unable to adjust the focus so that it can give a shot of exactly k consecutive flowerpots. Daniel hopes his friends enjoy themselves, but he doesn't want his friend to see all of his flowers due to some secret reasons, so he guides his friends to the best place to catch the most beautiful view in the interval [x, y], that is to say, to maximize the sum of the aesthetics values of the k flowerpots taken in one camera shot when they are only allow to see the flowerpots between position x to position y.
There are m operations or queries are given in form of (p, x, y), here p = 0, 1 or 2. The meanings of different value of p are shown below.

1. p=0 settheaestheticvalueofthepotinpositionxasy.(1<=x<=n;-100<= y <= 100)
2. p = 1 exchange the pot in position x and the pot in position y. (1 <= x, y <= n; x might equal to y)
3. p = 2 print the maximum sum of aesthetics values of one camera shot in interval [x, y]. (1 <= x <= y <= n; We guarantee that y-x+1>=k)

Input
There are multiple test cases.
The first line of the input file contains only one integer indicates the number of test cases.
For each test case, the first line contains three integers: n, m, k (1 <= k <= n <= 200,000; 0 <= m <= 200,000).
The second line contains n integers indicates the initial aesthetic values of flowers from position 1 to position n. Some flowers are sick, so their aesthetic values are negative integers. The aesthetic values range from -100 to 100. (Notice: The number of position is assigned 1 to n from left to right.)
In the next m lines, each line contains a triple (p, x, y). The meaning of triples is mentioned above.

Output
For each query with p = 2, print the maximum sum of the aesthetics values in oneshot in interval [x, y].

Sample Input
1
5 7 3
-1 2 -4 6 1
2 1 5
2 1 3
1 2 1
2 1 5
2 1 4
0 2 4
2 1 5

Sample Output
4
-3
3
1
6