HDU 5213 Lucky 莫队+容斥

时间:2022-09-01 07:30:21

Lucky

Problem Description

WLD is always very lucky.His secret is a lucky number K.k is a fixed odd number. Now he meets a stranger with N numbers:a1,a2,...,aN.The stranger asks him M questions.Each question is like this:Given two ranges [Li,Ri] and [Ui,Vi],you can choose two numbers X and Y to make aX+aY=K.The X you can choose is between Li and Ri and the Y you can choose is between Ui and Vi.How many pairs of numbers(X,Y) you can choose?
If WLD can answer all the questions correctly,he'll be the luckiest man in the world.Can you help him?
 
Input
 
There are multiple cases.(At MOST 5)

For each case:

The first line contains an integer N(1≤N≤30000).

The following line contains an integer K(2≤K≤2∗N),WLD's lucky number.K is odd.

The following line contains N integers a1,a2,...,aN(1≤ai≤N).

The following line contains an integer M(1≤M≤30000),the sum of the questions WLD has to answer.

The following M lines,the i-th line contains 4 numbers Li,Ri,Ui,Vi(1≤Li≤Ri<Ui≤Vi≤N),describing the i-th question the stranger asks.

 
Output
 
For each case:

Print the total of pairs WLD can choose for each question.

 
Sample Input
 
5
3
1 2 1 2 3
1
1 2 3 5
 
Sample Output
 
2
Hint

a1+a4=a2+a3=3=K.
So we have two pairs of numbers (1,4) and (2,3).
Good luck!

 

题意

  给你你n个数一个k

  m次询问,每次给你两区间

  问你这两个区间 任选两个数a[i] + a[j] = k 的对数

题解:

  这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A,B时的答案 用记号+表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值

  不妨假设A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]A=[l1,r1],B=[l2,r2],C=[r1+1,l2−1]

  容易知道f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)f(A,B)=f(A+B+C,A+B+C)+f(C,C)−f(A+C,A+C)−f(C+B,C+B)

  因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为O(msqrt(n))O(msqrt(n))

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 3e4+, M = 6e4+, mod = 1e9+, inf = 1e9+;
typedef long long ll; int T,n,a[N],ans[N],belong[N],mp[M * ],k;
struct ss{
int l,r,id,res;
ss () {}
ss (int l,int r,int id,int res) : l(l), r(r), id(id), res(res) {}
}Q[N * ];
bool operator < (ss s1 , ss s2) {
if(belong[s1.l] == belong[s2.l]) return s1.r<s2.r;
else return belong[s1.l] < belong[s2.l];
} int main()
{
while(~scanf("%d",&n)) {
memset(mp,,sizeof(mp));
memset(ans,,sizeof(ans));
scanf("%d",&k);
for(int i = ; i <= n; ++i) scanf("%d",&a[i]);
int q,cnt=;cin>>q;
for(int i = ; i <= q; ++i) {
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
Q[++cnt] = ss (l1,r2,i,);
if(l2->=r1+)Q[++cnt] = ss (r1+,l2-,i,);
Q[++cnt] = ss(r1+,r2,i,-);
Q[++cnt] = ss(l1,l2-,i,-);
}
int t = sqrt(n);
for(int i = ; i <= n; ++i) belong[i] = (i-) / t + ;
sort(Q+,Q+cnt+);
int l = , r = , ret = ;
for(int i = ; i <= cnt; ++i) {
for(;r<Q[i].r;r++) {
ret += mp[k-a[r+]+M];
mp[a[r+]+M]++;
}
for(;l>Q[i].l;l--) {
ret += mp[k-a[l-]+M];
mp[a[l-]+M]++;
}
for(;r>Q[i].r;r--) {
mp[a[r]+M]--;
ret -= mp[k-a[r]+M]; }
for(;l<Q[i].l;l++) {
mp[a[l]+M]--;
ret -= mp[k-a[l]+M]; }
// cout<<Q[i].l<<" "<<Q[i].r<<" ";
//cout<<Q[i].res*ret<<endl;
ans[Q[i].id] += Q[i].res*ret;
}
for(int i = ; i <= q; ++i) {
printf("%d\n",ans[i]);
}
}
}

