BZOJ 4722: 由乃

给一个长为 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

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

日期： 2016-11-27

标签： BZOJ 乱搞 暴力 倍增 树状数组

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/83/ 查看。