题意:给出\(n<3e4\)个有序组\((a,b,c,d,e)\),求对第\(i\)个有序组有多少个\(j\)满足\((a_j<a_i,b_j<b_i,c_j<c_i,d_j<d_i,e_j<e_i)\) 五维偏序问题按套路来可以排序+树套树套树套树(打死 然而这是显然连\(O(n^2)\)暴力都不如的 可是题目给4s,\(O(n^2)\)是不可能的,但在神奇的bitset加持下\(O(5*n^2/32)\)的时空复杂度是可以卡过去的! 用bitset表示集合,\(bi

求解五维偏序 给定 \(n(\le 3\times 10^4)\) 个五元组,对于每个五元组 \((a_i, b_i, c_i, d_i, e_i)\),求存在多少个 \(1\le j\le n\) 满足 \(a_i > a_j\) 且 \(b_i > b_j\) 且 \(c_i > c_j\) 且 \(d_i > d_j\) 且 \(e_i > e_j\).保证每一维都是 \(1\cdots n\) 的排列. 第一感觉 传统的做法有 cdq 分治或 树套树,但是在本题中复杂

COGS2479:四维偏序. CDQ套CDQ CDQ:对a分治,对b排序,再对a打标记,然后执行CDQ2 CDQ2:对b分治,对c归并排序,对d树状数组. #include<cstdio> #include<algorithm> #define rep(i,l,r) for (int i=l; i<=r; i++) using namespace std; typedef long long ll; ; int n,ans,c[N]; struct P{ int a,b,c,

hiho#1513 : 小Hi的烦恼 五维偏序 链接 hiho 思路 高维偏序用bitset,复杂度\((\frac{n^2}{32})\) 代码 #include <bits/stdc++.h> using namespace std; const int N=3e4+7; int read() { int x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0

初识CDQ分治 CDQ分治是一个好东西,一直听着dalao们说所以就去学了下. CDQ分治是我们处理各类问题的重要武器.它的优势在于可以顶替复杂的高级数据结构,而且常数比较小:缺点在于必须离线操作. --by __stdcall 其实CDQ分治名字听上去很高大上,其实和一般的分治没有特别大的区别,其大体流程如下: 将问题抽象为一个区间\([l,r]\)内的问题(废话) 分:将问题分解成左\([l,mid]\)右\([mid+1,r]\)两部分,然后递归操作 治:合并两个子问题,同时考虑到\([l

卢卡斯定理 题目中说到\(p\)是质数. 而此时要求组合数向质数取模的结果,就可以用卢卡斯定理: \[C_x^y=C_{x\ div\ p}^{y\ div\ p}\cdot C_{x\ mod\ p}^{y\ mod\ p}\] 也就是说,我们可以把\(x\)和\(y\)转化成两个\(p\)进制数,然后每一位分别求组合数后再乘起来. 所以问题来了,什么时候一个组合数的值模\(p\)为\(0\)? 由于它是质数,所以对于一个组合数\(C_a^b\),当且仅当\(a<b\)时它的值才会为\(0\)

「HAOI2017」新型城市化 题意 有一个 \(n\) 个点的无向图,其中只有 \(m\) 对点之间没有连边,保证这张图可以被分为至多两个团. 对于 \(m\) 对未连边的点对,判断有哪些点对满足将他们连边后最大团 的大小增加. \(n \le 10^4 , m \le 1.5 × 10^5\) 题解 脑洞图论题我真的一道都不会. 考虑原图的话,有 \(n^2\) 条边,显然是不行的.可以考虑补图,那么只有它给出的 \(m\) 条边,那么这个图一定是个二分图. 因为题目保证了原图可以被至多两个

(总计:共66题) 4.18~4.25:19题 4.26~5.2:17题 5.3~5.9: 6题 5.10~5.16: 6题 5.17~5.23: 9题 5.24~5.30: 9题 4.18 [BZOJ3786]星系探索(伪ETT) [BZOJ4337][BJOI2015]树的同构(树的最小表示法) [BZOJ3551][ONTAK2010]Peaks(加强版)(Kruskal重构树,主席树) [CTSC2017]游戏(Bayes定理,线段树) 4.19 [CTSC2017]吉夫特(Lucas定

BZOJ2683: 简单题(CDQ分治 + 树状数组) 题意: 你有一个\(N*N\)的棋盘,每个格子内有一个整数,初始时的时候全部为\(0\),现在需要维护两种操作: 命令 参数限制 内容 \(1\ x\ y\ A\) \(1\le x,y \le N\),A是正整数 将格子\(x,y\)里的数字加上\(A\) \(2\ x1\ y1\ x2\ y2\) \(1\le x1\le x2\le N,1\le y1\le y2\le N\) 输出\(x1\ y1\ x2\ y2\)这个矩形内的数字

Clarke and puzzle Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://hihocoder.com/contest/acmicpc2015beijingonline/problem/10 Description Kyle is a student of Programming Monkey Elementary School. Just as others, he is deeply concerned with his grad

Bitset简介 下面介绍C++ STL 中一个非常有用的东西: Bitset 类似于二进制状压,它可以把信息转化成一个01串存储起来 定义方法: 首先要#include<bitset>或#include<bits/stdc++.h> 然后定义一个长度为len的bitset S bitset<len>S; 一些操作 bitset还支持&,^,|三个运算 b._Find_first() 找到第一个1的位置 b._Find_next(x)找到x后面为1的第一个位置

题目链接 五维偏序,对每一维维护bitset,表示哪儿为1(比它大),然后5个bitset与起来就能得到答案了. 具体实现可以用5*n个bitset,按排名搞个前缀和. 复杂度\(O(n^2/w)\)(本质是暴力的优化). //1284ms 565MB #include <cstdio> #include <cctype> #include <bitset> #include <algorithm> #define gc() getchar() const

四维偏序.. 就是给你一个四维集合.再给你一些询问,请你求出a[i].x1<=ask.x1&&a[i].x2<=ask.x2&&a[i].x3<=ask.x3&&a[i].x4<=ask.x4的个数.. 集合大小<=30000 询问个数<=30000 然后怎么做呢?? 其实很简单只要排序+cdq+树状数组套平衡树什么的就行了 qnmd老子不会.. 这时! 神器来了! 那就是bitset! 众所周知,bitset能存一堆二进

------------更多Bitset的运用,请看这里http://www.cnblogs.com/hua-dong/p/8519739.html. 由于在学cdq分治,看到了这道题.先来看一道题目 (hihocoder1513): 问题:给出每个人(n<=100000)的五门学科成绩,求出所有人:五门学科名次都比自己靠前的同学的人数   学过cdq分治的应该知道,这就是个五维偏序,只要一维排序,二维分治,然后树套树套树就能轻松搞定了...去他妈的 请拉到最下面,先感受一下代码.开始的确想过用

链接:http://hihocoder.com/problemset/problem/1236 思路; 有n个五维的向量,给出q个询问,每个询问是一个五维向量,问有多少个向量没有一维比这个向量大.并且答案需要加密,除了第一个答案,其他答案都要和上一个答案异或. 因为是强制在线所以不能用cdq分治写..我们可以用stl里面的bitset来写这道题,但是因为数据还是太大了,这里我们可以用分块处理下,降低空间复杂度,需要用的时候直 接二分查找需要的块,预处理后可以o(1)获取前k-1个块的信息,然后我

题目链接 题意:给定n个五维空间上的点,以及m组询问,每组询问给出一个点,求五个维度都不大于它的点有多少个,强制在线. 神仙题 单独考虑每个维度,把所有点按这个维度上的大小排序,然后分成T块,每块用一个bitset记录这个块以及之前的块中包含的点的集合的前缀和,并用mx[i][j]来记录第i维上大小为j的点所对应的最右边的块.对于每个询问的点,也是单独考虑每个维度,找到每个维度上对应的块,把这个块之前的块的前缀和加上,然后再暴力加上这个块中所有当前维度不超过它的点,五个维度取个交集就行了. 预处

题目描述 给定一个有\(n\)个元素的序列,元素编号为\([1,n]\),每个元素有\(k\)个属性\(p_1,p_2,p_3,...,p_k\) ,求序列中满足 \(i<j\)且 \(1 \leq t \leq k\),\(p_{t,i}<p_{t,j}\) 的数对\((i,j)\)的个数. 输入格式 第一行两个整数 \(n\),\(k\),表示序列长度和属性个数. 接下来\(k\) 行,每行 \(n\)个整数,第\(t\) 行第 \(i\)个数表示\(p_{t,i}\) . 输出格式 共1

若干道偏序问题(STL,分块) 找了4道题目 BZOJ陌上花开(权限题,提供洛谷链接) Cogs2479偏序 Cogs2580偏序II Cogs2639偏序++ 作为一个正常人,肯定先看三维偏序 做法很多呀 首先,由于 智商不够数据结构来补 $       $--菊开 所以我们用最傻逼的数据结构来做这道题目 第一维:排序 第二维:树状数组 第三维:平衡树 于是乎,我们得到了一个复杂度为\(O(nlog^2n)\)的做法 并且常数巨大 这个做法到这里去看 第二种做法 CDQ分治 相信大家都会逆序对

Kyle is a student of Programming Monkey Elementary School. Just as others, he is deeply concerned with his grades. Last month, the school held an examination including five subjects, without any doubt, Kyle got a perfect score in every single subject

大意: n个人, 5门课, 给定每个人每门课的排名, 对于每个人输出有多少人5门课都比他差. 明显是个5维偏序问题, 题目有保证排名均不同, 可以用bitset优化为$O(\frac{n^2}{\omega})$ #include <iostream> #include <algorithm> #include <cstdio> #include <math.h> #include <set> #include <map> #incl