题目链接:http://oj.ecustacm.cn/problem.php?id=1299
题目描述
小明最近在研究压缩算法。他知道,压缩的时候如果能够使得数值很小,就能通过熵编码得到较高的压缩比。然而,要使数值很小是一个挑战。
最近,小明需要压缩一些正整数的序列,这些序列的特点是,后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列,小明准备对序列做一个变换来减小数字的值。
变换的过程如下:
从左到右枚举序列,每枚举到一个数字,如果这个数字没有出现过,刚将数字变换成它的相反数,如果数字出现过,则看它在原序列中最后的一次出现后面(且在当前数前面)出现了几种数字,用这个种类数替换原来的数字。
比如,序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在变换过程为:
a1: 1未出现过,所以a1变为-1;
a2: 2未出现过,所以a2变为-2;
a3: 2出现过,最后一次为原序列的a2,在a2后、a3前有0种数字,所以a3变为0;
a4: 1出现过,最后一次为原序列的a1,在a1后、a4前有1种数字,所以a4变为1;
a5: 2出现过,最后一次为原序列的a3,在a3后、a5前有1种数字,所以a5变为1。
现在,给出原序列,请问,按这种变换规则变换后的序列是什么。
最近,小明需要压缩一些正整数的序列,这些序列的特点是,后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列,小明准备对序列做一个变换来减小数字的值。
变换的过程如下:
从左到右枚举序列,每枚举到一个数字,如果这个数字没有出现过,刚将数字变换成它的相反数,如果数字出现过,则看它在原序列中最后的一次出现后面(且在当前数前面)出现了几种数字,用这个种类数替换原来的数字。
比如,序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在变换过程为:
a1: 1未出现过,所以a1变为-1;
a2: 2未出现过,所以a2变为-2;
a3: 2出现过,最后一次为原序列的a2,在a2后、a3前有0种数字,所以a3变为0;
a4: 1出现过,最后一次为原序列的a1,在a1后、a4前有1种数字,所以a4变为1;
a5: 2出现过,最后一次为原序列的a3,在a3后、a5前有1种数字,所以a5变为1。
现在,给出原序列,请问,按这种变换规则变换后的序列是什么。
输入
输入第一行包含一个整数n,表示序列的长度。第二行包含n个正整数,表示输入序列a。
1 <=n<=100000,1<=ai<=10^9
1 <=n<=100000,1<=ai<=10^9
输出
对于每组测试数据,输出一行,包含n个数,表示变换后的序列。
样例输入 Copy
5
1 2 2 1 2
样例输出 Copy
-1 -2 0 1 1
思路:
因为数字的范围的大小是 [1,1e9] 所以不会考虑用数组去记录下标,那么干脆就采取 map 去记录下标
然后要求 [l,r] 之间数字的种类的个数 ,因为是区间问题 ,所以就采取线段树去维护区间
如果一个数字是第一次出现,那么它的这个位置 +1 如果它是第二次(或以上)出现,那么它之前的位置需要 -1 (有点像前缀和)
#include <iostream> #include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #define LL long long #define INF 0x3f3f3f3f #define ls nod<<1 #define rs (nod<<1)+1 const int maxn = 1e5 + 10 ; const LL mod = 20010905; struct segment_tree { int l,r; int val; int lazy; }tree[maxn << 2]; void pushup(int nod) { tree[nod].val = (tree[ls].val + tree[rs].val); } void pushdown(int nod) { tree[ls].lazy += tree[nod].lazy; tree[rs].lazy += tree[nod].lazy; tree[ls].val += (tree[ls].r-tree[ls].l+1) * tree[nod].lazy; tree[rs].val += (tree[rs].r-tree[rs].l+1) * tree[nod].lazy; tree[nod].lazy = 0; } void build(int l,int r,int nod) { tree[nod].l = l; tree[nod].r = r; if (l == r) { tree[nod].lazy = 0; tree[nod].val = 0; return ; } int mid = (l + r) >> 1; build(l,mid,ls); build(mid+1,r,rs); pushup(nod); } void modify(int x,int y,int z,int k=1) { int l = tree[k].l,r = tree[k].r; if (x <= l && y >= r) { tree[k].lazy += z; tree[k].val += (r-l+1) * z; return ; } if (tree[k].lazy) pushdown(k); int mid = (l + r) >> 1; if (x <= mid) modify(x,y,z,k<<1); if (y > mid) modify(x,y,z,(k<<1)+1); pushup(k); } int query(int x,int y,int k=1) { int l = tree[k].l,r = tree[k].r; if (x <= l && y >= r) return tree[k].val; if (tree[k].lazy) pushdown(k); int mid = (l + r) >> 1; int sum = 0; if (x <= mid) sum += query(x,y,k<<1); if (y > mid) sum += query(x,y,(k<<1)+1); return sum; } int a[maxn]; std::map<int,int> mp; int main() { int n; scanf("%d",&n); build(1,n,1); for (int i = 1;i <= n;i++) { int v; scanf("%d", &v); if (mp.count(v)) { int pre = mp[v]; a[i] = query(pre+1,i); modify(pre,pre,-1); } else { a[i] = -v; } mp[v] = i; modify(i,i,1); } for (int i = 1;i <= n;i++) printf("%d ",a[i]); return 0; }