为什么RE啊
查看原帖
为什么RE啊
999274
CNS_5t0_0r2楼主2025/1/20 14:14
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,M = 1e5 + 9,SqrtN = 339,V = 1e5 + 9,SqrtV = 339;
int n,m;
struct block{
	int l,r;
} b[SqrtN];
int belong[N];
int block_len,block_cnt;
void build_block(){
	block_len = block_cnt = (int)sqrt(n);
	for(int i = 1;i <= block_cnt;i++){
		b[i].l = b[i - 1].r + 1;
		b[i].r = i * block_len;
	}
	b[block_cnt].r = n;
	for(int i = 1;i <= block_cnt;i++)
		for(int j = b[i].l;j <= b[i].r;j++)
			belong[j] = i;
}
struct queries{
	int typ,l,r,x;
	int id;
} q1[M];
vector<queries> q2[SqrtV];
int cnt1,cnt2;
int a[N],max_a;
int cnt[V];
bitset<V> vis1,vis2;
int pre1[V],pre2[N],last;
bool ans[M];
int lres = 1,rres;
bool cmp(queries q1,queries q2){
    return belong[q1.l] == belong[q2.l] ? belong[q1.r] < belong[q2.r] : belong[q1.l] < belong[q2.l];
}
void add(int x){
	cnt[x]++;
	if(cnt[x] == 1)
		vis1[x] = vis2[max_a - x] = true;
}
void del(int x){
	cnt[x]--;
	if(cnt[x] == 0)
		vis1[x] = vis2[max_a - x] = false;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	build_block();
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		max_a = max(max_a,a[i]);
	}
	for(int i = 1;i <= m;i++){
		int typ,l,r,x;
		cin >> typ >> l >> r >> x;
		if(typ != 3 || x >= sqrt(max_a))
			q1[++cnt1] = (queries){typ,l,r,x,i};
		else
			q2[x].push_back((queries){typ,l,r,x,i});
	}
	sort(q1 + 1,q1 + cnt1 + 1,cmp);
    for(int i = 1;i <= cnt1;i++){
        int typ = q1[i].typ,L = q1[i].l,R = q1[i].r,x = q1[i].x;
        while(lres > L)
            add(a[--lres]);
        while(rres < R)
            add(a[++rres]);
        while(lres < L)
            del(a[lres++]);
        while(rres > R)
            del(a[rres--]);
        if(typ == 1){
        	if((vis1 & (vis1 >> x)).any())
        		ans[q1[i].id] = true;
		}
		else if(typ == 2){
			if((vis1 & (vis2 >> (max_a - x))).any())
				ans[q1[i].id] = true;
		}
		else if(typ == 3){
			for(int j = 1;j * j <= x;j++){
				if(vis1[j] && vis1[x / j] && x % j == 0){
					ans[q1[i].id] = true;
					break;
				}
			}
		}
		else if(typ == 4){
			for(int j = 1;x * j <= max_a;j++){
				if(vis1[j] && vis1[x * j]){
					ans[q1[i].id] = true;
					break;
				}
			}
		}
    }
    for(int x = 1;x < sqrt(max_a);x++){
    	int siz = q2[x].size();
    	if(!siz)
    		continue;
    	for(int i = 1;i <= n;i++){
    		int y = a[i];
    		pre1[y] = i;
    		if(x * y <= max_a)
    			last = max(last,pre1[x * y]);
    		if(y % x == 0)
    			last = max(last,pre1[y / x]);
    		pre2[i] = last;
		}
    	for(int i = 0;i < siz;i++)
    		ans[q2[x][i].id] = (q2[x][i].l <= pre2[q2[x][i].r]);
    	memset(pre1,0,sizeof pre1);
    	memset(pre2,0,sizeof pre2);
    	last = 0;
	}
	for(int i = 1;i <= m;i++)
		cout << (ans[i] ? "yuno" : "yumi") << '\n';
	return 0;
}
2025/1/20 14:14
加载中...