A simple Blog for wyx I've been down the bottle hoping.
4810: [Ynoi2017]由乃的玉米田 莫队 bitset压位
发表于: | 分类: Oi | 评论:0 | 阅读:55

首先我没有想到任何一种数据结构能维护这玩意……

然后我们就可以莫队了【大雾

用 $bitset$ 把桶中是否有元素的状态压出来

显然第一个操作对应着一个右移取并

第二个操作对应着翻转右移取并

等等翻转是什么鬼……没听说过啊……【我被这个卡了十分钟

所以我们可以维护一个正着的 $bitset$ 和一个反着的 $bitset$ 23333333333333

第三个操作显然只会遍历不超过 $log$ 次,复杂度是支持乱搞的 ……

然后我们来讲几个非常奇怪的错误吧……

  • 没有保证区间非空……

  • 第二个操作没考虑到 0

  • 数据范围断句问题【大雾

#include <cmath>
#include <vector>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
const int Max = 100000;
const int N = 100000+5;
bitset <Max+5> f, g;
int a[N], T[N], ans[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct data{
    int opt,x, y, bl, id, val;
    bool operator < (const data &z) const {
        return bl ^ z.bl ? bl < z.bl : y > z.y;
    }
} b[N];

inline void add(int x) {
    T[x] ++;
    f[x] = 1;
    g[Max-x] = 1;
}

inline void del(int x) {
    T[x] --;
    if(T[x] == 0) {
        f[x] = 0;
        g[Max-x] = 0;
    }
}

vector <int> V[Max+5];

int main() {
//  freopen("tt.in","r",stdin);
    int n = read() , m = read();
    for(int i=1;i<=n;++i) a[i] = read();
    int sz = (int)sqrt(n)+1;
    for(int i=1;i<=m;++i) {
        b[i].opt = read();
        b[i].x = read(), b[i].y = read(), b[i].bl = (b[i].x -1)/ sz + 1, b[i].id = i;
        b[i].val = read();
    }
    for(int i=1;i<=Max;++i) {
        for(int j=i;j<=Max;j+=i) {
            V[j].pb(i);
        }
    }
    sort(b+1,b+m+1);
    add(0);
    int l = 0, r = 0;
    for(int i=1;i<=m;++i) {
        while(l > b[i].x) add(a[--l]);
        while(r < b[i].y) add(a[++r]);
        while(l < b[i].x) del(a[l++]);
        while(r > b[i].y) del(a[r--]);
        if(b[i].opt == 1) ans[b[i].id] = ((f>>(b[i].val))&f).count();
        else if(b[i].opt == 2) ans[b[i].id] = ((g>>(Max-b[i].val))&f).count();
        else if(b[i].opt == 3) {
            for(int j=0;j<V[b[i].val].size();++j) {
                if(f[V[b[i].val][j]] && f[b[i].val/V[b[i].val][j]]) ans[b[i].id] = 1;
            }
            if(b[i].val == 0 && f[0]) ans[b[i].id] = 1;
        }
    }
    for(int i=1;i<=m;++i) 
        if(ans[i]) puts("yuno");
        else puts("yumi");
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP