CCPC-Wannafly Winter Camp Day5

From Ingenuity Wiki

Problem C

upsolved by ybmj.

Problem D

unsolved. (-3)

直接暴搜即可,可能需要一些牛逼的剪枝技巧,没有卡过去。

Problem E

upsolved by CSL.

考虑分开计算每个数的贡献。

  • 当某个数出现次数少的时候,直接把下标拿出来暴力。
  • 当某个数出现次数多的时候,构造两个向量进行NTT。

需要调一下参数,大概 $10000$ 左右差不多可以过。

Problem I

upsolved by CSL.

观察到操作2和3不会影响 大于 $x$ 的数和小于等于 $x$ 的数的相对位置,可以分开维护。

设一个 01 序列,表示这个数的大小。

每次查询只需要知道查询的数是哪几个 $0$ 和 $1$,通过前缀和来求解。更新操作就是查一下区间里 $0$ 和 $1$ 的个数,然后在线段树上打一下标记就好了。

Problem J

unsolved. (-3)

自闭了。