hihocoder1236(北京网络赛J):scores 分块+bitset

时间:2022-01-27 05:16:46

北京网络赛的题- -。当时没思路,听大神们说是分块+bitset,想了一下发现确实可做,就试了一下,T了好多次终于过了

题意:

初始有n个人,每个人有五种能力值,现在有q个查询,每次查询给五个数代表查询的五种能力值,输出有多少个人每种能力值都比查询的小

n和q都是50000,每种能力值最大也为50000

思路:

对于某一个大小的能力值,有哪些人的此项能力值比他小可以用一个50000的bitset表示。这样我们在查询的时候就可以拿到5个对应的bitset,对其进行and就可以得出最终的人数

这样每组询问的复杂度为5*n/32 总复杂度较高但勉强可以接受。

但是这样做有一点问题就是要开5*50000个大小为50000的bitset,显然这样会超内存。。于是想到将bitset分块,这样虽然询问时需要花费一定时间(sqrt)来找到5个bitset

但是显然这个时间是小于n/32的,所以并不会对总时间造成较大的影响,于是显然可行

注意一点就是分块的时候不仅要按照分数段分块,还要按照人数分块,否则如果某个分数段人数太多就gg了

代码:

 #include <bits/stdc++.h>
using namespace std;
bitset<>b[][];
bitset<>tmp;
int n,m,q;
int a[][];
vector<int>v[][];
bitset<>p[];
int tt=;
int now[];
vector<int>d[];
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=; i<; i++)
{
d[i].clear();
for(int j=; j<=m; j++)
{
v[i][j].clear();
}
}
for(int i=;i<;i++)
{
for(int j=;j<=;j++)
{
b[i][j].reset();
}
}
for(int i=; i<n; i++)
{
for(int j=; j<; j++)
{
scanf("%d",a[i]+j);
v[j][a[i][j]].push_back(i);
}
}
int tm=;
for(int i=; i<; i++)
{
tm=;
tmp.reset();
b[i][]=tmp;
d[i].push_back();
for(int j=; j<=m; j++)
{
for(int to:v[i][j])
{
tmp[to]=;
tm++;
}
if(tm>sqrt(n)||j-d[i][(int)d[i].size()-]>sqrt(m)||j==m)
{
b[i][(int)d[i].size()]=tmp;
d[i].push_back(j);
tm=;
}
}
}
scanf("%d",&q);
int pre=;
tm=;
while(q--)
{
for(int i=; i<; i++)
{
scanf("%d",now+i);
now[i]^=pre;
}
for(int i=; i<; i++)
{
int kk=upper_bound(d[i].begin(),d[i].end(),now[i])-d[i].begin();
kk--;
p[i]=b[i][kk];
for(int j=d[i][kk]+; j<=now[i]; j++)
{
for(int to:v[i][j])
{
p[i][to]=;
}
}
//p&=tmp;
}
for(int i=;i<;i++)
{
p[]&=p[i];
}
int ans=p[].count();
pre=ans;
printf("%d\n",ans);
}
}
return ;
}