Lucky
Problem Description
If WLD can answer all the questions correctly,he'll be the luckiest man in the world.Can you help him?
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.
Print the total of pairs WLD can choose for each question.
3
1 2 1 2 3
1
1 2 3 5
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 莫队+容斥的更多相关文章
-
Lucky HDU - 5213 (莫队,容斥)
WLD is always very lucky.His secret is a lucky number . is a fixed odd number. Now he meets a strang ...
-
HDU 5145 分块 莫队
给定n个数,q个询问[l,r]区间,每次询问该区间的全排列多少种. 数值都是30000规模 首先考虑计算全排列,由于有同种元素存在,相当于每次在len=r-l+1长度的空格随意放入某种元素即$\bin ...
-
HDU 5768 Lucky7 (中国剩余定理+容斥)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5768 给你n个同余方程组,然后给你l,r,问你l,r中有多少数%7=0且%ai != bi. 比较明显 ...
-
hdu 6390 欧拉函数+容斥(莫比乌斯函数) GuGuFishtion
http://acm.hdu.edu.cn/showproblem.php?pid=6390 题意:求一个式子 题解:看题解,写代码 第一行就看不出来,后面的sigma公式也不会化简.mobius也不 ...
-
HDU 6053 TrickGCD 莫比乌斯函数/容斥/筛法
题意:给出n个数$a[i]$,每个数可以变成不大于它的数,现问所有数的gcd大于1的方案数.其中$(n,a[i]<=1e5)$ 思路:鉴于a[i]不大,可以想到枚举gcd的值.考虑一个$gcd( ...
-
hdu 5768 Lucky7 中国剩余定理+容斥+快速乘
Lucky7 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Problem D ...
-
hdu 4336 Card Collector —— Min-Max 容斥
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4336 bzoj 4036 的简单版,Min-Max 容斥即可. 代码如下: #include<cst ...
-
hdu 4638 Group 莫队算法
题目链接 很裸的莫队, 就不多说了... #include<bits/stdc++.h> using namespace std; #define pb(x) push_back(x) # ...
-
HDU 6397 Character Encoding (组合数学 + 容斥)
题意: 析:首先很容易可以看出来使用FFT是能够做的,但是时间上一定会TLE的,可以使用公式化简,最后能够化简到最简单的模式. 其实考虑使用组合数学,如果这个 xi 没有限制,那么就是求 x1 + x ...
随机推荐
-
Json概述以及python对json的相关操作
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式.易于人阅读和编写.同时也易于机器解析和生成.它基于JavaScript Programming Langu ...
-
vim正则表达式(转)
Vim中的正则表达式功能很强大,如果能*运用,则可以完成很多难以想象的操作. 如果你比较熟悉Perl的正规表达式,可以直接参照与Perl正则表达式的区别一节. 一.使用正则表达式的命令 使用正则表达 ...
-
JavaScript面向对象简介
JavaScript面向对象简介 @(编程) [TOC] 1. 命名空间 命名空间是一个容器,它允许开发人员在一个独特的,特定于应用程序的名称下捆绑所有的功能. 在JavaScript中,命名空间只是 ...
-
springmvc中forward和redirect
一.跳转 import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; im ...
-
判断一个面(Polygon)是不是矩形
判断一个面是不是矩形在GIS中很长用的功能,那么怎么判断一个面是不是矩形呢. 这里先要弄懂一些概念,面是什么,先看OGC标准的定义. 我的英文水平有限,(有翻译更好的请留言,如果翻译的准确将被采纳)大 ...
-
调用test case集,并生成测试报告
结构是 test_all.py 进行配置,执行所有测试用例集,并合并测试报告到同一个文件 #test_all.py 进行配置,执行所有测试用例集 # coding = utf-8 from time ...
-
SpringMVC 上下文webApplicationContext
使用listener听众载入配置,一般Struts+Spring+Hibernate是使用listener监听器的.例如以下 <listener> <listener-class&g ...
-
sbt结合IDEA对Spark进行断点调试开发
笔者出于工作及学习的目的,经常与Spark源码打交道,也难免对Spark源码做修改及测试.本人一向讲究借助工具提升效率,开发Spark过程中也在摸索如何更加顺畅的对源码进行调试. Spark基于Sca ...
-
201521123049 《JAVA程序设计》 第3周学习总结
1. 本周学习总结 1.学习了对象与类的定义: 2.掌握了构造函数与其重载: 3.学会了this关键字的利用: 4.明白了静态变量与非静态变量的区分. 下面是对本周学习的图片小结: 2. 书面作业 Q ...
-
phpstudy中的mysql
1.进入mysql命令台,执行 select version()即可 2status;