「BZOJ3339」Rmq Problem
Description
Input
Output
Sample Input
7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
Sample Output
3
0
3
2
4
0
3
2
4
HINT
题解
这一题在线似乎比较麻烦
至于离线。。
首先按照左端点将询问排序
然后一般可以这样考虑
首先如何得到1-i的sg值呢
这个可以一开始扫一遍完成
接着考虑l-r和l+1-r的答案有何不同
显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]
这一步如果暴力修改的话只有30分
但是修改区间我们可以想到线段树，这样就能a了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<iostream> #include<cstdio> #include<algorithm> #define inf 0x7fffffff using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,k=0; int a[200005],sg[200005],ans[200005],next[200005],last[200005]; int ls[600005],rs[600005],mn[600005]; bool mark[200001]; struct data{int l,r,id;}q[200005]; bool cmp(data a,data b) {return a.l<b.l;} void build(int k,int l,int r) { ls[k]=l;rs[k]=r;mn[k]=inf; if(l==r){mn[k]=sg[l];return;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void pushdown(int k) { int l=ls[k],r=rs[k]; if(l==r)return; mn[k<<1]=min(mn[k],mn[k<<1]); mn[k<<1|1]=min(mn[k],mn[k<<1|1]); } int ask(int k,int x) { if(mn[k]!=inf)pushdown(k); int l=ls[k],r=rs[k]; if(l==r)return mn[k]; int mid=(l+r)>>1; if(x<=mid)return ask(k<<1,x); return ask(k<<1|1,x); } void update(int k,int x,int y,int val) { if(mn[k]!=inf)pushdown(k); int l=ls[k],r=rs[k]; if(l==x&&y==r){mn[k]=min(mn[k],val);return;} int mid=(l+r)>>1; if(y<=mid)update(k<<1,x,y,val); else if(x>mid)update(k<<1|1,x,y,val); else {update(k<<1,x,mid,val);update(k<<1|1,mid+1,y,val);} } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { mark[a[i]]=1; if(a[i]==k) while(mark[k])k++; sg[i]=k; } build(1,1,n); for(int i=n;i>0;i--) next[i]=last[a[i]],last[a[i]]=i; for(int i=1;i<=m;i++) { q[i].l=read();q[i].r=read(); q[i].id=i; } sort(q+1,q+m+1,cmp); int now=1; for(int i=1;i<=m;i++) { while(now<q[i].l) { if(!next[now])next[now]=n+1; update(1,now,next[now]-1,a[now]); now++; } ans[q[i].id]=ask(1,q[i].r); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; } |
计数器 9302629
OI 课件=>
OI 课件=>
[…] 本弱上去讲个mex，刷刷存在感，结果上台就不知道自己口胡什么鬼了，我错了大家没听懂不要打我，可以看看http://hzwer.com/3032.html […]