题目链接 : [Ynoi2017] 由乃的玉米田
弱化版 : 小清新人渣的本愿
这两道题都是看会不会用bitset，bitset大胜利
-
减操作 : 用一个bitset \(vis1\) 记录一个数是否出现，如果有就是\((vis1\And(vis>>x)).count()\ge 1\)，其实就是看是否有数\(a\)和数\(a+x\)同时出现
-
加操作 : 同减操作，但是要转化一下，就是\(a+b=x\Leftrightarrow a-(100000-b)=x-100000\)。记录一个相反的bitset \(vis2\)，然后就是判断是否 \((vis1\And(vis2>>(100000-x))).count()\ge 1\)(因为vis2是相反的bitset，所以不是右移\(x-100000\)位而是\(100000-x\)位)
-
乘操作 : \(O(\sqrt x)\)暴力跑即可
-
除操作 : 根号分治
- \(x\ge \sqrt{100000}\)的暴力跑，复杂度是正确的\(O(\sqrt{n})\)
- 对于\(x< \sqrt{100000}\)的，将其特殊处理
定义两个数组 : \(pre_x\)表示\(x\)上一次(包括当前位置，因为一个位置可以重复选两次)出现的位置，\(lastpos_i\)表示到\(i\)时最后一个合法点对\((i,j)(i\le j)\)中\(i\)的位置。
然后将所有\(op = 4 \And x<\sqrt{100000}\)的单独记录出来，单独处理。
枚举\(x\)，然后用一个指针\(i\; O(n)\)扫一遍\(a\)，假设当前扫到的位置为\(i\)，记录当前最后一个合法点对\((i,j)\)中\(i\)的位置为\(res\)，依次执行以下操作 :
- 用\(i\)替换\(pre_{a_i}\)
- 如果\(a_i\times x\le 100000\)，那么\(res = \max(res,pre_{a_i\times x})\)
- 如果\(a_i\bmod x = 0\)，那么\(res = \max(res,pre_{\frac{a_i}{x}})\)
最后统计一下答案，就是比较\(l\)与\(lastpos_r\)的大小关系，如果\(l>lastpos_r\)则无解。
预处理的复杂度是\(O(n\sqrt n)\)，莫队的复杂度是\(O(n(\sqrt{n} + \frac{n}{w}))\)的，可以通过，无需卡常
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10,M = 330;
int n,m,a[N],L[M],R[M],pos[N],len,ct[N];
struct node{int op,l,r,x,id;}q[N];int cnt = 0;
bool ans[N];
struct Node{int l,r,id;};
vector<Node> p[M];
int pre[N],lastpos[N];
inline void solve(){
cin>>n>>m;
for(int i = 1;i <= n; ++i) cin>>a[i];
for(int i = 1,op,l,r,x;i <= m; ++i){
cin>>op>>l>>r>>x;
if(op == 4 && x < M) p[x].emplace_back((Node){l,r,i});
else q[++cnt] = {op,l,r,x,i};
}
for(auto i:p[1]) ans[i.id] = true;
for(int now = 2;now < M; ++now){
if(p[now].empty()) continue;
int res = 0;
memset(lastpos,0,sizeof lastpos);
memset(pre,0,sizeof pre);
for(int i = 1;i <= n; ++i){
int y = a[i];
pre[y] = i;
if(now * y <= 100000) res = max(res,pre[now*y]);
if(y % now == 0) res = max(res,pre[y/now]);
lastpos[i] = res;
}
for(auto i : p[now]) ans[i.id] = (i.l <= lastpos[i.r]);
}
len = sqrt(n);
for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i * len;
if(R[len] < n) len ++, L[len] = R[len - 1] + 1,R[len] = n;
for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
sort(q+1,q+1+cnt,[](node x,node y){return (pos[x.l]==pos[y.l]?(pos[x.l]&1?x.r<y.r:x.r>y.r):x.l<y.l);});
bitset<N> vis1,vis2;
int left = 1,right = 0;
auto add = [&](int x) -> void{
if(!ct[x])vis1[x] = vis2[100000 - x] = true;
ct[x]++;
};
auto del = [&](int x) -> void{
ct[x]--;
if(!ct[x]) vis1[x] = vis2[100000 - x] = false;
};
for(int i = 1;i <= cnt; ++i){
int l = q[i].l,r = q[i].r,op = q[i].op,x = q[i].x;
while(left > l) add(a[--left]);
while(right < r) add(a[++right]);
while(left < l) del(a[left++]);
while(right > r) del(a[right--]);
if(op == 1) ans[q[i].id] = (vis1&(vis1>>x)).count();
if(op == 2) ans[q[i].id] = (vis1&(vis2>>(100000-x))).count();
if(op == 3){
int k = sqrt(x);
for(int j = 1;j <= k; ++j){
if(x % j == 0 && vis1[j] && vis1[x/j]){ans[q[i].id] = true;break;}
}
}
if(op == 4){
for(int j = 1;j <= 100000/x; ++j) if(vis1[j] && vis1[j*x]){ans[q[i].id] = true;break;}
}
}
for(int i = 1;i <= m; ++i) cout<<(ans[i]?"yuno\n":"yumi\n");
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}