BZOJ 4722: 由乃

###Description
给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。
操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足：
1.X和Y没有交集
2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献
相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki
操作2：修改一个区间l,r之间的数，使得所有l <= i <= r，a[i] = a[i] \* a[i] \* a[i] % v ，即区间立方

###Input
第一行三个数n , m , v，意义如题所述
之后一行n个数，表示序列a
之后m行每行三个数opt , l , r，表示操作类型是1还是2，操作的区间是[l , r]

###Output
m行，每行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合

###Sample Input
20 20 152
3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58
2 1 17
2 6 12
1 1 12
2 3 5
2 11 11
2 7 19
2 6 15
1 5 12
1 1 9
1 10 19
2 3 19
2 6 20
2 1 13
2 1 15
2 1 9
1 1 1
2 1 7
2 7 19
2 6 19
2 3 6

###Sample Output
Yuno
Yuno
Yuno
Yuno
Yuki

###HINT
总算在bzoj上出题了呀
这下可以安心退役了~
总共有10组数据
对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度

###Solution
当某个区间长度大于13一定有解，小于13 bitset乱搞
立方操作树状数组区间加，取数时倍增

###Code
```c++
#include<bits/stdc++.h>
int n,m,v,u,s[100001],p[100001],N[1000][17],i,j,O,l,r,t,T;
main()
{
	scanf("%d%d%d",&n,&m,&v);
	while((1<<u)<=v)u++;
	for(;i<v;i++)
		N[i][0]=1ll*i*i*i%v;
	for(i=1;i<=n;i++)
		scanf("%d",s+i);
	for(i=0;i<16;i++)
		for(j=0;j<v;j++)
			N[j][i+1]=N[N[j][i]][i];
	while(m--)
	{
		scanf("%d%d%d",&O,&l,&r);
		if(O&1)
		{
			if(r-l>=u)puts("Yuno");
			else
			{
				std::bitset<10360> x(1);
				for(i=l;i<=r;i++)
				{
					t=0,T=s[i];
					for(j=i;j;j^=j&-j)t+=p[j];
					for(j=0;j<17;j++)if((t>>j)&1)T=N[T][j];
					if((x&(x<<T+1)).any())
					{
						puts("Yuno");
						goto Y;
					}
					x|=x<<T+1;
				}
				puts("Yuki");
				Y:;
			}
		}
		else
		{
			for(i=l;i<=n;i+=i&-i)p[i]++;
			for(i=r+1;i<=n;i+=i&-i)p[i]--;
		}
	}
}
```

最新文章

最近回复

分类

归档

其它