题目链接 https://www.luogu.org/problemnew/show/P4688
第一道 Ynoi
显然每次询问的答案为三个区间的长度和减去公共数字个数 * 3.
如果是公共数字种数的话就能用莫队 + bitset 存每个区间的状态, 然后 3 个区间按位与就行了.
但现在是个数, bitset 中除了保存每个数是否出现外, 还要保存出现的次数.
这时我们发现每个数字的出现次数之和 \(=n\)
于是想到离散化以后每个数字占 bitset 中的一格.
还记得 \(SA\) 里的基数排序吗? 这样就能使第 \(n\) 次加入区间的同一个数字有固定的位置安放.
于是就能莫队了.
但是一看数据范围, 好像开不下 \(1e5\) 个长度为 \(1e5\) 的 bitset 啊.
没关系, 把答案分成 3 组, 一组一组来就行了.
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <bitset>
- #include <cmath>
- #include <iostream>
- using namespace std;
- const int MAXN = 100010;
- const int MAXM = 34010;
- bitset <MAXN> 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;
- }
来源: http://www.bubuko.com/infodetail-3092729.html