题目链接：http://oj.ecustacm.cn/problem.php?id=1299
5
1 2 2 1 2
-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; }
原文：https://www.cnblogs.com/-Ackerman/p/12245097.html