题目链接 离别 离线算法+线段树 容易发现当我们枚举右端点r时，符合条件的左端点是一段连续的区间 我们可以用队列来维护这个连续区间的左右端点 当枚举到端点\(i\)时，将下标\(i\)插入到队列\(q[a_i]\)中 如果元素大于k，队首+1即为左端点（注意要与之前的取max) 如果元素等于k，队首即为右端点 这样对每个右端点，就找到了符合条件的左端点 然后将询问离线，以右端点排序 对于每个右端点，将符合条件的左端点插入线段树中，同时查询答案 时间复杂度\(O（nlogn)\) （注意要开long long，还有update 与 query 都要push_down) ...

题目链接： 数列 查询有多少\([l,r]\)区间满足每个数出现\(k\)的倍数次 即为\(1\)到\(r\)与\(1\)到\(l-1\)每个数相减的次数为\(k\)的倍数次 可以使用哈希维护 记录每个数出现的次数为\(cnt[x]\)，哈希值为\(hash[x]\) 那么前缀哈希和即为\(\sum_{x} cnt[x]*hash[x]\)(\(cnt\)注意要模\(k\)) 当我们循环到i时候，更新哈希值，查询得到的哈希值在之前map[hash]出现的次数 （\([l,r]\)区间的哈希值为0） 就可以得到以\(i\)结尾的符合条件区间的个数，从而得到答案 #includ...

题目链接： 排列 考虑\(dp\)，我们思考如何设计状态 将第i个数插入i-1个数中，我们考虑会新增多少个超级逆序对 假设将\(i\)插入后\(i\)的位置为\(l\)，\(i-1\)的原来的位置为\(l2\) 如果\(l2>=l\) 我们会新产生\(i-l-1\)个逆序对 否则\(l2<l\) 我们会新产生\(i-l\)个逆序对 设j为逆序对的个数，我们可以得到如下的状态转移方程 \(dp[i][j][l]+=dp[i-1][j-i+l+1][l2]\)如果\(l2>=l\) 否则\(dp[i][j][l]+=dp[i-1][j-i+l][l2]\)如果\...

题目链接： 最小的指数 乍一看还以为是Pollard_rho算法，其实大可不必。 发现\(1<= n <= 1e18\),我们可以将n分为两部分（分块思想降低时间复杂度）。 剔除小于等于\(4000\)的所有质因子，剩余的设为x，设此时得到的答案为\(minnum\) 如果x为\(1\)，那我们得到答案，可以直接返回 否则知道x的质因子一定大于\(4000\)，可以分类讨论 若x可写成\(x=p^{(1/4)}\),\(minnum = min(minnum,4)\),返回 若x可写成\(x=p^{(1/3)}\),\(minnum = min(minnum,3)\...