洛谷P3674 小清新人渣的本愿
2024-09-24 10:01:00
题意:多次询问,区间内是否存在两个数,使得它们的和为x,差为x,积为x。
n,m,V <= 100000
解:
毒瘤bitset......
假如我们有询问区间的一个桶,那么我们就可以做到O(n)枚举查找了。
然后我们用bitset优化一下......外面套上莫队来维护桶。
具体来说,差为x可以写成 a - b = x
然后我们把bitset左移/右移x位,与原来的and一下,看是否有元素为1即可。
和为x可以写成 a + b = x N - a - b = N - x (N - a) - b = N - x
这启示我们维护一个N - x的反桶,然后把反桶右移N - x位与原桶and。
关于积,直接n0.5暴力即可。
#include <cstdio>
#include <bitset>
#include <cmath>
#include <algorithm> const int N = ; int fr[N], a[N], bin[N];
std::bitset<N> bs, bs2, tp; struct ASK {
int f, l, r, x, t, ans;
inline bool operator <(const ASK &w) const {
if(fr[l] != fr[w.l]) {
return l < w.l;
}
return r < w.r;
}
}ask[N]; inline bool cmp(const ASK &A, const ASK &B) {
return A.t < B.t;
} inline void add(int x) {
if(!bin[a[x]]) {
bs.set(a[x]);
bs2.set(N - a[x]);
}
bin[a[x]]++;
return;
} inline void del(int x) {
bin[a[x]]--;
if(!bin[a[x]]) {
bs.reset(a[x]);
bs2.reset(N - a[x]);
}
return;
} int main() {
int n, m;
scanf("%d%d", &n, &m);
int T = sqrt(n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
fr[i] = (i - ) / T + ;
}
for(int i = ; i <= m; i++) {
scanf("%d%d%d%d", &ask[i].f, &ask[i].l, &ask[i].r, &ask[i].x);
ask[i].t = i;
}
std::sort(ask + , ask + m + ); int l = , r = ;
bin[a[]]++;
bs.set(a[]);
bs2.set(N - a[]);
for(int i = ; i <= m; i++) {
while(l > ask[i].l) {
add(--l);
}
while(r < ask[i].r) {
add(++r);
}
while(l < ask[i].l) {
del(l++);
}
while(r > ask[i].r) {
del(r--);
}
// ------------
if(ask[i].f == ) {
tp = bs & (bs >> ask[i].x);
ask[i].ans = tp.any();
}
else if(ask[i].f == ) {
tp = bs & (bs2 >> (N - ask[i].x));
ask[i].ans = tp.any();
}
else {
bool fd = ;
for(int j = ; j * j <= ask[i].x; j++) {
if(ask[i].x % j) {
continue;
}
if(bs[j] && bs[ask[i].x / j]) {
ask[i].ans = ;
break;
}
}
}
} std::sort(ask + , ask + m + , cmp);
for(int i = ; i <= m; i++) {
if(ask[i].ans) {
puts("hana");
}
else {
puts("bi");
}
}
return ;
}
AC代码
最新文章
- BZOJ 3531: [Sdoi2014]旅行 [树链剖分]
- GPS部标平台的架构设计(五)-地图服务算法库
- flow.ci Beta 上线,将开发工作流自动化
- POJ 2559 Largest Rectangle in a Histogram(单调栈)
- 使用visual studio 2012 编译opencv2.4.9
- 【多线程同步案例】Race Condition引起的性能问题
- Flask-在浏览器中直接显示文本文件中的内容
- linux线程(二)内存释放
- 通过eclipse的DDMS连接bluestacks找不到设备的解决方法
- 黑马程序员-for和foreach
- unity 之2D游戏简单操作
- winsocket <;研究了一天的成果>;
- 内部框架——axure线框图部件库介绍
- 2、Libgdx配置你的开发环境(Eclipse,Intellij IDEA,NetBeans)
- Extjs renderer函数
- 深入研究EF Core AddDbContext 引起的内存泄露的原因
- IdentityServer4【Reference】之Profile Service
- Nginx ssl证书部署方法
- Android IntentFilter匹配规则
- 实验五 Java网络编程及安全 实验报告 20135232王玥
热门文章
- day 7-12 数据库的基本操作和存储引擎
- C# Note11:如何优雅地退出WPF应用程序
- Vue 中提示报错 handlers[i].call is not a function解决方法
- springCloud com.sun.jersey.api.client.ClientHandlerException: java.net.ConnectException: Connection refused: connect
- vue element-ui 绑定@keyup事件无效
- tornado.gen.coroutine-协程
- CSS3之box-sizing属性
- fpm 打包教程
- zabbix在ubuntu16.04上的安装
- try-with-resource机制的一个编译陷阱