首页 > 代码库 > BZOJ4810 [Ynoi2017]由乃的玉米田
BZOJ4810 [Ynoi2017]由乃的玉米田
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ4810
正解：$bitset$+莫队算法
解题报告：
考虑直接上$bitset$会$MLE$，我们用莫队来优化空间，不用每个点都开一个。
维护一个$cnt$数组，表示每种值的出现次数，那么我可以用$bitset$维护每种权值是否出现过。
考虑乘法操作的话，直接利用$cnt$数组，每次暴枚所有因子，$check$一下就好了；
对于减法操作，相当于是查询是否存在$i$,$j$满足$a[i]-a[j]=x$的形式，那么把$bitset$右移$x$位与原来的&一下看新的二进制数是否为$0$（用$bitset$自带的$count$就好了）；
加法类似，不过需要维护的是$a[i]+a[j]=x$的形式，那么我用$c$（$c$是所有数中的最大值）去减$a[j]$，即变成$a[i]=(c-a[j])+x-c$的形式，另外维护一个$bitset$，右移$(c-x)$位查询就好了。所以总复杂度就是$O(n\sqrt{n}+\frac{n^2}{60})$。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <bitset>
#include <queue>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
int n,m,ans[MAXN],block,a[MAXN],b[MAXN],c,cnt[MAXN<<2];
bitset<100011>f,g,h;
struct ask{ int l,r,bel,id,x,type; }q[MAXN];
inline bool cmp(ask q,ask qq){ if(q.bel==qq.bel) return q.r<qq.r; return q.bel<qq.bel; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void add(int x){
cnt[a[x]]++;
if(cnt[a[x]]==1) {
f[a[x]]=1;
g[b[x]]=1;
}
}
inline void del(int x){
cnt[a[x]]--;
if(cnt[a[x]]==0) {
f[a[x]]=0;
g[b[x]]=0;
}
}
inline bool query(ask tmp){
int now;
if(tmp.type==3) {//a[i]*a[j]=x
now=sqrt(tmp.x+1);
for(int i=1;i<=now;i++) {
if(tmp.x%i==0) {
if(cnt[i]>0 && cnt[tmp.x/i]>0)
return true;
}
}
}
else if(tmp.type==2) {//a[i]+a[j]=x
h=g;
h>>=(c-tmp.x);
h&=f;
if(h.count()) return true;
}
else {//a[i]-a[j]=x
h=f;
h>>=tmp.x;
h&=f;
if(h.count()) return true;
}
return false;
}
inline void work(){
n=getint(); m=getint();block=2*sqrt(m);
c=100002; for(int i=1;i<=n;i++) a[i]=getint(),b[i]=c-a[i];
for(int i=1;i<=m;i++) { q[i].type=getint(); q[i].l=getint(); q[i].r=getint(); q[i].x=getint(); q[i].id=i; q[i].bel=(q[i].l-1)/block+1; }
sort(q+1,q+m+1,cmp); int l=q[1].l,r=q[1].r;
for(int i=l;i<=r;i++) add(i)/*!!!*/;
ans[q[1].id]=query(q[1]);
for(int i=2;i<=m;i++) {
while(r<q[i].r) r++,add(r);
while(l>q[i].l) l--,add(l);
while(r>q[i].r) del(r),r--;
while(l<q[i].l) del(l),l++;
ans[q[i].id]=query(q[i]);
}
for(int i=1;i<=m;i++)
if(ans[i]) puts("yuno");
else puts("yumi");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("4810.in","r",stdin);
freopen("4810.out","w",stdout);
#endif
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
BZOJ4810 [Ynoi2017]由乃的玉米田
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。