第一道Ynoi 显然每次询问的答案为三个区间的长度和减去公共数字个数*3.
如果是公共数字种数的话就能用莫队+bitset存每个区间的状态，然后3个区间按位与就行了。
但现在是个数，bitset中除了保存每个数是否出现外，还要保存出现的次数。
这时我们发现每个数字的出现次数之和
\(=n\) 于是想到离散化以后每个数字占bitset中的一格。
还记得
\(SA\)里的基数排序吗？这样就能使第
\(n\)次加入区间的同一个数字有固定的位置安放。
于是就能莫队了。
但是一看数据范围，好像开不下
\(1e5\)个长度为
\(1e5\)的bitset啊。
没关系，把答案分成3组，一组一组来就行了。
#include #include #include #include #include #include using namespace std;const int MAXN = 100010;const int MAXM = 34010;bitset ans[MAXM], now;int n, m, a[MAXN];inline int read(){ int s = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s;}int Q;struct lsh{ int val, id; int operator < (const lsh A) const{ return val < A.val; }}p[MAXN];struct ask{ int l, r, id; int operator < (const ask A) const{ return l / Q == A.l / Q ? r < A.r : l < A.l; }}q[MAXM * 3];int val[MAXN], cnt, sum[MAXN], v[MAXN], all, Ans[MAXM];void work(){ sort(q + 1, q + all + 1); now.reset(); memset(v, 0, sizeof v); int l = 1, r = 1; now.set(val[1]); v[val[1]] = 1; for(int i = 1; i <= all; ++i){ while(r < q[i].r){ ++r; now.set(val[r] - v[val[r]]); ++v[val[r]]; } while(l > q[i].l){ --l; now.set(val[l] - v[val[l]]); ++v[val[l]]; } while(r > q[i].r){ --v[val[r]]; now.set(val[r] - v[val[r]], 0); --r; } while(l < q[i].l){ --v[val[l]]; now.set(val[l] - v[val[l]], 0); ++l; } ans[q[i].id] &= now; }}int main(){ n = read(); m = read(); Q = sqrt(n); for(int i = 1; i <= n; ++i) p[i].val = read(), p[i].id = i; for(int i = 1; i <= 33337; ++i) ans[i].set(); sort(p + 1, p + n + 1); for(int i = 1; i <= n; ++i) if(p[i].val != p[i - 1].val) val[p[i].id] = ++cnt; else val[p[i].id] = cnt; for(int i = 1; i <= n; ++i) ++sum[val[i]]; for(int i = 1; i <= cnt; ++i) sum[i] += sum[i - 1]; for(int i = 1; i <= n; ++i) val[i] = sum[val[i]]; int o = m / 3; if(o){ for(int qqc = 1; qqc <= 2; ++qqc){ cnt = 0; for(int i = 1; i <= o; ++i){ q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; } all = o * 3; work(); for(int i = 1; i <= o; ++i){ printf("%d\n", Ans[i] - int(ans[i].count()) * 3); Ans[i] = 0; ans[i].set(); } } } m -= o * 2; cnt = 0; for(int i = 1; i <= m; ++i){ q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1; } all = m * 3; work(); for(int i = 1; i <= m; ++i) printf("%d\n", Ans[i] - int(ans[i].count()) * 3); return 0;}