给定一个 $n$ 的排列 $a$，$q$ 次询问，每次查询 $a_{[l_i,r_i]}$ 的 LIS 长度。

$1\le n\le 10^5$，$1\le q\le 10^6$。

对于两个字符串 $A,B$，若能将 $A$ 的一个后缀整体移动到 $A$ 的前面则称它们是循环同构的。

给定一个长 $n$ 的字符串，求最大的 $L$ 使得 $S_{[1,L]}$ 和 $S_{[n-L+1,n]}$ 是循环同构的。

$1\le n\le 10^6$。

给定三个长 $n$ 的序列 $A,B,C$，找到一个符合以下条件且大小最大的集合 $S$：

• 其能被这样生成：对于每个 $i\in [1, n]$，向 $S$ 中加入 $A_i$ 或者 $B_i$；
• 其能被这样生成：对于每个 $i\in [1, n]$，向 $S$ 中加入 $A_i$ 或者 $C_i$；

需要输出方案。

$1\le n\le 5000$，$1\le A_i,B_i,C_i\le 10000$。

给定 $n$ 个单调不降的数组，初始计数器 $sum=0$。你需要进行 $k$ 次操作，每次选择某个数组的第一个未被删除的元素 $x$，将 $sum$ 加上 $x$，然后将 $x$ 从这个数组中删去。最大化 $sum$。

$1\le n,k\le 3000$，所有数组长度之和不超过 $10^6$，值域 $[0,10^8]$。

有一棵 $n$ 个点的树，每个点上有一个二叉搜索树。

然后依次进行 $m$ 次操作：

• 1 u v x：在 $u\to v$ 路径上每个点的二叉搜索树中插入元素 $x$，即 $\forall p\in \{u\to v\}$ 执行 $\text{insert}(rt_p,x)$：

  void insert(int&p,int x){
      if(!p) return p=x,void();
      if(x<p) insert(ch[p][0],x);
      else insert(ch[p][1],x);
  }
  

• 0 u w：在点 $u$ 上的二叉搜索树中执行 $\text{ask}(rt_u,w)$，求其返回值：

  long long ask(int p,int x){
      if(x==p) return x;
      if(x<p) return ch[p][0]?ask(ch[p][0])+p:p;
      else return ch[p][1]?ask(ch[p][1])+p:p;
  }
  

$1\le n,m,x,w\le 2\times 10^5$，每次 $1$ 操作的 $x$ 互不相同。

有 $n$ 个人在一个长 $L$ 的环上，第 $i$ 个人位于坐标 $a_i$ 处。你要选择 $k$ 个关键点，最小化每个人到最近的关键点的距离的和。输出方案。

$1\le k\le n\le 2\times 10^5$，$1\le L\le 10^{12}$。