列表

详情

NC216010. JustAnotherGameofStones

描述

Kotori and Umi are playing games of stones, which is hosted by Honoka. The rule is the same as the classic one: There are some piles of stones and the players take turns to remove any positive number of stones from one pile. The one who can't make a legal move loses the game.

This time however, things will be a little different. As the host, Honoka will prepare the games from n candidate piles of stones, where the i-th pile initially has a_i stones. Honoka will perform q operations of the following two types:
  1. Given three integers l, r and x, for all change the number of stones in the i-th candidate pile to , where b_i is the current number of stones in the i-th candidate pile.
  2. Given three integers l, r and x, start a game of stones consisting of piles where the i-th pile contains stones for all , and the -th pile contains x stones. Note that this operation is only querying for answer and will not affect the state of the n candidate piles of stones.

Kotori is always the first to move. As a big fan of Kotori, you would like to know, for each game of stones, the number of ways Kotori can play in the first step to ensure her victory if both players use the best strategy. We consider two ways different if Kotori is taking stones from different piles, or from the same pile but is taking different number of stones.

输入描述

There is only one test case in each test file.

The first line of the input contains two integers n and q () indicating the number of candidate piles and the number of operations.

The second line contains n integers  () where a_i indicates the initial number of stones in the i-th pile.

For the following q lines, the i-th line contains four integers op_i, l_i, r_i and x_i (, , ) indicating the i-th operation, where op_i is the type of operation and the others are the parameters of the operation. Operations are given in the order they're performed.

输出描述

For each operation of the second type output one line containing one integer indicating the answer.

示例1

输入: 

5 4
1 2 1 4 1
2 1 3 1
1 2 4 3
2 2 4 4
2 1 4 4

输出: 

1
0
3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 1173ms, 内存消耗: 72824K, 提交时间: 2021-04-04 16:58:05 

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int inf=1<<30;
struct pr{
	int a,sa,b,xr,s[30];
	friend pr operator+(const pr&a,const pr&b){
		pr c;
		if(a.a<b.a){
			c.a=a.a;c.sa=a.sa;
			c.b=min(a.b,b.a);
		}else if(a.a>b.a){
			c.a=b.a;c.sa=b.sa;
			c.b=min(a.a,b.b);
		}else{
			c.a=a.a;c.sa=a.sa+b.sa;
			c.b=min(a.b,b.b);
		}
		c.xr=a.xr^b.xr;
		rep(i,0,29)c.s[i]=a.s[i]+b.s[i];
		return c;
	}
}a[N*4];
int lz[N*4];
void upd(pr&a,int x){
	if(x<=a.a)return;
	if(a.sa&1)a.xr^=x^a.a;
	rep(i,0,29)a.s[i]+=(((x>>i)&1)-((a.a>>i)&1))*a.sa;
	a.a=x;
}
void bd(int x,int l,int r){
	if(l==r){
		scanf("%d",&a[x].a);
		a[x].sa=1;a[x].b=inf;
		a[x].xr=a[x].a;
		rep(i,0,29)a[x].s[i]=(a[x].a>>i)&1;
		return;
	}
	int m=(l+r)>>1;
	bd(x<<1,l,m);bd(x<<1|1,m+1,r);
	a[x]=a[x<<1]+a[x<<1|1];
}
void dw(int x){
	if(lz[x]>lz[x<<1]){
		lz[x<<1]=lz[x];upd(a[x<<1],lz[x]);
	}
	if(lz[x]>lz[x<<1|1]){
		lz[x<<1|1]=lz[x];upd(a[x<<1|1],lz[x]);
	}
	lz[x]=0;
}
void f(int x,int l,int r,int y,int L,int R){
	if(l<=L&&r>=R&&y<a[x].b){
		if(y>lz[x]){
			lz[x]=y;upd(a[x],y);
		}
		return;
	}
	dw(x);int m=(L+R)>>1;
	if(l<=m)f(x<<1,l,r,y,L,m);
	if(r>m)f(x<<1|1,l,r,y,m+1,R);
	a[x]=a[x<<1]+a[x<<1|1];
}
pr q(int x,int l,int r,int L,int R){
	if(l==L&&r==R)return a[x];
	dw(x);int m=(L+R)>>1;
	if(r<=m)return q(x<<1,l,r,L,m);
	if(l>m)return q(x<<1|1,l,r,m+1,R);
	return q(x<<1,l,m,L,m)+q(x<<1|1,m+1,r,m+1,R);
}
int main(){int n,Q;
	scanf("%d%d",&n,&Q);
	bd(1,1,n);
	rep(i,1,Q){int op,l,r,x;
		scanf("%d%d%d%d",&op,&l,&r,&x);
		if(op==2){
			pr s=q(1,l,r,1,n);
			s.xr^=x;
			rep(i,0,29)if((x>>i)&1)++s.s[i];
			if(!s.xr)printf("0\n");
			else dep(i,29,0)if((s.xr>>i)&1){
				printf("%d\n",s.s[i]);break;
			}
		}else f(1,l,r,x,1,n);
	}
}

上一题

© 2025 nowcoder.com