bzoj3339：rmqproblem&bzoj3585&洛谷4137：mex——题解(代码片段)

关键词：

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=4e5+5;
inline int read()
    int X=0,w=0;char ch=0;
    while(!isdigit(ch))w|=ch==\'-\';ch=getchar();
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;

struct node
    int l,r,min;
tr[N*20];
int rt[N],pool,n,m,q,b[N],a[N];
inline void LSH()
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+m+1,a[i])-b;

void insert(int y,int &x,int l,int r,int p,int v)
    tr[x=++pool]=tr[y];
    if(l==r)
    tr[x].min=v;
    return;
    
    int mid=(l+r)>>1;
    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,v);
    else insert(tr[y].r,tr[x].r,mid+1,r,p,v);
    tr[x].min=min(tr[tr[x].l].min,tr[tr[x].r].min);

int query(int x,int l,int r,int v)
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(tr[tr[x].l].min<v)return query(tr[x].l,l,mid,v);
    else return query(tr[x].r,mid+1,r,v);

int main()
    n=read(),q=read();
    b[++m]=0;
    for(int i=1;i<=n;i++)
    a[i]=b[++m]=read();
    b[++m]=a[i]+1;
    
    LSH();
    for(int i=1;i<=n;i++)insert(rt[i-1],rt[i],1,m,a[i],i);
    for(int i=1;i<=q;i++)
    int l=read(),r=read();
    printf("%d\\n",b[query(rt[r],1,m,l)]);
    
    return 0;

bzoj_3585_mex&&bzoj_3339_rmqproblem_主席树

BZOJ_3585_mex&&BZOJ_3339_RmqProblem_主席树Description　　有一个长度为n的数组a1,a2,...,an。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。　　第二行为n个数。　　从第三行开始，每行一个询问l,r。Output... 查看详情

bzoj3339：rmqproblem&bzoj3585&洛谷4137：mex——题解(代码片段)

前者：https://www.lydsy.com/JudgeOnline/problem.php?id=3339后者：https://www.lydsy.com/JudgeOnline/problem.php?id=3585https://www.luogu.org/problemnew/show/P4137有一个长度为n的数组a1,a2,…,an。m次询问，每次询问一个区间内最 查看详情

bzoj3585:mex&&3339:rmqproblem--主席树

3585:mexTimeLimit: 20Sec  MemoryLimit: 128MBDescription　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。Input　　第一行n,m。　　第二行为n个数。　　从第三行开始，每行一个询... 查看详情

bzoj3339:rmqproblem

3339:RmqProblemTimeLimit: 20Sec  MemoryLimit: 128MBSubmit: 1270  Solved: 666[Submit][Status][Discuss]DescriptionInputOutputSampleInput7502101321323143627SampleO 查看详情

bzoj3339rmqproblem

【bzoj3339】RmqProblem DescriptionInputOutputSampleInput7502101321323143627SampleOutput30324HINT分析离线算法。对于[l,r]区间的询问，我们可以线性求出来，然后考虑[l+1,r]区间有什么不同，在a[l]下一次出现的位置之前，所有大于a[l]的mex，都变成... 查看详情

bzoj3339:rmqproblem(代码片段)

【传送门：BZOJ3339】简要题意：　　给出一个长度为n的数列，有m个询问，每个询问输入l,r，求出l到r之间没出现过的最小自然数题解：　　同BZOJ3585参考代码：#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm&g... 查看详情

bzoj3339rmqproblem

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3339【题解】业界偷懒。突然发现好像可以主席树啊。。然后就强行上了一波发现确实可以。第i棵主席树维护[1...i]这个前缀内，某权值区间的“最小出现位置”。比如2301那么在rt[4]这... 查看详情

bzoj-3339:rmqbzoj-3585:mex

 3339:RmqProblem3585:mex题解：分块维护权值，用莫队转移。分块修改操作$O(1)$，查询$O(sqrt{A_{max}})$。莫队转移$O(msqrtn)$。总共是$O(msqrtn)$一份代码解决两道题。额外的经验！1#include<cmath>2#include<algorithm>3#include<cstdio>4 查看详情

bzoj3339&&bzoj3585莫队+权值分块

 显然若一个数大于n就不可能是答案。12#include<iostream>3#include<cstring>4#include<cstdio>5#include<algorithm>6#include<map>7#include<cmath>8usingnamespacestd;9constintMaxn=200 查看详情

rmqproblem

大视野——3339:RmqProblemTimeLimit: 20Sec  MemoryLimit: 128MBSubmit: 1192  Solved: 620[Submit][Status][Discuss]DescriptionInputOutputSampleInput750210132 查看详情

[bzoj3585][bzoj3339]mex

[BZOJ3585][BZOJ3339]mex试题描述有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。输入第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r。输出一行一个数，表示每个询问的答案。... 查看详情

bzoj3339

线段树+离线这种题既可以用莫队做也可以用线段树做，跟hh的项链差不多首先我们处里出前缀mex，也就是1->i的mex值，再预处理出每个数下一次出现的位置，然后把每个前缀mex插入线段树，每个节点表示l==r表示1->l的mex，然后... 查看详情

bzoj1477&&exgcd学习笔记

exgcd由于忘记了exgcd,这道题就没做出来。。。exgcd的用处是求ax+by=gcd(a,b)这样方程的解大概是这个样子的voidext_gcd(longlonga,longlongb,longlong&x,longlong&y){if(b==0){x=1;y=0;}else{ext_gcd(b,a%b,y,x);y-=x*(a/b);}}ViewCode证明大概是ax+b 查看详情

luogu4137：rmqproblem/mex

题面传送门Sol这题可能是假的离线莫队搞一搞，把数字再分块搞一搞，就行了#include<bits/stdc++.h>#defineILinline#defineRGregister#defineFill(a,b)memset(a,b,sizeof(a))usingnamespacestd;typedeflonglongll;constint_(2e5+5);ILllInput(){R 查看详情

bzoj1061&&bzoj3256

http://www.lydsy.com/JudgeOnline/problem.php?id=1061单纯形。。。先开始我不知道对偶，看着代码不知所措，并不能懂他们写的是什么。。。单纯形的标准形式是uoj上那样的，限制小于，最大化，但是这道题是最小化，而且系数取负还不行... 查看详情

bzoj3550:[ontak2010]vacation&&bzoj3112:[zjoi2013]防守战线(代码片段)

学了下单纯形法解线性规划看起来好像并不是特别难，第二个code有注释。我还有...*=-....这个不是特别懂第一个是正常的，第二个是解对偶问题的#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algor... 查看详情

bzoj2242计算器

1#include<bits/stdc++.h>2#defineinf10000000003usingnamespacestd;4typedeflonglongll;5intgcd(inta,intb){returnb==0?a:gcd(b,a%b);}6voidexgcd(inta,intb,int&x,int&y){7if(b==0){x=1;y=0;return; 查看详情

bzoj3585:mex|莫队算法

...;n的数就可以了因为大于n的数对答案肯定没有影响代码与BZOJ3339完全一样……似有又水了一题#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<queue>#include<vector>#include<set>#include<map>#include... 查看详情