BZOJ3339: Rmq Problem

3339: Rmq Problem

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 545 Solved: 261
[Submit][Status]

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

Source

By Xhr

题解：

xhr的题看起来就很神。。。

因为在线好像是不可做的，所以我们离线做。

然后搬运题解。。。hzwer

首先按照左端点将询问排序

然后一般可以这样考虑

首先如何得到1-i的sg值呢

这个可以一开始扫一遍完成

接着考虑l-r和l+1-r的答案有何不同

显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]

这一步如果暴力修改的话只有30分

但是修改区间我们可以想到线段树，这样就能a了

orz!!!!

代码：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #include<string>
12 #define inf 1000000000
13 #define maxn 250000+5
14 #define maxm 500+100
15 #define eps 1e-10
16 #define ll long long
17 #define pa pair<int,int>
18 #define for0(i,n) for(int i=0;i<=(n);i++)
19 #define for1(i,n) for(int i=1;i<=(n);i++)
20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
22 #define mod 1000000007
23 using namespace std;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
28     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 int n,m,a[maxn],v[maxn],sg[maxn],next[maxn],ans[maxn];
32 struct seg{int l,r,mi;}t[4*maxn];
33 struct rec{int l,r,id;}c[maxn];
34 inline void build(int k,int l,int r)
35 {
36     t[k].l=l;t[k].r=r;int mid=(l+r)>>1;
37     t[k].mi=inf;
38     if(l==r){t[k].mi=sg[l];return;}
39     build(k<<1,l,mid);build(k<<1|1,mid+1,r);
40 }
41 inline void update(int k,int z)
42 {
43     t[k].mi=min(t[k].mi,z);
44 }
45 inline void pushdown(int k)
46 {
47     if(t[k].mi==inf)return;
48     update(k<<1,t[k].mi);
49     update(k<<1|1,t[k].mi);
50     t[k].mi=inf;
51 }
52 inline void change(int k,int x,int y,int z)
53 {
54     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
55     if(l==x&&r==y){update(k,z);return;}
56     pushdown(k);
57     if(y<=mid)change(k<<1,x,y,z);
58     else if(x>mid)change(k<<1|1,x,y,z);
59     else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z);
60 }
61 inline int query(int k,int x)
62 {
63     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
64     if(l==r)return t[k].mi;
65     pushdown(k);
66     if(x<=mid)return query(k<<1,x);else return query(k<<1|1,x);
67 }
68 inline bool cmp(rec x,rec y){return x.l<y.l;}
69 int main()
70 {
71     freopen("input.txt","r",stdin);
72     freopen("output.txt","w",stdout);
73     n=read();m=read();int k=0;
74     for1(i,n)
75     {
76         a[i]=read();
77         v[a[i]]=1;
78         if(a[i]==k){while(v[k])k++;}
79         sg[i]=k;
80     }
81     memset(v,0,sizeof(v));
82     build(1,1,n);
83     for1(i,m)c[i].l=read(),c[i].r=read(),c[i].id=i;
84     sort(c+1,c+m+1,cmp);
85     for3(i,n,1)next[i]=v[a[i]],v[a[i]]=i;
86     int now=1;
87     for1(i,m)
88     {
89         while(now<c[i].l)
90         {
91             if(!next[now])next[now]=n+1;
92             if(next[now]-1>=now+1)change(1,now+1,next[now]-1,a[now]);
93             now++;
94         }
95         ans[c[i].id]=query(1,c[i].r);
96     }
97     for1(i,m)printf("%d
",ans[i]);
98     return 0;
99 }

View Code