tyvj4866 摆摊 线段树MEX

tyvj4866 摆摊 线段树MEX

​​在zhx的代码帮助下理解了这个内容 我不知道自己这么低的智商未来会不会有出路

有一些必要的解释，放在了程序中

next[i][0]表示 在序列a中下标为i+1到m中最近一次出现a[i]-1的位置

关于这个线段树的使用

线段树其实我们是查找截至到右端点，我们现在可用的最小值

我每次处理l的时候 在l+1到min(next[l][1],next[l][2])之间 都可以使用a[l]这个地方

官方的题解：

100分做法： 记 nxt(x,y) 为下标从 x+1 开始 a 数组第一次出现 y 这个数字的位置。 离线处理这个问题，考虑 L 从 1 到 M 扫过去，在扫过去的同时维护 R 等于 L 到 M 的答案。 然后把询问也按照 L 排序，就可以在 L 扫过去的过程依次回答询问。 L=1 的时候，可以暴力处理出来 R 等于每个值的答案。 然后 L 每次 +1。 L 从 x 变成 x+1 的过程，对于维护 R 等于 x+1 到 M 的答案来 说，变化是少了 a[x] 这一个数字，对于 R>=nxt(x,a[x]) 的数字是没有影 响的。对于 R 在 x 到 min(nxt(x,a[x]),nxt(x,a[x]+1)) 之间的答案由于 a[x] 被去掉，并且也没有 a[x]+1 这个数字，a[x] 在这一段就是一个可能的答 案 (换句话说 R 在这些位置的答案应该和 a[x] 取 min);对于 R 在 x 到 min(nxt(x,a[x]),nxt(x,a[x]-1)) 之间的答案由于 a[x] 被去掉，并且没有 a[x]-1 这个数字，a[x]-1 在这一段就是一个可能的答案 (换句话说 R 在这些位置的 答案应该和 a[x]-1 取 min)。发现去掉 a[x] 并没有其他影响。 nxt(x,a[x]),nxt(x,a[x]+1),nxt(x,a[x]-1) 可以 O(n) 预处理。

#include#include#define N 220000#define inf 0x7f7f7f7fstruct node{ int l,r,id;}q[N];struct node1{ int l,r,left,right,min;}tree[N<<2];inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline bool cmp(node a,node b){return a.l>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); //update(x);}void insert1(int x,int l,int r,int v){ if (l<=tree[x].l&&r>=tree[x].r){tree[x].min=min(tree[x].min,v);return;} int mid=tree[x].l+tree[x].r>>1; if (l<=mid) insert1(tree[x].left,l,r,v); if (r>mid) insert1(tree[x].right,l,r,v); //update(x);}int query(int x,int l){ if (tree[x].l==tree[x].r) return tree[x].min; int mid=tree[x].l+tree[x].r>>1;int min1=tree[x].min; if (l<=mid) min1=min(min1,query(tree[x].left,l)); if (l>mid) min1=min(min1,query(tree[x].right,l)); return min1;}void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d %d\n",tree[x].l,tree[x].r,tree[x].min); if (tree[x].right) print(tree[x].right);}int main(){ freopen("stall.in","r",stdin); n=read();m=read();q1=read();int tmp=1; for (int i=1;i<=m;++i) { a[i]=read(),last[i]=m+1;map[a[i]]=true; while (map[tmp]||map[tmp+1]) ++tmp; mex[i]=tmp;//表示已经放了前i个 然后我最好的答案可以取在哪里 } //for (int i=1;i<=m;++i) printf("%d,mex[i]); for (int i=m;i>=1;--i){ next[i][0]=last[a[i]-1];next[i][1]=last[a[i]];next[i][2]=last[a[i]+1];last[a[i]]=i; } for (int i=1;i<=q1;++i) q[i].l=read(),q[i].r=read(),q[i].id=i; std::sort(q+1,q+q1+1,cmp); build(root,1,m);int l=1;//printf("asdf%d,tree[root].min); for (int i=1;i<=q1;++i){ while(l=1) insert1(root,l+1,min(next[l][1],next[l][0])-1,a[l]-1);++l; } // print(root);printf("asdfasd\n"); ans[q[i].id]=query(root,q[i].r); } for (int i=1;i<=q1;++i) printf("%d %d\n",ans[i],ans[i]+1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。