## The question

Now? cf It's true nm trouble , Youdao web translation and Google translation are a ghost beast

Two people are playing a game .

One has $$n$$ Number sequence $$B$$, There was a piece in the beginning $$B$$ The first position .

Both sides operate in turn , Before the first operation $$B_1-1$$.

Then every time , You can move the pieces to a position $$j\in[i,min(i+m,n)]$$ And $$B_j>0$$, And then $$B_j-1$$, Suppose that both sides adopt the optimal strategy , Who can't operate first will lose .

And then the problem you're going to solve is ：

Give a length of $$n$$ Sequence $$A$$ and $$m$$, And the number of questions $$q$$.

There are two kinds of inquiries , One is interval plus , The other is to ask $$A$$ An interval of a sequence , Take this interval as a sequence $$B$$ Play the game above , Ask the first or the second to win .

$$n.q<=2*10^5 m<=5$$

## Solution

Let's start with a sequence $$B$$, How to judge whether to win first or second hand .

set up $$f_i$$ For the first time when a player chooses the second $$i$$ Will he win when he's in a position .

If $$[i+1,i+m]$$ There is a winner in the game , Then this position is the first to lose ,$$f_i=0$$.

Otherwise, it depends on the parity of the value in the current position , Calm analysis, it's not hard to think of when $$A_i$$ For even when $$f_i=0$$, In an odd number of $$f_i=1$$.

So at the moment $$f_i$$ We can get the value from $$f_j (j \in [i+1,i+m])$$ Launched in .

And then think about how to maintain it .

Find out $$m$$ Very small , So we're going to do a lot of back work $$m$$ individual $$f_j$$ Press it up .

Use the line tree to maintain this thing , Each node maintains when the right end of the interval is on the right $$m$$ Location $$f_j$$ Press up for $$k$$ when , The left end of the interval, the right end of the interval $$m$$ individual $$f_j$$ The value of pressing up .

When merging $$xjb$$ I'll just transfer it .

If you change it , It's not hard to find out when $$d$$ It's no use being even .

We can treat all the numbers in the interval as ^1 And the value of , So the modification is just $$swap$$ Just a moment .

Feeling $$NOIP$$ After doing cultural courses, it leads to serious mental decline ... Even such a problem depends on the solution ...$$QAQ$$

#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define cross(i,k) for (register int i=first[k];i;i=last[i])
using namespace std;
typedef long long ll;
ll x=0;int ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int N = 3e5+10;
int n,m,q,p,a[N];
struct node{
int f[32];
inline node operator + (const node &b)const{
node ans;
For(i,0,p) ans.f[i]=f[b.f[i]];
return ans;
}
};
inline node New(int x){
node ans;ans.f[0]=x;
For(i,1,p) ans.f[i]=i<<1&p;
return ans;
}
struct SegMent_Tree{
node v[N<<2][2];
bool lazy[N<<2];
inline void push_up(int u){For(i,0,1) v[u][i]=v[u<<1][i]+v[u<<1^1][i];}
inline void Build(int u,int l,int r){
if (l==r){v[u][0]=New(a[l]),v[u][1]=New(a[l]^1);return;}
int mid=l+r>>1;Build(u<<1,l,mid),Build(u<<1^1,mid+1,r);
push_up(u);
}
inline void push_down(int u){
if (!lazy[u]) return;
swap(v[u<<1][0],v[u<<1][1]),swap(v[u<<1^1][0],v[u<<1^1][1]);
lazy[u<<1]^=1,lazy[u<<1^1]^=1,lazy[u]=0;
}
inline void update(int u,int l,int r,int ql,int qr){
if (l>=ql&&r<=qr){lazy[u]^=1,swap(v[u][0],v[u][1]);return;}
int mid=l+r>>1;push_down(u);
if (qr<=mid) update(u<<1,l,mid,ql,qr);
else if (ql>mid) update(u<<1^1,mid+1,r,ql,qr);
else update(u<<1,l,mid,ql,qr),update(u<<1^1,mid+1,r,ql,qr);
push_up(u);
}
inline node Query(int u,int l,int r,int ql,int qr){
if (l>=ql&&r<=qr) return v[u][0];
int mid=l+r>>1;push_down(u);
if (qr<=mid) return Query(u<<1,l,mid,ql,qr);
else if (ql>mid) return Query(u<<1^1,mid+1,r,ql,qr);
else return Query(u<<1,l,mid,ql,qr)+Query(u<<1^1,mid+1,r,ql,qr);
}
}t;
int main(){
t.Build(1,1,n);
while (q--){
if (opt==2) puts(t.Query(1,1,n,l,r).f[0]&1?"2":"1");
}
}


