?

【題目鏈接】?http://www.lydsy.com/JudgeOnline/problem.php?id=4810

?

【題目大意】

　　給出一個數列，有三種區間查詢，
　　分別查詢區間是否存在兩個數乘積為x，是否存在兩個數和為x，以及是否存在兩個數差為x，

?

【題解】

　　我們對于詢問進行莫隊處理，保存當前區間的權值數組，記為F，
　　同時保存權值數組的反向數組G
　　那么存在差為x的情況只要存在一組F[i]&F[i-x]=1即可
　　存在和為x的情況只要存在一組F[i]&G[M-x+i]即可。
　　對于乘積為x的情況，我們枚舉x的約數，判斷F[i]&F[x/i]是否存在。
　　復雜度O(nsqrt(n)+nm/w)

?

【代碼】

#include <cstdio> #include <algorithm> #include <bitset> #include <cmath> using namespace std; const int N=100010,M=100000; int limit,n,m,pos[N],a[N],ans[N],cnt[N]; bitset<N> F,G; struct Q{int l,r,x,id,op;friend bool operator < (const Q &a,const Q &b){return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r);} }ask[M]; int read(int &x){int f=1;char ch=getchar();x=0;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f; } int main(){read(n); read(m);limit=(int)sqrt(n+0.5);for(int i=1;i<=n;i++)read(a[i]),pos[i]=(i-1)/limit+1;for(int i=1;i<=m;i++)read(ask[i].op),read(ask[i].l),read(ask[i].r),read(ask[i].x),ask[i].id=i;sort(ask+1,ask+m+1);for(int i=1,l=1,r=0;i<=m;i++){for(;r<ask[i].r;r++)cnt[a[r+1]]++,F.set(a[r+1]),G.set(M-a[r+1]);for(;l>ask[i].l;l--)cnt[a[l-1]]++,F.set(a[l-1]),G.set(M-a[l-1]);for(;l<ask[i].l;l++){cnt[a[l]]--;if(!cnt[a[l]])F.reset(a[l]),G.reset(M-a[l]);}for(;r>ask[i].r;r--){cnt[a[r]]--;if(!cnt[a[r]])F.reset(a[r]),G.reset(M-a[r]);}if(ask[i].op==1){if((F&(F>>ask[i].x)).any())ans[ask[i].id]=1;}else if(ask[i].op==2){if((F&(G>>(M-ask[i].x))).any())ans[ask[i].id]=1;}else{for(int j=1;j*j<=ask[i].x;j++)if(ask[i].x%j==0){if(F[j]&F[ask[i].x/j]){ans[ask[i].id]=1;break;}}}}for(int i=1;i<=m;i++)puts(ans[i]?"yuno":"yumi");return 0; }

轉載于:https://www.cnblogs.com/forever97/p/bzoj4810.html

總結

以上是生活随笔為你收集整理的BZOJ 4810 [Ynoi2017]由乃的玉米田（莫队+bitset）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。