F (莫队+分块)little w and Discretization
首先啊,我们可以知道,对于数值大于 3e5 的数,离散化后一定会变得不同。所以将其变为3e5+1既可。
经过观察我们发现本题和mex有关(最小未出现正整数)。求出mex后对于大于mex的数,一定是会变得不同的。
举个例子, [1,2,4,7] 的mex为3 离散后的结果为[1,2,3,4] 大于3 的数都变得不同了。
那么怎么求mex
贴个链接
https://www.luogu.com.cn/problem/P4137
(这里的mex是最小的未出现的非负整数,也就是说可以是0)
我们发现题解里有很多说主席树的,但是我们不会怎么办(但是题解里有说莫队的被我看到了)
如果你打过杭电多校,那么你一定记得有个题是莫队套分块的。
求mex也是这样的,这里就关放上add del que的代码
inline void add(int p) { cot[p]++; if (cot[p] == 1)sum[p / sq]++; } inline void del(int p) { cot[p]--; if (cot[p] == 0)sum[p / sq]--; } inline int que() { for (int i = 1; i <= sq; i++) { if (sum[i - 1] != sq) { for (int j = (i - 1)*sq; j < i*sq; j++) { if (!cot[j])return j; } } } }
需要解释的就是que了,sum保存着每个块中的出现的数的个数,如果不等于sq,说明没有放满,第一个没有放满的块里就有我们要的mex。
是不是很简单,然后就在分块套一个区间求和既可
注意由于本题只要正整数,所以mex不能是0,第一个块的大小应该是sq-1,特判一下就可以了。
const int maxnum = 3e5 + 5; int sq = 550; int sum[550];//求mex的 int cot[maxnum];//求mex的 int cnt[maxnum];//求和的 int S[maxnum];//求和的 int SUM;//求和的 struct query // 把询问以结构体方式保存 { int l, r, id; } Q[maxnum]; bool cmp(query &a, query &b) { if (a.l / sq != b.l / sq) return a.l < b.l; if ((a.l / sq) & 1) return a.r < b.r; return a.r > b.r; } int ans[maxnum]; int a[maxnum]; int n, m; inline void add(int p) { cot[p]++; if (cot[p] == 1)sum[p / sq]++; cnt[p]++; S[p / sq]++; SUM++; } inline void del(int p) { cot[p]--; if (cot[p] == 0)sum[p / sq]--; cnt[p]--; S[p / sq]--; SUM--; } inline int pre(int p) { int res = 0; for (int i = 0; i < p / sq; i++) res += S[i]; for (int i = p / sq * sq; i <= p; i++)res += cnt[i]; return res; } inline int que() { for (int i = 1; i <= sq; i++) { if ((i - 1) == 0) { if (sum[i - 1] != sq - 1) { for (int j = (i - 1)*sq + 1; j < i*sq; j++) { if (!cot[j])return j; } } } else { if (sum[i - 1] != sq) { for (int j = (i - 1)*sq; j < i*sq; j++) { if (!cot[j])return j; } } } } } void slove() { cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++) { if (a[i] > 3e5)a[i] = 3e5 + 1; } cin >> m; for (int i = 1; i <= m; i++) { cin >> Q[i].l >> Q[i].r; Q[i].id = i; } sort(Q + 1, Q + 1 + m, cmp); int l = 1, r = 0; for (int i = 1; i <= m; i++) { while (l > Q[i].l) add(a[--l]); while (r < Q[i].r) add(a[++r]); while (l < Q[i].l) del(a[l++]); while (r > Q[i].r) del(a[r--]); int mex = que(); ans[Q[i].id] = SUM - pre(mex); } for (int i = 1; i <= m; i++)cout << ans[i] << endl; }
完整代码地址
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48813168