HDU 5213 Lucky 莫队+容斥的更多相关文章

  1. Lucky HDU - 5213 (莫队,容斥)

    WLD is always very lucky.His secret is a lucky number . is a fixed odd number. Now he meets a strang ...

  2. HDU 5145 分块 莫队

    给定n个数,q个询问[l,r]区间,每次询问该区间的全排列多少种. 数值都是30000规模 首先考虑计算全排列,由于有同种元素存在,相当于每次在len=r-l+1长度的空格随意放入某种元素即$\bin ...

  3. HDU 5768 Lucky7 &lpar;中国剩余定理&plus;容斥&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5768 给你n个同余方程组,然后给你l,r,问你l,r中有多少数%7=0且%ai != bi. 比较明显 ...

  4. hdu 6390 欧拉函数&plus;容斥(莫比乌斯函数) GuGuFishtion

    http://acm.hdu.edu.cn/showproblem.php?pid=6390 题意:求一个式子 题解:看题解,写代码 第一行就看不出来,后面的sigma公式也不会化简.mobius也不 ...

  5. HDU 6053 TrickGCD 莫比乌斯函数&sol;容斥&sol;筛法

    题意:给出n个数$a[i]$,每个数可以变成不大于它的数,现问所有数的gcd大于1的方案数.其中$(n,a[i]<=1e5)$ 思路:鉴于a[i]不大,可以想到枚举gcd的值.考虑一个$gcd( ...

  6. hdu 5768 Lucky7 中国剩余定理&plus;容斥&plus;快速乘

    Lucky7 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem D ...

  7. hdu 4336 Card Collector —— Min-Max 容斥

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4336 bzoj 4036 的简单版,Min-Max 容斥即可. 代码如下: #include<cst ...

  8. hdu 4638 Group 莫队算法

    题目链接 很裸的莫队, 就不多说了... #include<bits/stdc++.h> using namespace std; #define pb(x) push_back(x) # ...

  9. HDU 6397 Character Encoding &lpar;组合数学 &plus; 容斥&rpar;

    题意: 析:首先很容易可以看出来使用FFT是能够做的,但是时间上一定会TLE的,可以使用公式化简,最后能够化简到最简单的模式. 其实考虑使用组合数学,如果这个 xi 没有限制,那么就是求 x1 + x ...

随机推荐

  1. Json概述以及python对json的相关操作

    JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式.易于人阅读和编写.同时也易于机器解析和生成.它基于JavaScript Programming Langu ...

  2. vim正则表达式(转)

    Vim中的正则表达式功能很强大,如果能*运用,则可以完成很多难以想象的操作. 如果你比较熟悉Perl的正规表达式,可以直接参照与Perl正则表达式的区别一节. 一.使用正则表达式的命令 使用正则表达 ...

  3. JavaScript面向对象简介

    JavaScript面向对象简介 @(编程) [TOC] 1. 命名空间 命名空间是一个容器,它允许开发人员在一个独特的,特定于应用程序的名称下捆绑所有的功能. 在JavaScript中,命名空间只是 ...

  4. springmvc中forward和redirect

    一.跳转 import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; im ...

  5. 判断一个面(Polygon)是不是矩形

    判断一个面是不是矩形在GIS中很长用的功能,那么怎么判断一个面是不是矩形呢. 这里先要弄懂一些概念,面是什么,先看OGC标准的定义. 我的英文水平有限,(有翻译更好的请留言,如果翻译的准确将被采纳)大 ...

  6. 调用test case集,并生成测试报告

    结构是 test_all.py 进行配置,执行所有测试用例集,并合并测试报告到同一个文件 #test_all.py 进行配置,执行所有测试用例集 # coding = utf-8 from time ...

  7. SpringMVC 上下文webApplicationContext

    使用listener听众载入配置,一般Struts+Spring+Hibernate是使用listener监听器的.例如以下 <listener> <listener-class&g ...

  8. sbt结合IDEA对Spark进行断点调试开发

    笔者出于工作及学习的目的,经常与Spark源码打交道,也难免对Spark源码做修改及测试.本人一向讲究借助工具提升效率,开发Spark过程中也在摸索如何更加顺畅的对源码进行调试. Spark基于Sca ...

  9. 201521123049 《JAVA程序设计》 第3周学习总结

    1. 本周学习总结 1.学习了对象与类的定义: 2.掌握了构造函数与其重载: 3.学会了this关键字的利用: 4.明白了静态变量与非静态变量的区分. 下面是对本周学习的图片小结: 2. 书面作业 Q ...

  10. phpstudy中的mysql

    1.进入mysql命令台,执行 select version()即可 2status;