给出一个序列,和m个查询。每一个查询有3个区间,问3个区间去掉相同的数字后,一共有多少个数字。
利用bitset的集合交来查询。b1&b2&b3可以统计3个区间一共有多少个相同数字。
对于某个数字i,在序列里面出现了k次,那么他就占了k位。这种可以通过离散化重新分配id来实现。
fr(i,1,n+1) a[i] = lower_bound(v+1,v+1+n,a[i])-(v+1);
因此一共需要n位来存储。这样就可以直接对m个查询当成是m*3个query来做了。
对于每一个query,把答案&到对应的ans上。
ans[q[i].id] &= sum;
但是m有10^5,n*m就很大,需要对m进行分段处理。
对于每一个分段,用莫队就好了。add的时候对应的位置1,del就置0.
void add(int idx){
sum.set(idx + num[idx]++);
}
void del(int idx){
sum.reset(idx+(--num[idx]));
}
代码
int block_size;
struct query{
int l,r,id;
int block;
int r_block;
int t;
bool operator<(const query &q) const{
if(block != q.block) return block<q.block;
return r<q.r;
}
};
bitset<N> ans[N/3+10],sum;
int tot[N],num[N];
int a[N],v[N];
void add(int idx){
sum.set(idx + num[idx]++);
}
void del(int idx){
sum.reset(idx+(--num[idx]));
}
vector<query> q;
void sol(){
sum.reset();
clr(num);
sort(q.begin(), q.end());
fr(i,0,q.size()/3){
tot[i] = 0;
ans[i].set();
}
int l = 1, r = 1;
add(a[1]);
fr(i,0,q.size()){
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--]);
ans[q[i].id] &= sum;
tot[q[i].id] += q[i].r - q[i].l + 1;
}
fr(i,0,q.size()/3){
pf("%d\n",tot[i] - 3*ans[i].count());
}
}
int main(){
int n,m;
sf("%d%d",&n,&m);
block_size = sqrt(n);
int process_num = max(1,m/3);
fr(i,1,n+1){
sf("%d",&a[i]);
v[i] = a[i];
}
sort(v+1,v+1+n);
fr(i,1,n+1) a[i] = lower_bound(v+1,v+1+n,a[i])-(v+1);
fr(i,0,m){
fr(j,0,3){
query qy;
sf("%d%d",&qy.l,&qy.r);
qy.id = q.size()/3;
qy.block = qy.l/block_size;
q.pb(qy);
}
if((i == m-1) || (i+1)%process_num==0){
sol();
q.clear();
}
}
}