既见君子

同济医学生的起落落落落人生记录

hiho 1236 scores

  本来写这道题WA了,我觉得不靠谱阿,看了别人的代码和我没什么区别,可能是我姿势不对,算了重写吧,写着写着就发现自己之前那个程序哪里错了- -真是件奇妙的事,迅速改了就A了

  写完之后还是觉得不靠谱阿,如果bitset真这么强大,那为什么三维偏序还要树套树- -迷糊状态ing

/*------------------
  五维偏序,排序之后bitset分块
  b[i][j]表示第i维前j块里有哪些人
  对于每一维:
    查询到i时候,查到i属于的块数的前一块的答案+暴力统计这一块内部的答案
  再把每一维取与count一下就好了
  时间复杂度:
    预处理:O(n^2/64)
    单次查询:O(n/64*sqrt(n)*5)//我也不知道为什么邱老师说n/64可以看做常数,感觉十分不靠谱,但还是能过,bitset玄学
------------------------*/

#include<cstdio>
#include<iostream>
#include<bitset>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=50000+5;
bitset <INF> b[5][230],tmp,sum;
int k,n,m,sq,len;
struct stu{
    int a[5],num;
    bool operator <(const stu &wq) const{
        return a[k]<wq.a[k];}
} s[INF];
int a[5][INF],pos[5][INF],be[INF],c[6],st[250],en[250];
void pre(){
    scanf("%d%d",&n,&m);
    sq=sqrt(n);
    len=n/sq;
    for(int i=1;i<=len;++i){
        st[i]=(i-1)*sq+1;
        en[i]=i*sq;
        for(int j=st[i];j<=en[i];++j)
            be[j]=i;
    }
    st[len+1]=len*sq+1,en[len+1]=n;
    for(int i=len*sq+1;i<=n;++i)
        be[i]=len+1;
    for(int i=1;i<=n;++i){
        s[i].num=i;    
        for(int j=0;j<5;++j)
            scanf("%d",&s[i].a[j]);
    }
    for(k=0;k<5;++k){
        sort(s+1,s+n+1);
        for(int i=1;i<=n;++i){
            a[k][i]=s[i].a[k];
            pos[k][i]=s[i].num;
            b[k][be[i]].set(s[i].num);
        }
    }
    for(int i=0;i<5;++i){
        for(int j=2;j<=len;++j)
            b[i][j]|=b[i][j-1];//表示前j个不会T,只表示当前就会
    }
}
int query(){
    sum.set();
    for(int i=0;i<5;++i){
        tmp.reset();
        int p=upper_bound(a[i]+1,a[i]+n+1,c[i])-a[i]-1;
        //printf("%d %d %d %d\n",c[i],p,a[i][p],pos[i][p]);
        tmp|=b[i][be[p]-1];
        for(int j=st[be[p]];j<=p;++j)
            tmp.set(pos[i][j]);
        sum&=tmp;
    }
    return sum.count();
}
int main(){
    freopen("scores.in","r",stdin);
    int T,q,lanstan;
    scanf("%d",&T);
    while(T--){
        pre();
        lanstan=0;//要记得清零,之前就WA在这儿
        scanf("%d",&q);
        for(int i=1;i<=q;++i)
          {
              for(int j=0;j<5;++j)
              {scanf("%d",&c[j]);
                  c[j]^=lanstan;}
              printf("%d\n",lanstan=query());
          }
        for(int i=0;i<5;++i)
            for(int j=1;j<=be[n];++j)
                b[i][j].reset();
    }
    return 0;
}


评论
©既见君子
Powered by LOFTER