Skip to content

Latest commit

 

History

History
301 lines (278 loc) · 7.34 KB

莫队算法.md

File metadata and controls

301 lines (278 loc) · 7.34 KB
Raw

莫队算法

BZOJ1878HH的项链(莫队算法)

莫队算法详解

莫队算法的模板题，洛谷上面的数据太强，主席树过了，莫队被卡掉了，BZOJ上面可以用莫队过。 莫队的思想就是加速了暴力的过程，分成了sqrt N个块。排序的时候如果在同一个块里面就按照r从小到大排序，不在同一个块里面就按照l从小到大排序 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],cnt[N];
int tim,ans[N];
int curl=1,curr=0,res=0;
inline int read()
{
    char ch=getchar();
    int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
inline void add(int pos)
{
    cnt[a[pos]]++;
    if(cnt[a[pos]]==1)
        res++;
}
inline void remove(int pos)
{
    cnt[a[pos]]--;
    if(cnt[a[pos]]==0)
        res--;
}
struct query
{
    int l,r,id;
} e[N];
bool cmp(query x,query y)
{
    if(x.l/tim==y.l/tim)//在同一个块
        return x.r<y.r;
    else
        return x.l<y.l;
}
int main()
{
    int n,m;
    n=read();
    for(int i=1; i<=n; i++)
        a[i]=read();
    m=read();
    tim=sqrt(m);
    for(int i=1; i<=m; i++)
    {
        e[i].l=read();
        e[i].r=read();
        e[i].id=i;
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        int l=e[i].l,r=e[i].r;
        while(curl<l) remove(curl++);
        while(curl>l) add(--curl);
        while(curr<r) add(++curr);
        while(curr>r) remove(curr--);
        ans[e[i].id]=res;
    }
    for(int i=1; i<=m; i++)
        printf("%d\n",ans[i]);
    return 0;
}
/*
10
1 2 3 1 1 2 1 2 3 1
1
1 2
*/

CF 340 E. XOR and Favorite Number

//CF#340 DIV2 E MO's Algorithm
//这题思路是首先求出前缀和，所以就会有sum[L-1]^sum[R]==k的公式，但是左边是两个都是不清楚值的，所以要转变一下，
//变为sum[R]^k==sum[L-1]，这样子我只要求出现在存在多少个sum[L-1]就知道有多少个可以和sum[k]异或为k的了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<20;
typedef long long LL;
LL Ans[maxn], ans;
int sum[maxn], num[maxn], pos[maxn], k, block;
int n, m;
struct Q{
    int l, r, id;
}q[maxn];
bool cmp(Q a, Q b){
    if(pos[a.l] == pos[b.l]) return a.r < b.r;
    return pos[a.l] < pos[b.l];
}

void add(int x){
    /*
    当前sum[L-1]^sum[R]=k，所以只要知道当前sum[L-1]有多少个
    即有多少个是在[L-1，R]区间异或是等于k的
    */
    ans += num[sum[x]^k];
    num[sum[x]]++; //增加当前前缀和个数
    //这里后来才加是为了防止增加为本身
}

void del(int x){
    num[sum[x]]--;//一个数有可能异或后还是本身，所以要先减去本身
    ans -= num[sum[x]^k];
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    block = sqrt(n);
    memset(num, 0, sizeof(num));
    sum[0] = 0;
    for(int i = 1; i <= n; i++){
        scanf("%d", &sum[i]);
        sum[i] ^= sum[i-1];
        pos[i] = (i - 1)/ block;
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int L = 1, R = 0;
    ans = 0;
    num[0] = 1;
    for(int i = 1; i <= m; i++){
        int id = q[i].id;
        while(R < q[i].r){
            R++;
            add(R);
        }
        while(L > q[i].l){
            L--;
            add(L-1);
        }
        while(R > q[i].r)
        {
            del(R);
            R--;
        }
        while(L < q[i].l)
        {
            del(L-1);
            L++;
        }
        Ans[id] = ans;
    }
    for(int i = 1; i <= m; i++){
        printf("%lld\n", Ans[i]);
    }
    return 0;
}

BZOJ 4810 莫队+BItset

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

解法：考虑一下要对区间信息查询，我们询问离线，跑个莫队，然后用bitset记录下哪些数出现了。然后区间a - b = x -> a = b + x , 同理 a + b = x -> a = x - b -> a = - (b - x)，所以对于差为x我们直接把第一个bitset右移然后和自己取交，同理对于和为x的情况，我们对之前的那个bitset取反，进行类似的操作就可以了，然后对于乘法的话 a*b = x我们直接枚举质因子暴力判断即可。

//BZOJ 4810

#include <bits/stdc++.h>
using namespace std;
//a - b = x -> a = b + x
//a + b = x -> a = -b + x -> a = - (b - x)
//a * b = x -> a = x / b
//O(n*n/32)

const int maxn = 100010;
const int offset = 100000;
bitset <maxn> pos;
bitset <maxn> neg;
int n, m, belong[maxn], block, a[maxn], ans[maxn], cnt[maxn];

struct node{
    int l, r, x, id, op;
    node(){}
    node(int l, int r, int x, int id, int op):l(l),r(r),x(x),id(id),op(op){}
    bool operator < (const node &rhs) const{
        if(belong[l] != belong[rhs.l]){
            return belong[l] < belong[rhs.l];
        }
        else{
            return r < rhs.r;
        }
    }
}q[maxn];

void input()
{
    scanf("%d%d", &n, &m);
    block = ceil(sqrt(n));
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        belong[i] = (i-1)/block+1;
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d%d", &q[i].op, &q[i].l, &q[i].r, &q[i].x);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
}

void work()
{
    int L = 1, R = 0;
    for(int i = 1; i <= m; i++)
    {
        int id = q[i].id;
        while(R < q[i].r){
            R++;
            cnt[a[R]]++;
            pos[a[R]] = 1;
            neg[offset - a[R]] = 1;
        }
        while(L > q[i].l){
            L--;
            cnt[a[L]]++;
            pos[a[L]] = 1;
            neg[offset - a[L]] = 1;
        }
        while(R > q[i].r){
            cnt[a[R]]--;
            if(cnt[a[R]] == 0) pos[a[R]] = 0;
            if(cnt[a[R]] == 0) neg[offset - a[R]] = 0;
            R--;
        }
        while(L < q[i].l){
            cnt[a[L]]--;
            if(cnt[a[L]] == 0) pos[a[L]] = 0;
            if(cnt[a[L]] == 0) neg[offset - a[L]] = 0;
            L++;
        }
        if(q[i].op == 1) //+
        {
            if(((pos>>q[i].x)&pos).any()){
                ans[id] = 1;
            }
            else{
                ans[id] = 0;
            }
        }
        else if(q[i].op == 2){//-
            if(((neg>>(offset-q[i].x))&pos).any()){
                ans[id] = 1;
            }
            else{
                ans[id] = 0;
            }
        }
        else{
            if(q[i].x == 0 && pos[0])
            {
                ans[id] = 1;
                continue;
            }
            for(int j = 1; j*j <= q[i].x; j++)
            {
                if(q[i].x % j == 0 && pos[j] == 1&& pos[q[i].x/j] == 1){
                    ans[id] = 1;
                    break;
                }
            }
        }
    }
}

void output()
{
    for(int i = 1; i <= m; i++){
        puts(ans[i]?"yuno":"yumi");
    }
}

int main()
{
    input();
    work();
    output();
}