3870: Game
内存限制：128 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
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 ai 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≤l≤r≤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 ai and ai+1 stones respectively, after this swapping there will be ai+1 and ai.
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*.
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≤l≤r≤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 ai and ai+1 stones respectively, after this swapping there will be ai+1 and ai.
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 a1,a2,...an, indicating the number of each piles' stones.
The next M lines will have an integar opt (1≤opt≤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≤ai≤1,000,000
1≤N,M≤100,000,∑N,∑M<600,000
1≤L≤R≤N
1≤POS<N
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 a1,a2,...an, indicating the number of each piles' stones.
The next M lines will have an integar opt (1≤opt≤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≤ai≤1,000,000
1≤N,M≤100,000,∑N,∑M<600,000
1≤L≤R≤N
1≤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.
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