## 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;

inline ll read(){

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(){

n=read(),m=read(),q=read(),p=(1<<m)-1;

For(i,1,n) a[i]=read()&1;

t.Build(1,1,n);

while (q--){

int opt=read(),l=read(),r=read();

if (opt==2) puts(t.Query(1,1,n,l,r).f[0]&1?"2":"1");

else if (read()&1) t.update(1,1,n,l,r);

}

}

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

- 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 ...

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

- Codeforces E. Interesting Array（ Line segment tree ）
Title Description : D. Interesting Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard ...

- B. Interesting Array（ Line segment tree ）
B. Interesting Array time limit per test 1 second memory limit per test 256 megabytes input standard ...

- 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* ...

- 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 . ...

- 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 $ ...

- 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 ...

- 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

- 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 ...

- .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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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) ...

- ( 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 : ...

- The finger of the sword offer—— Interview questions 5： Replace blank space
utilize STL: #include"iostream" #include"stdio.h" #include"algorithm" using ...

- 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=" ...