首页 > 代码库 > bzoj4810

bzoj4810

2024-09-16 08:29:35   217人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=4810

问题就在于怎么快速查询
我们先用莫队转移，但是没办法快速地查询，那么我们就用bitset这个东西快速查询。
cnt是一个权值数组，记录每个数出现次数，a，c是两个bitset
减法：a[i]-a[j]=x那么我们把a<<x&a看是否出现1，有1就说明可以
加法：a[i]+a[j]=x我们发现没办法向上面那个样子直接搞，但是我们可以把加法转换成减法。我们化简一下式子:a[i]=x-c+c-a[j] c是一个a中最大的数
那么我们就搞出了减法a[i]=(x-c)+c-a[j] a<<(x-c)&c
乘法：枚举每个因数是否存在。
技术分享 
#include<bits/stdc++.h>
using namespace std;
const int N = 200010, MAX = 100001;
struct query {
    int type, l, r, x, block, id; 
} q[N];
bitset<N> a, c;
int n, m;
int cnt[N], x[N], ans[N];
inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); }
    while(c >= ‘0‘ && c <= ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); }
    return x * f;
}
bool cp(query i, query j) { return i.block == j.block ? i.r < j.r : i.block < j.block; } 
void add(int pos)
{
    if(!cnt[x[pos]]) 
    {
        a[x[pos]] = 1;
        c[MAX - x[pos]] = 1;
    }
    ++cnt[x[pos]];
}
void del(int pos)
{
    if(cnt[x[pos]] == 1) 
    {
        a[x[pos]] = 0;
        c[MAX - x[pos]] = 0;
    }
    --cnt[x[pos]];
}
int query(int type, int x)
{
    if(type == 1) // 减法 如果a >> x & a == 1 那么就是有 
        return (a & (a << x)).any();
    if(type == 2)
        return (c & (a << (MAX - x))).any(); 
    for(int i = 1; i * i <= x; ++i) if(x % i == 0 && cnt[i] && cnt[x / i]) return 1;
    return 0;
}
void solve()
{
    int l = 1, r = 1; add(1);
    for(int i = 1; i <= m; ++i)
    {
        while(l < q[i].l) {
            del(l); ++l;
        }
        while(l > q[i].l) {
            --l; add(l); 
        }
        while(r < q[i].r) {
            ++r; add(r);
        }
        while(r > q[i].r) {
            del(r); --r;
        }
        ans[q[i].id] = query(q[i].type, q[i].x);
    }
    for(int i = 1; i <= m; ++i) puts(ans[i] == 1 ? "yuno" : "yumi");
}
int main()
{
    n = read(); m =read();
    for(int i = 1; i <= n; ++i) x[i] = read();
    int block = sqrt(n);
    for(int i = 1; i <= m; ++i)
    {
        q[i].type = read(); q[i].l = read(); q[i].r = read(); q[i].x = read();
        q[i].block = (q[i].l - 1) / block; q[i].id = i;
    }
    sort(q + 1, q + m + 1, cp);
    solve();
    return 0;
}
View Code

 

 

bzoj4810


联系
我们