logo AlgoBeat OnlineJudge
登录 注册

#155. 【模板】拉格朗日插值

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

这是一道模板题。

维护一个点集 ,初始时点集为空集。下面依次进行 个操作,操作有两种:

  • 1 x y:向点集中添加点 。保证点集中 互不相同。
  • 2 k:输出 的值,其中 是一个次数不超过 次的函数,且经过 中所有的点。

输入格式

第一行,一个整数 ,表示操作个数。

接下来 行,每行 个整数,描述操作。

数据保证第一个操作必定为 1 类型操作。

输出格式

多行,第 行,一个整数,表示对第 2 类型操作要求计算的 的值。

样例

输入

6
1 2 3
2 5
1 4 7
2 5
1 1 4
2 5

输出

3
9
12

数据范围与提示

样例解释

初始时点集

  • 第一个操作 1 2 3,向点集中插入点 。此时点集
  • 第二个操作 2 5,询问 的值。唯一满足次数不超过 次且经过点 的函数为 ,因此
  • 第三个操作 1 4 7,向点集中插入点 。此时点集
  • 第四个操作 2 5,询问 的值。唯一满足次数不超过 次且经过点 的函数为 ,因此
  • 第五个操作 1 1 4,向点集中插入点 。此时点集
  • 第六个操作 2 5,询问 的值。唯一满足次数不超过 次且经过点 的函数为 ,因此

数据范围

对于 的数据,,所有 互不相同。

数据有一定梯度。