Codeforces Round #832 (Div. 2)「D 思维 + 异或前缀和 + 奇偶二分优化」

D. Yet Another Problem

题目描述：

给你一个长度为n的数组，m次询问，每次询问都给出一个区间[L, R]，你可以进行如下操作若干次

• 在[L, R]中选择一个长度为奇数的连续的子区间[l,r],使得区间[l, r]的所有a[i]都变成a[l]^[al+1]^...^a[r]

问最少经过多少次可以使得区间[L,R]的所有数字都变成0

每次询问都是独立的

思路：

简单分析一下，对于二进制的第i位，我们假设区间[L,R]中第i位是1的数量是num

• 假设num是奇数，我们选取的长度为奇数的子区间中的第i位是1的数量cnt是偶数，则异或后第i位应该是0，也就是使得[L,R]中的第i位的数量减少了偶数个，但奇数-偶数结果还是奇数

根据同样的方式，我们可以发现无论怎么操作，都不会改变每一位的1的数量的奇偶性

所以如果区间异或和等于0，才能满足条件

如果区间长度为奇数，如果所有元素非0，那答案就是1，如果都是0，则答案也是0

如果区间长度为偶数：

则一定存在某个mid,满足a[L]^a[L+1]^...^a[mid] = a[mid+1]^...^a[r] = 0，其中mid-l+1是奇数，利用前缀异或和的思想，我们其实转变成了在区间[L, R]中找一个mid满足sum[mid] = sum[L-1]，sum是异或前缀和

我们只需要用map存下来每个sum[i]出现的位置，然后去里面遍利一遍看是否存在符合长度要求以及在规定的区间内的

但是有些本事就是000的区间，我们不需要对其进行操作，我们可以搞一个前缀和来判就行

如果这样写就会返回一个TLE

原因是你遍历的时候会遍历到很多无用的长度为偶数的点

但是我们只需要知道是否存在一个奇数长度的就行，所以我们可以对奇偶分开讨论，开俩map，然后去里面二分，看是否存在就行

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
ll tr[MAX];
ll sum[MAX];
ll pre[MAX];
ll fuck[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        pre[i] = pre[i - 1] + tr[i];
        sum[i] = sum[i - 1] ^ tr[i];
    }
    map<ll, vector<ll>>odd, even;
    for(int i = 1; i <= n; ++i){
        if(i%2)odd[sum[i]].push_back(i);
        else even[sum[i]].push_back(i);
    }
    for(int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        if((sum[x-1] ^ sum[y]) != 0){
            cout << -1 << endl;
        }
        else{
            int len = y - x + 1;
            if(len % 2 == 1){
                if(pre[y] - pre[x - 1] == 0)cout << 0 << endl;
                else cout << 1 << endl;
            }
            else{//oushu
                if(pre[y] - pre[x - 1] == 0)cout << 0 << endl;
                else{
                    int ans = inf;
                    if(tr[x] == 0 || tr[y] == 0){
                        ans = 1;
                    }
                    else{
                        if(x % 2){
                            int id = (int)(lower_bound(odd[sum[x-1]].begin(), odd[sum[x-1]].end(), x) - odd[sum[x-1]].begin());
                            if(id < odd[sum[x-1]].size() && odd[sum[x-1]][id] <= y)ans = 2;
                            else ans = -1;
                        }
                        else{
                            int id = (int)(lower_bound(even[sum[x-1]].begin(), even[sum[x-1]].end(), x) - even[sum[x-1]].begin());
                            if(id < even[sum[x-1]].size() && even[sum[x-1]][id] <= y)ans = 2;
                            else ans = -1;
                        }
                    }
                    
                    cout << ans << endl;
                }
                
            }
        }
    }
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78