Gym101138D Strange Queries/BZOJ5016 SNOI2017 一个简单的询问 莫队、前缀和、容斥
2024-08-20 13:52:25
THUWC2019D1T1撞题可还行
以前有些人做过还问过我,但是我没有珍惜,直到进入考场才追悔莫及……
设\(que_{i,j}\)表示询问\((1,i,1,j)\)的答案,那么询问\((a,b,c,d)=que_{b,d} - que_{a-1 , d} - que_{b , c - 1} + que_{a - 1 , c - 1}\)
把一个询问拆成\(4\)个询问,然后对这\(4\)个询问莫队就可以了
不知道怎么回事THUWC上想到了莫队想到了前缀和想到了容斥就是没想到莫队+前缀和+容斥……
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return f ? -a : a;
}
const int MAXN = 5e4 + 3;
int N , M , T , cnt , cntQ;
int arr[MAXN] , times[MAXN][2];
long long ans[MAXN] , cur;
struct query{
int p1 , p2 , ind , flg;
query(int a = 0 , int b = 0 , int c = 0 , int d = 0):p1(a) , p2(b) , ind(c) , flg(d){}
bool operator <(const query b)const{
return p1 / T == b.p1 / T ? p2 < b.p2 : p1 < b.p1;
}
}que[MAXN << 2];
inline void add(int a , int ind){
cur += times[a][ind ^ 1];
++times[a][ind];
}
inline void del(int a , int ind){
cur -= times[a][ind ^ 1];
--times[a][ind];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read();
T = sqrt(N);
for(int i = 1 ; i <= N ; ++i)
arr[i] = read();
M = read();
for(int i = 1 ; i <= M ; ++i){
int a = read() , b = read() , c = read() , d = read();
que[++cntQ] = query(b , d , i , 1);
if(a - 1)
que[++cntQ] = query(a - 1 , d , i , -1);
if(b - 1)
que[++cntQ] = query(b , c - 1 , i , -1);
if(a - 1 && b - 1)
que[++cntQ] = query(a - 1 , c - 1 , i , 1);
}
sort(que + 1 , que + cntQ + 1);
int l1 = 0 , l2 = 0;
for(int i = 1 ; i <= cntQ ; ++i){
while(l1 < que[i].p1)
add(arr[++l1] , 0);
while(l1 > que[i].p1)
del(arr[l1--] , 0);
while(l2 < que[i].p2)
add(arr[++l2] , 1);
while(l2 > que[i].p2)
del(arr[l2--] , 1);
ans[que[i].ind] += que[i].flg * cur;
}
for(int i = 1 ; i <= M ; ++i)
cout << ans[i] << '\n';
return 0;
}
最新文章
- 介绍几个好用的vs插件
- Web负载均衡的几种实现方式
- js 图片轮播(一)
- puporwindow
- Java虚拟机内存管理机制
- 解读SQL Server 2014可更新列存储索引——存储机制
- paip.基于navicate mysql的自动化报表工具总结
- CCNA实验4:HDLC和PPP
- dict和set
- 从零开始学android开发-项目打包发布
- 调用系统API还是很高效的,不必担心性能
- T-SQL触发器
- QF——UI之几种常用的隐藏键盘的方法
- python cookbook第三版学习笔记 一
- ABB机器人基础培训资料整理与总结
- java环境下载
- P3833 [SHOI2012]魔法树
- pyhton 学习 函数式编程
- android studio 引用远程仓库下载慢(JCenter下载慢)的办法
- test20181006 石头剪刀布
热门文章
- 你不可不知的Java引用类型之——PhantomReference源码详解
- OneAPM 获得“2018中国 IT 服务创新奖”,彰显技术创新实力
- websocket后台数据推送
- ERROR 1044 (42000): Access denied for user 'root'@'localhost'
- Timeout occurred while waiting for latch: class &#39;ACCESS_METHODS_DATASET_PARENT&#39;
- c/c++ 哈希表 hashtable
- f.lux 自动调节显示器色温
- ES5-ES6-ES7_对象的扩展
- Linux的基础命令
- 数位dp D - Count The Bits