[洛谷P3674]小清新人渣的本愿

news/2025/2/12 18:07:05

题目传送门

这道题是一道莫队题。对于每一种问法,就是查询对应的数是否在当前的区间内。

设$b[i]$表示莫队当前区间中有没有$i$这个数。

对于第一问“是否可以选出两个数它们的差为x”,也就是判断当$i-j=x$时是否存在$b[i],b[j]=1$。变形一下发现$i=j+x$,就成了$b[j],b[j+x]=1$。

我们用一个$\text{bitset}$操作,判断这一问就变成了判断$(b\ \text{&&}\ (b<<x))$是否为真。

对于第二问就是当$i+j=x$时,是否存在$b[i],b[j]=1$。变形下发现

$$i=x-j$$

$$i+N=x+N-j$$

$$i-(x-N)=(N-j)$$

再开个$b'=\text{bitset}$维护$N-j$,当$j$出现后,$N-j$为$1$。答案即为$((b<<(N-x))\ \text{&&}\ b')$。

对于第三问发现枚举因数直接判断复杂度不大,暴力解决。

一开始计算复杂度发现是$O(m\sqrt{n}+mn)$,$mn$复杂度是由$\text{bitset}$的与运算贡献的,会炸的。

但后来了解到$\text{bitset}$的复杂度要除掉一个$\omega$,$\omega$为计算机位数,一般为$32/64$。

所以就能过了。

下面的代码的写法可能与上面有细微差别,但与上面是等效的。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define re register
 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
 7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
 8 #define maxx(a, b) a = max(a, b);
 9 #define minn(a, b) a = min(a, b);
10 #define LL long long
11 #define INF (1 << 30)
12 
13 inline int read() {
14     int w = 0, f = 1; char c = getchar();
15     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
16     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
17     return w * f;
18 }
19 
20 const int maxn = 1e5 + 5;
21 
22 bitset<maxn> S1, S2;
23 
24 struct Query {
25     int l, r, id, pos, opt, x;
26 } q[maxn];
27 bool cmp(Query a, Query b) { return a.pos < b.pos || a.pos == b.pos && a.r < b.r; }
28 
29 int n, m, a[maxn], ans, b[maxn], size, cnt[maxn];
30 
31 void del(int x) { cnt[x]--; if (!cnt[x]) S1[x] = S2[n-x] = 0; }
32 void ins(int x) { if (!cnt[x]) S1[x] = S2[n-x] = 1; cnt[x]++; }
33 
34 int main() {
35     n = read(), m = read();
36     size = sqrt(n);
37     rep(i, 1, n) a[i] = read();
38     rep(i, 1, m) q[i].opt = read(), q[i].l = read(), q[i].r = read(), q[i].x = read(), q[i].id = i, q[i].pos = (q[i].l + size - 1) / size;
39     sort(q+1, q+m+1, cmp);
40     int pl = 1, pr = 0;
41     rep(i, 1, m) {
42         while (pl < q[i].l) del(a[pl]), pl++;
43         while (pl > q[i].l) pl--, ins(a[pl]);
44         while (pr < q[i].r) pr++, ins(a[pr]);
45         while (pr > q[i].r) del(a[pr]), pr--;
46         if (q[i].opt == 1) {
47             b[q[i].id] = ((S1 << q[i].x) & S1).any() ? 1 : 0;
48         }
49         else if (q[i].opt == 2) {
50             b[q[i].id] = ((S2 >> (n-q[i].x)) & S1).any() ? 1 : 0;
51         }
52         else if (q[i].opt == 3) {
53             b[q[i].id] = 0;
54             rep(x, 1, sqrt(q[i].x))
55                 if (!(q[i].x % x) && S1[x] && S1[q[i].x/x]) { b[q[i].id] = 1; break; }
56         }
57     }
58     rep(i, 1, m) printf("%s\n", b[i] ? "hana" : "bi");
59     return 0;
60 }

 

