hihocoder #1236 Scores (15北京赛区网络赛J) （五维偏序，强制在线，bitset+分块）

链接：http://hihocoder.com/problemset/problem/1236

思路;

有n个五维的向量，给出q个询问，每个询问是一个五维向量，问有多少个向量没有一维比这个向量大。并且答案需要加密，除了第一个答案，其他答案都要和上一个答案异或。

因为是强制在线所以不能用cdq分治写。。我们可以用stl里面的bitset来写这道题，但是因为数据还是太大了，这里我们可以用分块处理下，降低空间复杂度，需要用的时候直

接二分查找需要的块，预处理后可以o(1)获取前k-1个块的信息，然后我们对当前块逐个更新下就好了。

这里 bit[i][j]代表第i维前j个块有多少个人。

实现代码：

#include<bits/stdc++.h>

using namespace std;

const int M = 5e4+;

struct node{

    int val,id;

    node(){};

    node(int val,int id):val(val),id(id){}

    bool operator < (const node &b) const{

        if(val == b.val) return id < b.id;

        return val < b.val;

    }

}a[][M];

bitset<M>bit[][];

bitset<M>ans;

bitset<M>temp;

int block;

int num;

int main()

{

    int t,n,m,q;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        for(int i = ;i <= n;i ++)

            for(int j = ;j <= ;j ++)

                scanf("%d",&a[j][i].val),a[j][i].id = i;

        for(int i = ;i <= ;i ++) sort(a[i]+,a[i]+n+);

        block = sqrt(n);

        //分块，预处理

        for(int i = ;i <= ;i ++){

            for(int j = ;(j-)*block < n;j ++){

                bit[i][j].reset();

                bit[i][j] = bit[i][j-];

                int st = (j-)*block;

                for(int k = ;k <= block&&st+k<=n;k ++){

                    bit[i][j].set(a[i][st+k].id);

                }

            }

        }

        int q;

        scanf("%d",&q);

        int now[];

        int pre = ;

        while(q--){

            for(int i = ;i <= ;i ++){

                scanf("%d",&now[i]);

                now[i]^=pre;

            }

            ans.reset();

            for(int i = ;i <= ;i ++){

                int tmp = lower_bound(a[i]+,a[i]+n+,node(now[i],n+))-a[i]-;

                tmp = tmp/block;

                temp = bit[i][tmp];//获取之前块的信息

                for(int j = tmp*block+;a[i][j].val<=now[i]&&j<=n;j++){ //当前块这个更新

                    temp.set(a[i][j].id);

                }

                if(i == )

                    ans = temp;

                else

                    ans &= temp;

            }

            int num = ans.count();

            pre = num;

            printf("%d\n",num);

        }

    }

    return ;

}