## Description:

Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from $1$ to $N$ , the i th pile has $a_i$ stones.

First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with $L$ and the rightmost one is $R$ . After, Bob will choose another consecutive piles labelled from $l$ to $r (L \le l \le r \le R)$ . Then they're going to play game within these piles.

Here's the rules of the game: Alice takes first and the two will take turn to make a move: choose one pile with nonegetive stones and take at least one stone and at most all away. One who cant make a move will lose.

Bob thinks this game is not so intersting because Alice always take first. So they add a new rule, which is that Bob can swap the number of two adjacent piles' stones whenever he want before a new round. That is to say, if the $i$ th and $i+1$ pile have $a_i$ and $a_i+1$ stones respectively, after this swapping there will be $a_i+1$ and $a_i$ .

Before today's game with Bob, Alice wants to know, if both they play game optimally when she choose the piles from L to R, there are how many pairs $(l, r)$ chosed by Bob that will make Alice win.

## Input:

Input contains several test cases.

For each case:

The fisrt line contains $N$ , $M$ . $N$ is mentioned aboved ans M is the number of the sum of game rounds and the times of Bob's swapping.

The second line contains $N$ integars $a_1,a_2,...a_n$ , indicating the number of each piles' stones.

The next $M$ lines will have an integar $opt (1 \le opt \le 2)$ , indicating the type of operation.

If opt equals $1$ , then $L$ and $R$ follow. Alice and Bob start a new round and Alice choose $L$ and $R$ as mentioned.

If opt equals $2$ , then $POS$ follows. Bob will swap the piles labelled $POS$ and $POS+1$ .

$0 \le a_i \le 1,000,000$

$1 \le N,M \le 100,000, \sum N, \sum M<600,000$

$1 \le L \le R \le N$

$1 \le POS<N$

## Output:

For each case:

For each opt which equals $1$ , you shall output one line with an integar indicating the number of pairs $(l,r)$ that will make Alice win the round.

3 3
4 0 4
2 2
2 1
1 1 3

## Sample Output:

3

### 题目链接

1. l r 求区间 $[l,r]$ 内 $NIM$ 博弈先手必胜区间数量
2. pos 将 $a_{i}$ 与 $a_{i+1}$ 交换

$NIM$ 博弈必胜表示区间异或和为零，即左右端点异或和前缀和相等

## AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxb = (1 << 21) + 5;
int n, m;
int block;
int a[maxn], b[maxn];
struct Query { int l, r, t, id; };
Query qry[maxm];
int upd[maxm];
int qrytot, updtot;
long long cur;
long long cnt[maxb];
long long ans[maxm];
void Add(int idx) { cur += cnt[b[idx]]++; }
void Sub(int idx) { cur -= --cnt[b[idx]]; }
void Modify(int t, int i) {
if (upd[t] >= qry[i].l && upd[t] <= qry[i].r) Sub(upd[t]);
b[upd[t]] ^= a[upd[t]];
std::swap(a[upd[t]], a[upd[t] + 1]);
b[upd[t]] ^= a[upd[t]];
if (upd[t] >= qry[i].l && upd[t] <= qry[i].r) Add(upd[t]);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
while (std::cin >> n >> m) {
block = std::pow(n, 2. / 3);
qrytot = updtot = 0;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
b[i] = b[i - 1] ^ a[i];
}
for (int i = 1, opt, l, r, p; i <= m; ++i) {
std::cin >> opt;
if (opt == 1) {
std::cin >> l >> r;
qry[++qrytot] = (Query) {l - 1, r, updtot, qrytot};
} else if (opt == 2) {
std::cin >> p;
upd[++updtot] = p;
}
}
std::sort(qry + 1, qry + qrytot + 1, [&] (const Query &k1, const Query &k2) {
if (k1.l / block != k2.l / block) return k1.l < k2.l;
if (k1.r / block != k2.r / block) return k1.r < k2.r;
return k1.t < k2.t;
});
cur = 0;
int l = 0, r = -1, t = 0;
for (int i = 1; i <= qrytot; ++i) {
while (l < qry[i].l) Sub(l++);
}