5.26 NOI 模拟

\(T1\)石子与HH与HHの取

博弈是不可能会的

\(c_i\)相等,比较显然的\(Nim,\)直接前缀异或求一下

\(a_i=1,\)区间长度对\(2\)取模

结论\(:\)黑色石子严格大于白色个数先手赢

反证,小于等于的话,我们后手肯定存在策略使自己异或和不为\(0\)

特殊情况,先手只有一堆,并且后手此时异或和为\(0,\)寄

讨论完之后用简单数据结构维护即可

\(T2\)离子王国

能想到扫描线就比较显然了

结论很好猜\(:\)当\(k\)在最大值和最小值之间的时候有解

//考场上已经想到求区间最大最小解决了(不会维护)

//扫描线之类的题我还是不是很会

//首先我们线段树维护的是我们插入后面每个l的历史最大值

//我们只需要查区间最小最大及出现位置即可啦,感觉很强,我考场上离正解就差一步扫描线

#include<bits/stdc++.h>

#define MAXN 500005

using namespace std;

const int INF=0x3f3f3f3f;

template<class T>

T Read()

{

	T x=0,f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9')

	{

		if(ch=='-')

		f=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^'0');

		ch=getchar();

	}

	return x*f;

}

int (*read)()=Read<int>;

#define read Read<int>

struct Que

{

	int l,r,k,id,res;

}que[MAXN];

int n,m,s[MAXN],val[MAXN];

vector<int>poz[MAXN];

namespace Seg

{

	#define ls (x<<1)

	#define rs ((x<<1)|1)

	int lz[MAXN<<1],Max[MAXN<<1],Min[MAXN<<1],TagMax[MAXN<<1],TagMin[MAXN<<1];

	int SumMax[MAXN<<1],SumMin[MAXN<<1];

	void Init(){for(int i=1;i<2*MAXN;i++) TagMax[i]=Max[i]=-INF,TagMin[i]=Min[i]=INF;}

    void pd(int x,int l,int r)

    {

    	if(l==r)

    	{

    		lz[x]=0,TagMax[x]=-INF,TagMin[x]=INF;

    		return ;

		}

		//关于这个历史最大值最小值

		//每个时刻的Tag/Sum都记录一下

		Max[ls]=max(Max[ls],SumMax[ls]+TagMax[x]);

		Min[ls]=min(Min[ls],SumMin[ls]+TagMin[x]);

		SumMax[ls]+=lz[x];

		SumMin[ls]+=lz[x];

		TagMax[ls]=max(TagMax[ls],lz[ls]+TagMax[x]);

		TagMin[ls]=min(TagMin[ls],lz[ls]+TagMin[x]);

		lz[ls]+=lz[x];

		Max[rs]=max(Max[rs],SumMax[rs]+TagMax[x]);

		Min[rs]=min(Min[rs],SumMin[rs]+TagMin[x]);

		SumMax[rs]+=lz[x];

		SumMin[rs]+=lz[x];

		TagMax[rs]=max(TagMax[rs],lz[rs]+TagMax[x]);

		TagMin[rs]=min(TagMin[rs],lz[rs]+TagMin[x]);

		lz[rs]+=lz[x];

		lz[x]=0,TagMax[x]=-INF,TagMin[x]=INF;

	}

	void push_up(int x)

	{

		SumMax[x]=max(SumMax[ls],SumMax[rs]);

		SumMin[x]=min(SumMin[ls],SumMin[rs]);

		Max[x]=max(Max[ls],Max[rs]);

		Min[x]=min(Min[ls],Min[rs]);

	}

	void change(int x,int l,int r,int L,int R,int v)

	{

		pd(x,l,r);

		if(l>=L&&r<=R)

		{

			SumMax[x]+=v;

			SumMin[x]+=v;

			Max[x]=max(Max[x],SumMax[x]);

			Min[x]=min(Min[x],SumMin[x]);

			lz[x]+=v;

			TagMax[x]=max(TagMax[x],lz[x]);

			TagMin[x]=min(TagMin[x],lz[x]);

			return ;

		}

		int mid=(l+r)>>1;

		if(L<=mid)change(ls,l,mid,L,R,v);

		if(R>mid) change(rs,mid+1,r,L,R,v);

		push_up(x);

	}

	int query(int x,int l,int r,int L,int R,int v)

	{

		if(l==r) return l;

		pd(x,l,r);

		int mid=(l+r)>>1;

		if(l<=mid&&Min[ls]<=v&&Max[ls]>=v) return query(ls,l,mid,L,R,v);

		else if(R>mid&&Min[rs]<=v&&Max[rs]>=v) return query(rs,mid+1,r,L,R,v);

		return INF;

	}

}

void Tr_change(int x)

{

	int f=val[s[x]];

	for(int i=0;i<poz[s[x]].size();i++)

	{

		if(poz[s[x]][i]>x) Seg::change(1,1,n,poz[s[x]][i-1],poz[s[x]][i]-1,f),f*=-1;;

	}

}

int main()

{

	freopen("ion.in","r",stdin);

	freopen("ion.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) s[i]=read(),poz[s[i]].push_back(i);

    for(int i=1;i<=n;i++) val[i]=read(),poz[i].push_back(n+1);

	Seg::Init();

	for(int i=1;i<=m;i++)

	{

		que[i].l=read();que[i].r=read();que[i].k=read();

		que[i].id=i;

	}

	sort(que+1,que+1+n,[=](Que a,Que b){return a.l<b.l;});

	int now=n;

	for(int i=m;i>=1;i--)

	{

		while(now>=que[i].l) Tr_change(now--);

		que[i].res=Seg::query(1,1,n,que[i].l,n,que[i].k);

		if(que[i].res>que[i].r) que[i].res=-1;

	}

	sort(que+1,que+1+n,[=](Que a,Que b){return a.id<b.id;});

	for(int i=1;i<=m;i++)

	{

		printf("%d\n",que[i].res);

	}

}

\(T3\)优秀

很巧妙的转化

首先,我们变化的是奇偶性不同的相邻同色两点,我们对奇数层染色之后,就变成了,两颜色不同的两点交换颜色,第一问答案就是,每个子树内部黑白差的绝对值,至于证明的话,我们要求的还是颜色翻转,每个点被交换奇数次

不是很会,待补

巴特西

5.26 NOI 模拟

最新文章

热门文章