T1：
不难发现间隔为$n$的倍数的两列，放的棋子数必须相同。
可以用背包DP解决，设$dp[i][j]$为考虑到第$i$列，放了$j$个棋子的方案数。
DP范围不能超过$n$，但可以用上面的性质。
每一列的摆放都是独立的，所以可以用快速幂求出。
状态转移方程：
$dp[i][j]=sum limits_{k=0}^{min(j,n)} dp[i-1][j-k]*s[i][k]$
$s[i][j]=(C_n^j)^{large frac{n-1}{i}+1}$
时间复杂度$O(n^4)$。
T2：
对于所有点，合法左端点的位置一定在最左侧的大于它的数右面。
维护一个单调递减的单调栈，每个点对应的左端点可以由弹掉的元素转移而来。
但前提是弹掉元素对应的左端点的值小于当前左端点的值，不然不合法。
时间复杂度$O(n)$。
T3：
没有办法直接维护，只能莫队。
普通莫队需要用线段树维护最长值域连续段，会超时。
所以这题要用到回滚莫队。
对于在每个块中的询问，右端点严格单调，所以不需要回滚。
而左端点要回溯，需用栈记录状态。
更新答案可以用类似链表的思路，只记录连通区间两侧的答案即可。
时间复杂度$O(nsqrt{n})$。