本文共 2070 字，大约阅读时间需要 6 分钟。
题意：求[l, r]区间内不重复的数的和。N个数，M次询问
解：离线处理M次询问，看得别人的思路后才知道的。。。思维局限在预处理N个数上了。。。
对M次询问按右区间的值从小到大排序。扫一遍N个数，如果发现当前这个数在之前出现过，就从之前出现这个数的位置上把这个数删除，在新位置上插入这个数。这样做的好处是删除前面重复的不会影响后面的。时间复杂度控制在(N + M)logN的数量级上。
ps：午不眠，困乎，我命休矣。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define Read() freopen("data.in", "r", stdin)#define Write() freopen("data.out", "w", stdout);typedef __int64 LL;const double eps = 1e-6;const double PI = acos(-1.0);const int inf = 0x1F1F1F1F;using namespace std;const int N = 50010;const int M = 200010;struct node { int l, r; int id; bool operator < (const node& cmp) const { return r < cmp.r; }}p[M];LL c[N];LL ans[M];int num[N];map mp;int lowbit(int i) { return i&(-i);}void add(int p, int val) { for( ; p < N; p += lowbit(p)) { c[p] += val; }}LL sum(int p) { LL res = 0; for( ; p > 0; p -= lowbit(p)) { res += c[p]; } return res;}int main() { //Read(); int T, n, m, i, r, t; scanf("%d", &T); while(T--) { scanf("%d", &n); for(i = 1; i <= n; ++i) scanf("%d", num + i); scanf("%d", &m); for(i = 0; i < m; ++i) { scanf("%d%d", &p[i].l, &p[i].r); if(p[i].l > p[i].r) swap(p[i].l, p[i].r); p[i].id = i; } sort(p, p + m); memset(c, 0, sizeof(c)); mp.clear(); r = 1; for(i = 0; i < m; ++i) { while(r <= p[i].r) { t = num[r]; if(mp[t] != 0) { add(mp[t], -t); } add(r, t); mp[t] = r++; } ans[p[i].id] = sum(p[i].r) - sum(p[i].l - 1); } for(i = 0; i < m; ++i) { OUT(ans[i]); } } return 0;}
转载地址：http://lapoo.baihongyu.com/
