关键词：
【题目描述】
给定两个长度为 n 的整数数列 A 和 B。再给定 q 组查询，每次查询给出两个整数 x 和 y，求满足 Ai >= x 且 Bi >= y 这样的 i 的数量。
输入格式
第一行给定两个整数 n 和 q。
第二行给定数列 A，包含 n 个整数。
第三行给定数列 B，包含 n 个整数。
接下来 q 行，每行两个整数 x 和 y，意义如上所述。
输出格式
对于每组查询，输出所求的下标数量。
输入样例
3 2
3 2 4
6 5 8
1 1
4 8
输出样例
3
1
数据规模
对于 30% 的数据，1 <= n, q <= 100。
对于 100% 的数据，1 <= n, q, Ai, Bi <= 10^5。
题解
想用暴力解法是可以通过一些的, 但是复杂度 O(N^2), 对10^5就不行了。
线段树的做法复杂度平均在O(NlogN)。
#include <bits/stdc++.h> using namespace std;//先以A对pair (A, B)排序, 树状数组维护i以后的比y大的个数 const int maxn = 100000 + 10; struct node { int x, y, pos; bool operator < (const node &a) const { if (x == a.x) return y<a.y; return x<a.x; } }p[maxn], q[maxn]; int A[maxn]; int B[maxn]; int lowbit(int i) { return i & (-i); } void add(int a, int i) { while (i <= maxn-1) { A[i] += a; i += lowbit(i); } } int sum(int i) { int res = 0; while (i >= 1) { res += A[i]; i -= lowbit(i); } return res; } int main() { int n, m; cin >> n >> m; for(int i = 0; i < n; i++) scanf("%d", &p[i].x); for(int i = 0; i < n; i++) scanf("%d", &p[i].y); sort(p, p+n); for(int i = 0; i < m; i++) { scanf("%d%d", &q[i].x, &q[i].y); q[i].pos = i; } for(int i = 0; i < n; i++) add(1, p[i].y); sort(q, q+m); int k = 0; for (int i = 0; i < n; i++) { if (p[i].x < q[k].x) add(-1, p[i].y); else { while (1) { B[q[k].pos] = sum(maxn - 1) - sum(q[k].y - 1); k++; if (k >= m) break; if (p[i].x < q[k].x) { add(-1, p[i].y); break; } } } if (k >= m) break; } for (int i = 0; i < m; i++) printf("%d ", B[i]); return 0; }
References
https://www.nowcoder.com/profile/2449601/test/12036803/110438#summary
2018今日头条笔试（第二题）
题目描述给定一个数组序列，需要选出一个区间，使得该区间是所有区间中经过如下计算的值最大的一个。区间中的最小数*区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列[6,2,1]可得... 查看详情
实习生求职今日头条笔试
时间：大三下学期职位：测试开发过程： 首先，会有练习题，但是练习题没有针对性，而且编程题会很简单；主要是用来检查自己的环境是否合适、熟悉系统。 然后就是正式考试了——开始会很卡（反... 查看详情
8.22今日头条笔试
这次套路深啊，怎么还有改错题！。上来看题，每个题目的输入数据都很大，果断上scanf,printf,千万不能用cin,cout1.右上角的点，我的思路是先对每一行去重（题目好像说没有重的点耶！），每一行只有最右边的点才是候选点，然... 查看详情
字节跳动（今日头条）的题目真的难吗？
...进，并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了，总是能看到大家在说字节跳动的题目好难呀，4个编程题没有一个题AC。天天觉得大家好难呀，所以找了一些==字节跳动==关于自家笔试内... 查看详情
●记录今日上午○线段树
●poj3225HelpwithIntervals○赘述题目：给出以下集合操作：然后有初始的一个空集S，和以下题目给出的操作指令，并输入指令：要求进行指令操作后，按格式输出集合S；○题解（此文标题就告诉了我们要用线段树维护。。。）关键... 查看详情
trie树/字典树题目（2017今日头条笔试题：异或）
1/*2本程序说明：34[编程题]异或5时间限制：1秒6空间限制：32768K7给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。8输入描述:9第一行包含两个整数n,m.1011第... 查看详情
今日头条2018aicamp5月26日在线笔试编程题第一道——最佳路径(代码片段)
题目给定一个n*m的矩阵A，矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径，每次只能向右或者向下移动， 使得路径上所有数字之积在16进制下的后缀0最少。输入描述：第一行：n,m(2<=n,m<=1000) ... 查看详情
2019暑假集训8/2
学习内容：线段树+可持久化线段树今日完成题数（不包含多校）：5/*多校补题情况（之前定的每支队伍标准）：?*/今日看书情况：3页学习算法的总结可持久化线段树一直没有好好研究直到最近着重开始写线段树专题写了一些权... 查看详情
字节跳动（今日头条）的题目真的难吗？
...进，并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了，总是能看到大家在说字节跳动的题目好难呀，4个编程题没有一个题AC。天天觉得大家好难呀，所以找了一些==字节跳动==关于自家笔试内... 查看详情
微信小程序-今日头条案例
github地址: https://github.com/HowName/toutiao项目为仿今日头条,使用了百度ApiStore接口查询数据,使用微信组件/api有封装请求方法,底部tab,启动页动画,loading,scroll-view,swiper,列表页支持上下拉加载更多效果图: 启动欢迎页,几行代... 查看详情
一般线段树与权值线段树(代码片段)
目录一般线段树与权值线段树1.算法分析1.1一般线段树1.2权值线段树2.板子2.1线段树入门2.1.1单点修改+区间查询2.1.2区间修改+区间查询2.1.3区间加乘操作2.1.4区间染色2.2权值线段树2.2.1求第k大、前驱、后继等3.例题3.1线段树入门3.2... 查看详情
线段树模板（poj3468）
之前一直没手写过线段树，今日手写线段树发现模板理解起来还是很容易的，lazy标记的用法也大概了解了一点，但对于线段树的理解应该还不是很好（等学会线段树的时候就学树链剖分，立个flag）下面是poj3468代码#include<cstdio... 查看详情
今日头条和今日头条极速版有什么区别
3C数码您的浏览器不支持HTML5视频zymedia(\'video\')参考技术A今日头条和今日头条极速版区别为：安装包大小不同、占用运行内存不同、特色功能不同。一、安装包大小不同1、今日头条普通版：今日头条普通版的安装包大小为22.8M。2... 查看详情
权值线段树套序列线段树(代码片段)
【模板】权值线段树套序列线段树P3380【模板】二逼平衡树（树套树）主要思路如下：外层为权值线段树，内层为动态开点线段树，也就是每个权值线段树上的节点开一个动态开点线段树。外层的权值线段树支持查询排名，内层... 查看详情
模板线段树-单点修改，区间查询
...打（又长又难调）------仅代表个人观点（能别打就别打）线段树是什么？大概长这样？（表示区间1到6）线段树是一颗二叉树，是通过二分思想建立的一颗表示区间关系的树形结构。（总之记住它很好用就对了）怎样建一颗线段... 查看详情
bzoj3110zjoi2013k大数查询线段树套线段树
...1、在a和b之间插入c 2、询问[a,b]中的第c大题解：权值线段树套区间线段树外层的权值线段树中每个节点如果维护[L,R]这个区间，那么该节点所对应的线段树维护的就是[L,R]这些数在每个区间里出现了几次，也就是说如果外层线... 查看详情
今日头条（3-30）第四题（离线）
题意：n对(a,b),q次查询(x,y)a>=x&&b>=y的对数对于100%数据，1<=所有的数<=1e51#include<bits/stdc++.h>2usingnamespacestd;3constintmaxn=1e5+5;4inta[maxn],b[maxn],c[maxn];5intx[maxn],y[maxn],z[maxn];6 查看详情
线段树区间修改和查询和单点查询（线段树模板1）(代码片段)
https://www.luogu.com.cn/problem/P3372题目描述如题，已知一个数列，你需要进行下面两种操作：将某区间每一个数加上 kk。求出某区间每一个数的和。输入格式第一行包含两个整数 n,mn,m，分别表示该数列数字的个数和操作的总... 查看详情