【题解】洛谷P3674： 小清新人渣的本愿

P3674 小清新人渣的本愿

自己想出来了，好耶！！其实和兔子洞那题差不多，标记哪些数区间中出现了，因为 bitset 就相当于状压，也是支持位运算的，所以减法相当于右移 \(x\) 位后与运算，如果有交说明可以得到 \(x\)，加法就要额外维护 \(g=f_{N-i}\)，查询时直接查找 \(f\) 与 \(g\) 右移 \(N-x\) 位是否有交，乘法更简单直接分解因数就可以，这样的复杂度位 \(O(m(\sqrt{n}+\frac{n}{w}))\)。

\(a+b=x,b=x-a\)，所以维护加要进行减操作。

其实不随机的话可以是 \(O(\frac{n^2}{w}\sqrt{n})\)，这样是乘法拉满的情况，但是数据范围没这么出就不管了。

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
#define pir pair<int,int>
const int N=1e5+10,M=25005;
const int mod=1e8;
using namespace std;

int n,m;
int a[N];
int of[N],len;
bitset<N> f,g;
int cnt[N];

struct ss{
	int l,r,op,id,x;
}q[N];

void add(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]==1){
		f[a[x]]=1;
		g[N-a[x]]=1;
	}
}

void del(int x){
	if(cnt[a[x]]==1){
		f[a[x]]=0;
		g[N-a[x]]=0;
	}
	cnt[a[x]]--;
}

int ans[N];

bool cmp(ss g,ss h){
	return (of[g.l]^of[h.l])?of[g.l]<of[h.l]:(of[g.l]&1)?of[g.r]<of[h.r]:of[g.r]>of[h.r];
}

signed main(){
//	freopen("xp1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    
    cin>>n>>m;
	
	len=sqrt(n);
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
    
    for(int i=1;i<=m;i++){
    	int op,l,r,x;
    	cin>>op>>l>>r>>x;
    	q[i].id=i;q[i].l=l;q[i].r=r;q[i].op=op;q[i].x=x;
    	of[i]=(i-1)/len+1;
	}
    
    sort(q+1,q+m+1,cmp); 
    
    int l=1,r=0;
    
    for(int i=1;i<=m;i++){
    	int ql=q[i].l,qr=q[i].r,id=q[i].id,x=q[i].x,op=q[i].op;
		while(l>ql) add(--l); 
    	while(r<qr) add(++r);
    	while(l<ql) del(l++);
    	while(r>qr) del(r--);
    	
    	int flag=0;
    	
    	
    	
    	if(op==1){
    		if((f&(f>>x)).any()){
    			flag=1;
			}
		}
		else if(op==2){
			if((f&(g>>(N-x))).any()){
				flag=1;
			}
		}
		else{
			for(int j=1;j*j<=x;j++){
				if(x%j==0&&f[j]==1){
					if(f[x/j]==1){
						flag=1;
						break;
					}
				}
			}
		}
		
		ans[id]=flag;
	}
	
	for(int i=1;i<=m;i++){
		if(ans[i]){
			cout<<"hana";
		}
		else{
			cout<<"bi";
		}
		cout<<"\n";
	}
	return 0;
}