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


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

#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);
inline void push_down(int u){
if (!lazy[u]) return;
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);
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);
int main(){
For(i,1,n) a[i]=read()&1;
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

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