P4137 权值线段树 回滚莫队
题意
传送门 P4137 Rmq Problem / mex
题解
权值线段树
将查询离线,按照右界升序排序后依次处理。权值线段树维护每个元素出现的索引最大的位置,特别的,将 [ 0 , m a x n ) [0,maxn) [0,maxn) 初始化为 1 -1 1。那么对于查询 [ l , r ) [l,r) [l,r),答案为索引值小于 l l l 的最小值。总时间复杂度 O ( n log n ) O(nlog n) O(nlogn)。
#include
using namespace std;
#define pb push_back
const int MAXN = 2E5 + 5, SZ = 1 << 19;
int N, M, A[MAXN], res[MAXN];
struct Query
{
int l, r, id;
bool oper
共有 0 条评论