当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6610:Game

题目描述
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 \leq{l}\leq{r}\leq 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 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 \leq opt \leq 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 \leq a_i \leq 1,000,000$

$1 \leq N, M \leq 100,000, \sum{N}, \sum{M} < 600,000$

$1 \leq L \leq R \leq N$

$1 \leq POS < N$
输出解释
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
输出样例
3
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6610

最后修改于 2020-10-25T23:32:47+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/10000MS(Java/Others) 65536/65536K(Java/Others)