## Codedforces 1076G Array Game More articles on line segment trees

1. codeforces 482B. Interesting Array【 Segment tree interval update 】

subject :codeforces 482B. Interesting Array The question : Give you a value n and m In the operation , Each operation is three numbers l ,r,val. It's the interval l---r The value of and on is val, Finally, I ask you the original number ...

2. Light OJ-1082 - Array Queries, Segment tree interval query maximum , ha-ha , Water pass ~~

...

3. Codeforces E. Interesting Array（ Line segment tree ）

Title Description : D. Interesting Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard ...

4. B. Interesting Array（ Line segment tree ）

B. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard ...

5. CodeForces Round #179 (295A) - Greg and Array A line tree is used twice

Interval updating and interval summation of segment trees ... A line segment tree like this is used twice ... Scan first 1~k... Use the line tree to count the number of times each operation is performed ... So every operation becomes op. l  , op.r , op.c= times* ...

6. CF1114F Please, another Queries on Array?（ Line segment tree , number theory , Euler function , State compression ）

I also came up with a positive solution to this problem in the examination room …… But it didn't come out . Topic link :CF Original network The main idea of the topic : Give a length of $n$ Sequence $a$,$q$ Operations : Interval times $x$, Find the Euler function module of interval product $10^9+7$ Value . ...

7. CF 1023D Array Restoration - Line segment tree

Answer key It's very easy to think of line segment trees , You can also use union search to . There is also a great God who uses $O(n)$ It's over Orz To determine whether the sequence given by the input can be colored , Two conditions must be met : 1. There must be one in the sequence $q$ 2. Two identical numbers \$ ...

8. CodeForces 266E More Queries to Array...（ Line segment tree + Formula expansion ）

I started to think it was a regular question , Self righteous pushed a rule , It turns out that none of the test data .... I saw love God's blog just found out that just unfolding the formula can find the law . But it's kind of 6 But I'm wrong , But there's nothing wrong with maintaining , Just change it. ( I've changed it for two hours ...

9. Codeforces #504(div1+div2) 1023D Array Restoration( Line segment tree )

The main idea of the topic : Give you an array , The array is passed through q The result of subinterval covering , The first i The second covering is to assign the value in the interval to i, There are a number of places where the values are unknown ( Namely 0), Let you determine whether the array can be obtained by covering , If possible , Output any feasible array . ...

## Random recommendation

1. Data warehouse development ——Kettle Examples of use

Kettle It's an open garden ETL Tools , For data warehouse Spoon. Tools : download Spoon, Decompression is available   1. Learn about common components :     Table input     Insert \ to update     Data synchronization     Text file output     ...

2. .net Test learning -- understand .net Test options

1. Create simple test based applications (1) start-up visual studio( Installed c# Of ) (2)  choice File|New project (3) Create a C# project, The name and save path are set by yourself , Hypothetical naming ...

3. CentOS7 Next linux The solution to not being able to access the Internet ​,centos7 eth0 No, ip,IP Suddenly lost

CentOS7 Next linux The solution to not being able to access the Internet ​ stay CentOS VMware Lower installation linux after , Sometimes we can't connect to the Internet directly , I'd like to share my experience , Hope to be useful for beginners Tools / raw material XP System VMware.Wo ...

4. Linux The finite state machine of programming FSM The understanding and Realization of

Finite state machine (finite state machine) abbreviation FSM, A mathematical model that represents a finite number of States and the transfer and action between them , It is widely used in the field of computer .FSM It's an efficient programming method inside a logical unit , stay ...

5. select Label default options

1.selected: This option is selected by default : 2.disabled: This option cannot be selected by the mouse :( notes : When options are not hidden ) 3.style="display:none": Hide this option :( notes : The ...

6. python in list Operation method

1, Create a list Just enclose the different data items separated by commas in square brackets . As shown below : Copy code The code is as follows :list1 = ['physics', 'chemistry', 1997, 2000];list2 ...

7. Daffodils are python3 stay pycharm The implementation of the

--- Resume content start --- # Method 1 :#-*- coding: utf-8-*-while True: num = input(" Please enter a three digit number ") num = int(num) ...

8. ( turn )CentOS Partition operation details

CentOS Partition operation details original text :http://blog.csdn.net/yonggeit/article/details/77924393 Disk partition Two choices of partition format :MBR and GPT Partition command : ...

9. The finger of the sword offer—— Interview questions 5： Replace blank space

utilize STL: #include"iostream" #include"stdio.h" #include"algorithm" using ...

10. struts2 First day of introduction ---------- A simple example

After setting up the environment, you can start to type the code . First, create a simple submit form jsp page (html The page can also ), <%@ page language="java" import=" ...