SPOJ-DQUERY D-query 莫队算法
题意: 给定一个区间和2e5次查询, 查找区间[L, R]的不同的数的个数.
分析: 莫队和主席树都可以解决, 先离线再处理查询.
1. 莫队算法: 莫队算法一般用来处理区间查询问题, 区间必须离线, 更新操作要简单的问题. 主要做法是将区间分块, 然后根据区间的范围进行排序, 查询R节点为第一关键字, L节点为第二关键字. 排序后在进行处理, 算是一种优美的暴力, 莫队算法在处理离线区间查询问题几乎是无敌的. 对于这道题, 查询的是不同数的个数, 离线处理时就直接记录不同的数的个数就好, 算是一道模板题.
2. 主席树: 待更新.
莫队算法代码:
#include <bits/stdc++.h>using namespace std;
const int MAXN = 1e6 + 10;
struct Query
{int l, r, id;
} Q[MAXN];int n, m;
int L = 1, R = 0, Ans = 0;
int pos[MAXN], a[MAXN];
int flag[MAXN], ans[MAXN];
map<int, int> mp;
bool cmp(Query x, Query y)
{if (pos[x.l] == pos[y.l])return x.r < y.r;elsereturn pos[x.l] < pos[y.l];
}void add(int x)
{if (flag[a[x]] == 0)Ans++;flag[a[x]]++;
}
void del(int x)
{flag[a[x]]--;if (flag[a[x]] == 0)Ans--;
}
int main()
{scanf("%d", &n);int unit = sqrt(n);int sz = 0;for (int i = 1; i <= n; i++){scanf("%d", &a[i]);if (mp[a[i]] == 0){mp[a[i]] = ++sz;}a[i] = mp[a[i]];pos[i] = i / unit + 1;}scanf("%d", &m);for (int i = 1; i <= m; i++){scanf("%d%d", &Q[i].l, &Q[i].r);Q[i].id = i;}sort(Q + 1, Q + 1 + m, cmp);for (int i = 1; i <= m; i++){while (L < Q[i].l){del(L);L++;}while (L > Q[i].l){L--;add(L);}while (R < Q[i].r){R++;add(R);}while (R > Q[i].r){del(R);R--;}ans[Q[i].id] = Ans;}for (int i = 1; i <= m; i++)printf("%d\n", ans[i]);return 0;
}主席树代码:
//待更新