11
2016-09
2016-09
HDU 5875 Function (RMQ+二分)
题目链接：点我~~
题意：给出a1~an,和 q 个询问 [i,j] 表示询问 aimod…aj 的值。
思路：每次找到下一个不超过当前余数的数。用RMQ记录区间最小的数。因为每次余数减少至少一半，复杂度应该是 O(q*logn*logAi).
#include <bits/stdc++.h>
using namespace std...
09月11日
2,341
20
2016-07
2016-07
HDU 5726 GCD (RMQ+二分)
题目链接：点我~~
题意：给你n个数，m个询问，每次询问某个区间，求这段区间所有数的gcd，然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~
思路：对于求区间gcd可以用线段树维护，或者RMQ，因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd，考虑枚举左端点，二分区间进行预处理~例如12467，以1为左端点，1~5为右端点5个...
07月20日
2,297
20
2016-07
2016-07
HDU 5289 Assignment (RMQ+二分)
题意：求存在最大差值小于给定K值的区间段个数。
思路：利用RMQ求出区间最大最小值，再枚举右端点，二分区间找到满足要求的最大区间累加~~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
t...
07月20日
2,272
16
2016-03
2016-03
RMQ 一维模板
void intRMQ(int n,int b[])
{
mm[0]=-1;
for(int i=1; i<=n; ++i)
{
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
//计算长度 n为2的倍数 n&n-1==...
03月16日
2,311