N 个元素在修改 M 个时间戳后的 XOR

Question

There are N elements (numbered 1 to N). All are Zero initially. There are M timestamps. In each timestamp, all the elements numbered between L and R (both inclusive) increased by P. Find XOR of all elements after M timestamps.

输入格式

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. The first line contains two space-separated integers N, M. M lines follow. The ith of these M lines contains three space-separated integers L, R, P, describing the ith timestamp.

约束条件

1 < T < 100
1 < N < 1e16
0 < M < 1e4
1 < L < R < N
0 < P < 1e9
Sum of M over all test cases do not exceed 1e5

我的方法

while(t--){
          long long n,m;
          cin>>n>>m;
          long long a[n+1]={0};
          while(m--){
              ll x,y,p;
              cin>>x>>y>>p;
             for(int i=x;i<=y;i++)
              a[i]=a[i]+p;
          }
          long long  ans=0;
          for(int i=1;i<=n;i++)
          ans=ans^a[i];
 
          cout<<ans<<"\n";
      }

我只能想出一个蛮力的想法，似乎无法解决，因为约束太大了。

如何在 O(1) 时间内回答每个测试用例。此题限时1秒

Answer 1

N 个元素可以看作数组的成员。

如果有偶数个具有相同值的连续元素，则所有这些元素的异或为零。

如果有奇数个连续元素具有相同的值X，所有这些元素的异或为X。

这个问题的一个解决方案是遍历数组，跟踪 X 在值发生变化之前有多少重复值，并对 X 进行异或运算运行重复次数为奇数时的结果。

这可以通过仅考虑输入中指定的 L 和 R 索引来计算，而无需实际构造数组，也不必遍历每个元素，这些索引指示数组值可能与其相邻元素不同。

这是 Python 中的一个实现，它读取来自 stdin 的输入。

import sys
from collections import defaultdict

def getline():
    return sys.stdin.readline().rstrip()

T = int(getline())
for _ in range(T):
    N, M = map(int, getline().split())
    lookup = defaultdict(int)
    for _ in range(M):
        L, R, P = map(int, getline().split())
        lookup[L] += P
        lookup[R + 1] -= P
    lookup[N + 1] = 0
    result = 0
    X = 0
    last_idx = 1
    for idx in sorted(lookup):
        count = idx - last_idx
        if count & 1:
            result ^= X
        X += lookup[idx]
        last_idx = idx
    print(result)

N 个元素在修改 M 个时间戳后的 XOR

XOR of N elements after M timestamps of modification in them

bit-manipulation

xor

输入格式

约束条件

我的方法