题目
现在给定一个N个数的序列A1 A2…,和大量的查询(i,j)(j 1≤≤≤N)。对于每个查询(i, j)你要计算子序列Ai, Ai1…Aj。——重复的数只能算一次。
输入
第一行是一个整数T(1≤T≤10),indecating以下测试点的数量。 对于每种情况输入格式如下: 1:N(1≤N≤30000)。 第2行:N个整数A1, A2…,一个Ai(0≤≤1000000000)。 3行:Q Q(1≤≤100000),查询的数量。 接下来问:每一行包含2整数,j代表一个查询(j 1≤≤≤N)。
输出
对于每个查询在一行中打印指定子序列的不同值的和。
题解 因为不允许重复 所以需要有清0操作。边插入(update)清零(update)。边询问。 离线处理多次询问。离散化处理Ai 以便存入到vis[],dex[]中。 将区间的右端点从小到大将区间排序。比如序列 1 3 3 2 3。查询(2,3) ; (3,5)。 查询(23)在插入1 3 3 的时候插入第二个3的时候就会把第一个3清0。插入 2 3时会把第二个3清0。 假如先查询 (35)。会在第一次查询时把第一个第二个3都清0。无法查询(23)。
#include#define m(a,b) memset(a,b,sizeof a)typedef long long ll;using namespace std;const int N30005<<2;ll sum[N],ans[N],refl[N],a[N];int pre[N];struct interval{int l,r,id;}span[N];bool cmp(interval a,interval b){return a.r