转载于:https://www.cnblogs.com/ac-evil/p/10372191.html


https://dhexx.cn/news/show-1546584.html

相关文章

nginx状态模块详解及实战

nginx status介绍nginx软件的功能模块中有一个ngx_http_stub_status_module模块&#xff0c;这个模块的主要功能是记录nginx的基本访问状态信息&#xff0c;让使用者了解nginx的工作状态&#xff0c;例如&#xff1a;连接数等信息。要想使用状态模块&#xff0c;在编译nginx时必…

windows下的host文件在哪里,有什么作用?

在Window系统中有个Hosts文件&#xff08;没有后缀名&#xff09;&#xff0c;在Windows98系统下该文件在Windows目录&#xff0c;在Windows2000/XP系统中位于C:\Winnt\System32\Drivers\Etc 目录中。WIN7(C:\Windows\System32\drivers\etc)该文件其实是一个纯文本的文件&#…

Selenium Grid简介与安装

一、序&#xff1a; 很多敏捷团队已经使用了Selenium和Watir等 工具进行验收测试或用户接口测试。这些工具通过驱动Web浏览器的方式反映用户体验&#xff0c;并且为测试那些使用DHTML和Ajax构建的动态接口提供强力支 持。然而&#xff0c;随着更多的团队采纳类似的工具&#xf…

JavaScript隐式类型转换

基本数据类型 ECMAScript 一共定义了七种 build-in types&#xff0c;其中六种为 Primitive Value&#xff0c;Null&#xff0c; Undefined&#xff0c;String&#xff0c; Number&#xff0c; Boolean&#xff0c; Symbol。而最后一种 Object build-in type 与通常意义上的 Ja…

C 语言

2019独角兽企业重金招聘Python工程师标准>>> #include <stdio.h> #include <sys/types.h> #include <fcntl.h> #include <unistd.h>typedef struct Hello {int a; } Hello;int main(){Hello *h;Hello ha;ha.a 1234;h &ha;int fd ope…

Selenium Grid使用与探索

一、启动Grid&#xff0c;顺序执行测试案例&#xff1a; 进入到Selenium Grid的根目录&#xff0c; ant launch-hub。启动Hub服务。运行后查看http://localhost:4444/console &#xff0c;检查Hub服务是否启动成功。 Hub启动成功后&#xff0c;首先来试运行一下&#xff0c;在…

如何将视频分割成几部分 视频剪切软件哪个好

视频已经成为继文字&#xff0c;图片后的又一个交流方式&#xff0c;在这个快节奏的发展时代&#xff0c;很多人看到文字就会头疼&#xff0c;转而通过视频来获取外界传递的信息&#xff0c;尤其是短视频以及影视的发展&#xff0c;对于很多女生来说&#xff0c;大概在追剧的过…

服务端线上接口监控实践

背景 最近上线了一个新的服务&#xff0c;这个服务有一个特点就是接入了n个第三方的数据服务&#xff0c;前端通过不同参数请求被测服务端&#xff0c;服务端根据参数不同proxy_pass到不同的后端服务器获取数据&#xff0c;处理后吐给前端展示&#xff1b; 问题 被测服务和后端…

Linux后台进程管理

fg、bg、jobs、&、ctrlz命令 一、 & 加在一个命令的最后&#xff0c;可以把这个命令放到后台执行 ,如sh start.sh & 二、ctrl z 可以将一个正在前台执行的命令放到后台&#xff0c;并且处于暂停状态&#xff0c;不可执行。 三、jobs&#xff1a;查看当前有多少在后…

MySQL Block Nested-Loop Join(BNL)

5.5 版本之前&#xff0c;MySQL本身只支持一种表间关联方式&#xff0c;就是嵌套循环(Nested Loop)。如果关联表的数据量很大&#xff0c;则join关联的执行时间会非常长。在5.5以后的版本中&#xff0c;MySQL通过引入BNL算法来优化嵌套执行【Nested Loop Join】 NLJ 算法…