bzoj - 4810

Posted by WildCow on March 15, 2018

[Ynoi2017]由乃的玉米田

Time Limit: 30000MS
Memory Limit: 256 MB

Description

由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。 由乃认为玉米田不美,所以她决定出个数据结构题

这个题是这样的:
给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1 ,2,3选出的这两个数可以是同一个位置的数 avater

Input

第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作,l,r表示操作的区间,x表示这次操作的x
定义c为每次的x和ai中的最大值,ai >= 0,每次的x>=2,n,m,c <= 100000

Output

对于每个询问,如果可以,输出yuno,否则输出yumi

Sample Input

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

Sample Output

yuno
yumi
yuno
yuno
yumi


这题感觉就是一个乱搞啊哎呦
感觉思维要改一改了
有一点见到题就怕

直接介绍一下bitset吧
bitset Bit
尖括号里不是数据类型
而是大小
这样一来可以理解成生命了一个长度为 N 的 bool 型数组
但是 bitset 有空间优化
是 char 的八分之一
然后可以把声明的 Bit当作数组来操作

Bit[3] = 1 或者 Bit[3] = 0什么的都是没问题

然后还可以把 Bit 当做一个二进制数
即我们可以直接对 Bit 进行二进制操作
&, |, ^, «, » 都是可以的= =!

总之就是一个超级牛逼的状压= =!

然后回到这一道题本身
对于一个序列
多次询问
每次询问[l, r]内能不能找到两个数a, b(可以相同)
使a - b = x 或者 a + b = x 或者 a * b = x

由于 x 最大也是 1e5

我们先来看 a * b = x
用一个权值数组维护[l, r]区间内每个数字是否存在
然后用类似于判断质数的方法
对于 x 开根号然后 for 循环直接找就好了

然后是 a - b = x
我们通过 bitset 建立一个权值数组维护[l, r]内每个数字是否存在
然后牛逼的来了! 我们把那个 bitset 右移 x, 不就等价于把那个权值数组中的每个数字减去 x 后的权值数组么!!!
妙啊
把右移后的权值 bitset 和原来的 bitset & 一下,如果不是 0,就说明有一位一样,就说明有解

a + b = x
有一个很妙的转换
设一个大值 c
a + b = x 等价于 a = (c − b) + x − c
维护一下 c - b 的权值 bitset 再右移 (c - x)
就变成和减法一样了!

最后用莫队维护权值数组或者权值 bitset 的内容


#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100010;
 
struct Quary
{
    int opt;
    int l;
    int r;
    int x;
    int num;
};
 
Quary quary[N];
bitset<N> a, b, t;
int ma[N];
int mb[N];
int pos[N];
int ans[N];
int cnt[N];
int block;
int n, m;
int l, r;
 
bool cmp(Quary a, Quary b)
{
    if(pos[a.l] == pos[b.l]){
        return a.r < b.r;
    }
    else{
        return pos[a.l] < pos[b.l];
    }
}
 
void add(int x)
{
    cnt[ma[x]] ++;
    if(cnt[ma[x]] == 1){
        a[ma[x]] = 1;
        b[mb[x]] = 1;
    }
}
 
void del(int x)
{
    cnt[ma[x]] --;
    if(!cnt[ma[x]]){
        a[ma[x]] = 0;
        b[mb[x]] = 0;
    }
}
 
bool ask(Quary node)
{
    int li;
 
    if(node.opt == 3){      /// *
        li = sqrt(node.x) + 1;
        for(int i = 1; i <= li; i ++){
            if(node.x % i == 0){
                if(cnt[i] > 0 && cnt[node.x / i] > 0){
                    return true;
                }
            }
        }
    }
    else if(node.opt == 2){ /// +
        t = b;
        t >>= (N - node.x);
        t &= a;
        if(t.count()){
            return true;
        }
    }
    else if(node.opt == 1){ /// -
        t = a;
        t >>= node.x;
        t &= a;
        if(t.count()){
            return true;
        }
    }
 
    return false;
}
 
int main(int argc, char const *argv[])
{
    while(scanf("%d%d", &n, &m) == 2){
        memset(cnt, 0, sizeof(cnt));
        block = sqrt(n);
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
            mb[i] = N - ma[i];
            pos[i] = i / block;
        }
        for(int i = 1; i <= m; i ++){
            int num, l, r, cnt;
 
            scanf("%d%d%d%d", &quary[i].opt, &quary[i].l, &quary[i].r, &quary[i].x);
            quary[i].num = i;
        }
        sort(quary + 1, quary + m + 1, cmp);
        l = 1;
        r = 0;
        for(int i = 1; i <= m; i ++){
            while(l < quary[i].l){
                del(l);
                l ++;
            }
            while(l > quary[i].l){
                l --;
                add(l);
            }
            while(r < quary[i].r){
                r ++;
                add(r);
            }
            while(r > quary[i].r){
                del(r);
                r --;
            }
            ans[quary[i].num] = ask(quary[i]);
        }
        for(int i=1;i<=m;i++){
            if(ans[i]){
                printf("yuno\n");
            }
            else{
                printf("yumi\n");
            }
        }
    }
 
 
    return 0;
}