Quailty and Binary Operation
题意
- 分别给\(N,M(N,M \le 50000)\)两个数组\(A\)和\(B\),满足\(0 \le A_i,B_i \le 50000\)。
- 有\(Q(Q \le 50000)\)次询问,每次求\(a_i \ opt\ b_j = c\)的对数\((i,j)\)。
- \[x\ opt\ y = \begin{cases} x+y,\ if\ x<y, \\ x-y,\ otherwise. \end{cases}
\]
思路
- 分治+FFT
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<time.h>
#include<stdlib.h>
#include<assert.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef pair<int, int> pii;
const int N = (1 << 17) + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const double Pi = acos(-1.0);
const double EPS = 1e-8;
//--------head--------
struct FastIO {
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() :
wpos(0) {
}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if (pos == len)
return -1;
return buf[pos++];
}
inline int xuint() {
int c = xchar(), x = 0;
while (c <= 32)
c = xchar();
for (; '0' <= c && c <= '9'; c = xchar())
x = x * 10 + c - '0';
return x;
}
inline int xint() {
int s = 1, c = xchar(), x = 0;
while (c <= 32)
c = xchar();
if (c == '-')
s = -1, c = xchar();
for (; '0' <= c && c <= '9'; c = xchar())
x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s) {
int c = xchar();
while (c <= 32)
c = xchar();
for (; c > 32; c = xchar())
*s++ = c;
*s = 0;
}
inline void wchar(int x) {
if (wpos == S)
fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos++] = x;
}
inline void wint(int x) {
if (x < 0)
wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n)
s[n++] = '0' + x % 10, x /= 10;
while (n--)
wchar(s[n]);
}
inline void wstring(const char *s) {
while (*s)
wchar(*s++);
}
~FastIO() {
if (wpos)
fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
int n, m, q, a[N], b[N];
ll ans[N << 1];
int ca[N], cb[N];
struct C {
double r, i;
C() {
r = i = 0;
}
C(double _r, double _i) {
r = _r, i = _i;
}
C operator+(const C &p) const {
return C(r + p.r, i + p.i);
}
C operator-(const C &p) const {
return C(r - p.r, i - p.i);
}
C operator*(const C &p) const {
return C(r * p.r - i * p.i, r * p.i + i * p.r);
}
};
void fft(C x[], int n, int rev) {
int i, j, k, t;
for (i = 1; i < n; ++i) {
for (j = 0, k = n >> 1, t = i; k; k >>= 1, t >>= 1)
j = j << 1 | (t & 1);
if (i < j)
swap(x[i], x[j]);
}
int s, ds;
for (s = 2, ds = 1; s <= n; ds = s, s <<= 1) {
C w = C(1, 0), t;
C wn = C(cos(2.0 * rev * Pi / s), sin(2.0 * rev * Pi / s));
for (k = 0; k < ds; ++k, w = w * wn)
for (i = k; i < n; i += s) {
t = w * x[i + ds];
x[i + ds] = x[i] - t;
x[i] = x[i] + t;
}
}
if (rev == -1)
for (i = 0; i < n; ++i)
x[i].r /= n;
}
C A[N], B[N], R[N];
void solve(int l, int r) {
if (l > r) {
return ;
}
if(r - l <= 30){
for(int i=l;i<=r;++i){
for(int j=l;j<=i;++j)
ans[i-j] += 1ll * ca[i] * cb[j];
for(int j=i+1;j<=r;++j)
ans[i+j] += 1ll * ca[i] * cb[j];
}
return ;
}
int m = (l + r) >> 1, L = 1;
while (L < r - l + 1)
L <<= 1;
solve(l, m), solve(m + 1, r);
// x + y
rep(i, 0, L) {
A[i] = (l + i <= m ? C(ca[l + i], 0) : C(0, 0));
B[i] = (m + i + 1 <= r ? C(cb[m + 1 + i], 0) : C(0, 0));
}
fft(A, L, 1), fft(B, L, 1);
rep(i, 0, L)
R[i] = A[i] * B[i];
fft(R, L, -1);
rep(i, 0, L)
ans[i + l + m + 1] += (ll) (R[i].r + 0.5);
// x - y
rep(i, 0, L) {
A[i] = (m + 1 + i <= r ? C(ca[m + 1 + i], 0) : C(0, 0));
B[i] = (m - i >= l ? C(cb[m - i], 0) : C(0, 0));
}
fft(A, L, 1), fft(B, L, 1);
rep(i, 0, L)
R[i] = A[i] * B[i];
fft(R, L, -1);
rep(i, 0, L)
ans[i + 1] += (ll) (R[i].r + 0.5);
}
int main() {
int T = 10;
T = io.xuint();
rep(cas, 0, T) {
n = io.xuint();
m = io.xuint();
q = io.xuint();
// n = m = q = 50000;
// rep(i, 0, n) a[i] = i, ++ca[a[i]];
// rep(i, 0, m) b[i] = i, ++cb[b[i]];
rep(i, 0, n) a[i] = io.xuint(), ++ca[a[i]];
rep(i, 0, m) b[i] = io.xuint(), ++cb[b[i]];
int mn = min(*min_element(a, a + n), *min_element(b, b + m));
int mx = max(*max_element(a, a + n), *max_element(b, b + m));
// printf("mn = %d, mx = %d\n", mn, mx);
solve(mn, mx);
rep(_q, 0, q) {
int x;
x = io.xuint();
printf("%lld\n", ans[x]);
}
rep(i, 0, 1 + (mx << 1))
ans[i] = 0;
rep(i, 0, n)
ca[a[i]] = 0;
rep(i, 0, m)
cb[b[i]] = 0;
}
return 0;
}
Quailty and Binary Operation的更多相关文章
-
[玲珑OJ1044] Quailty and Binary Operation (FFT+cdq分治)
题目链接 题意:给定两个长度为n的数组a与长度为m的数组b, 给定一个操作符op满足 x op y = x < y ? x+y : x-y. 有q个询问,每次给出询问c,问:有多少对(i, j ...
-
Data structure alignment by binary operation
在寫C的過程中,我們會很自然地以為,我連續宣告一堆大小不一的char array. 經過Complier之後這些char array未必是連續擺放.至於為什麼就要談到我們今天的主角了alignment ...
-
uestc 1709 Binary Operations 位运算的灵活运用
Binary Operations Time Limit: 2000 ms Memory Limit: 65535 kB Solved: 56 Tried: 674 Description B ...
-
matlab进阶:常用功能的实现,常用函数的说明
常用功能的实现 获取当前脚本所在目录 current_script_dir = fileparts(mfilename('fullpath')); % 结尾不带'/' 常用函数的说明 bsxfun m ...
-
reduce方法
API里面这样写 reduce(initial, sym) → obj reduce(初始值,符号) reduce(sym) → obj re ...
-
Scalaz(8)- typeclass:Monoid and Foldable
Monoid是种最简单的typeclass类型.我们先看看scalaz的Monoid typeclass定义:scalaz/Monoid.scala trait Monoid[F] extends S ...
-
我们的动机(Our motivation)
我们的动机(Our motivation) There are many PHP frameworks nowadays, but none of them is like Phalcon (Real ...
-
bzoj2548[Cstc2002]灭鼠行动
Description 最近,有一些繁殖力很强的老鼠在下水道非常猖獗,灭鼠特工队正在计划消灭这些老鼠.下水道只有东西方向和南北方向的管道,如图所示. 灭鼠特工队的队员拥有强大的武器.他们将在某些时刻t ...
-
hdu-5929 Basic Data Structure(双端队列+模拟)
题目链接: Basic Data Structure Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 65536/65536 K (Ja ...
随机推荐
-
UIAlertController
楼主在整理项目的警告,于是乎你懂的. 然后自己整理了一下以后方便自己忘了之后能及时找到它 关于UIAlertController .h文件的解析 /** 关于UIAlertController的解析 ...
-
python3 字典相关函数
python版本3.5 #Author by Liguangbo#_*_ coding:utf-8 _*_'''info={'No.1':'ligb','No.2':'donglx','No.3':' ...
-
通过MSSQL连接服务器连接至Oracle数据库
前言 有很多时候,我们需要MSSQL与Oracle进行跨库查询或数据交互.本篇随笔将阐述如何通过MSSQL的连接服务器连接至Oracle数据库,并且读取数据的示例. 具体步骤 首先需要到Oracle的 ...
-
CentOS学习笔记--系统服务 (daemons)
系统服务 (daemons) 系统为了某些功能必须要提供一些服务 (不论是系统本身还是网络方面),这个服务就称为 service . 但是 service 的提供总是需要程序的运行吧!否则如何运行呢? ...
-
Android使用JNI(从java调用本地函数)
当编写一个混合有本地C代码和Java的应用程序时,需要使用Java本地接口(JNI)作为连接桥梁.JNI作为一个软件层和API,允许使用本地代码调用Java对象的方法,同时也允许在Java方法中调用本 ...
-
poj 2362
回溯加剪枝 #include <cstdio> #include <cstdlib> #include <cmath> #include <map> # ...
-
navicat for mysql远程连接ubuntu服务器的mysql数据库
经常玩服务器上的mysql数据库,但是基于linux操作Mysql多有不便,于是就想着使用GUI工具来远程操作mysql数据库.已经不是三次使用navicat-for-mysql了,但是每次连接远程服 ...
-
node.js 从入门到。。。
本人安装环境为 mac ,所以只记录了 mac 下的操作步骤 1.安装 node node的国内下载地址:http://nodejs.cn/download/ 安装之后,在终端输入指令 node -v ...
-
PyQt5学习笔记----标准文件打开保存框QFileDialog
单个文件打开 QFileDialog.getOpenFileName()多个文件打开 QFileDialog.getOpenFileNames() 文件夹选取 QFileDialog.getE ...
-
多线程处理慢sql查询小笔记~
多线程处理慢sql查询以及List(Array)的拆分 系统数据量不大,但是访问速度特别慢,使用多线程优化一下!!! 优化结果:访问时间缩短了十几秒 25s --> 8s 一.List的拆分: ...