BZOJ 4810 [Ynoi2017]由乃的玉米田

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4810

题意:给定一个非负整数序列a_{1},a_{2},\cdots,a_{n}m次询问:1.给定x,询问区间[l,r]内能否选出两个可重叠位置i,j,满足a_{i}-a_{j}=x;2.给定x,询问区间[l,r]内能否选出两个可重叠位置i,j,满足a_{i}+a_{j}=x;3.给定x,询问区间[l,r]内能否选出两个可重叠位置i,j,满足a_{i}*a_{j}=x;

思路:Claris课件上的题目(%%%),具体如下:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,m;
bitset<maxn>f,g;
int a[maxn],block[maxn],cnt[maxn];
bool ans[maxn];
struct Query{
    int l,r,op,x,k;
    bool operator<(const Query&b)const{
        if (block[l]==block[b.l]) return r<b.r;
        return block[l]<block[b.l];
    }
}Q[maxn];
void init(){}
int main(){
    read(n),read(m);
    for (int i=0;i<n;i++) read(a[i]);
    int sz=1;
    while (sz*sz<n) sz++;
    int j=0;
    for (int i=0;i<sz;i++){
        for (int k=min(j+sz,n);j<k;j++){
            block[j]=i;
        }
    }
    for (int i=0;i<m;i++){
        read(Q[i].op),read(Q[i].l),read(Q[i].r),read(Q[i].x);
        Q[i].l--,Q[i].r--;
        Q[i].k=i;
    }
    sort(Q,Q+m);
    int l=Q[0].l,r=l-1;
    for (int i=0;i<m;i++){
        const Query&q=Q[i];
        while (r<q.r) if (!cnt[a[++r]]++) f[a[r]]=g[n-a[r]]=1;
        while (l>q.l) if (!cnt[a[--l]]++) f[a[l]]=g[n-a[l]]=1;
        while (r>q.r) if (!--cnt[a[r--]]) f[a[r+1]]=g[n-a[r+1]]=0;
        while (l<q.l) if (!--cnt[a[l++]]) f[a[l-1]]=g[n-a[l-1]]=0;
        if (q.op==1){
            ans[q.k]=(f&(f<<q.x)).any();
        }
        else if (q.op==2){
            ans[q.k]=(f&(q.x>n?g<<(q.x-n):g>>(n-q.x))).any();//q.x<n相当于负数要往左移
        }
        else{
            for (int j=1;j*j<=q.x;j++){
                if (q.x%j==0 && cnt[j] && cnt[q.x/j]){
                    ans[q.k]=true;
                    break;
                }
            }
        }
    }
    for (int i=0;i<m;i++) puts(ans[i]?"yuno":"yumi");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注