题解 | #可做题#

        这题是利用贪心的思想。那么面对连续赋值的数组，他所带来的任何影响都不会影响到下一段连续子数组（很简单，因为连续子数组异或结果可以被一个未赋值的抵消）。
     那么也就是这个连续子数组对答案产生的贡献取决于子数组前的一个未赋值的数（特别的，如果该数组前没有数字，那么直接计算该段的贡献就好了）。
     对于连续字段前缀和计算后,我们可以知道2进制下每一位为0的数量以及为1的数量，分别记为cnt[0],cnt[1],答案记为 ans,那么假设该前缀和这一位如果为0，那么就没有任何影响,计算贡献ans += (1 << k) * cnt[1]，如果为1，ans += (1 << k) * (cnt[0]+1),cnt[0]表示的是反转了0和1，+1指的是前一个数字带来的影响。最后这一位的结果ans += (1 << k) * min(cnt[1],(cnt[0]+1))
     然后知道如何计算贡献后简单处理一下数组就可以了。
     AC代码：

using namespace std;
#define int long long
const int N = 1e9 ;
int T, n = 0, m, k, l, r;
const int mod = 998244353;
#define ll long long
#define endl '\n'
bool flag = false;
int cnt = 0;
#define all(x) x.begin(),x.end()

void solve()
{
    cin >> n >> m;
    vector<array<int, 2>>s(m);
    for (int i = 0; i < m; i++)
    {
        int x, p; cin >> x >> p; x--;
        s[i] = { x,p };
    }
    sort(s.begin(), s.end());
    int ans = 0;
    
    int lg = __lg(N);
    
    for (int i = 0; i < m; i++) {
        int j = i;
        for (j = i; j + 1 < m && s[j + 1][0] == s[j][0] + 1; j++);
        vector<int>b(1);
        b[0] = s[i][1];
        for (int z = i + 1; z <= j; z++) {
            b.push_back(b.back() ^ s[z][1]);
        }
        for (int k = 0; k <= lg; k++) {
            array<int, 2>cnt{};
            for (auto c : b) {
                cnt[c >> k & 1]++;
            }
            if (s[i][0]==0)cnt[0] = n;
            ans += min(cnt[0] + 1, cnt[1]) * (1ll << k);
        }
        i = j;
    }

    cout << ans << endl;
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    T = 1;
    //cin >> T;


    while (T--)solve();


}