四川第十届省赛 A.Angel Beats bitset

四川第十届省赛 A.Angel Beats bitset

题目链接

题解参考：http://www.cnblogs.com/Aragaki/p/9142250.html

考虑用bitset来维护对于所有的\(x\)，需要翻转的位置。但是这样来搞的话，很难处理题目的要求。

所以换个角度，考虑翻转哪些位置会影响这一位。我们会发现，如果位置编号为某些数的公倍数，那么就会受到那些位置的影响。进一步深入想，其实会发现可以考虑只翻转某一位需要翻转哪些位置，这样的方案是唯一的。

设\(s[i]\)为只翻转第\(i\)位需要翻转哪些位置，那么\(s[i]=s[i]\) ^ \(s[2*i]\) ^ ... ^ \(s[k*i]\)，因为翻转第\(i\)位会影响后面的位置，我们消去影响即可得只翻转第\(i\)位的位置。

之后就按照题意搞下就行了。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <bitset>

using namespace std;

typedef long long ll;

const int N = 1e4 + 5, M = 1e5 + 5;

int T;

int n, m;

bitset <N> s[N], pre[N], ans;

int main() {

    scanf("%d", &T);

    while(T--) {

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

        for(int i = 1; i <= n; i++) s[i].reset() ;

        for(int i = n; i >= 1; i--) {

            s[i].set(i) ;

            for(int j = 2 * i; j <= n; j += i) s[i] ^= s[j] ;

        }

        for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ s[i] ;

        ans.reset() ;

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

            int x, y;

            scanf("%d%d", &x, &y) ;

            ans ^= pre[x - 1] ^ pre[y] ;

            printf("%d\n", ans.count()) ;

        }

    }

    return 0;

}