BZOJ2653: middle

 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 100000+5
14 #define maxm 5000000
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 for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
23 #define mod 1000000007
24 #define mid (l+r>>1)
25 #define lch ls[k],l,mid
26 #define rch rs[k],mid+1,r
27 using namespace std;
28 inline int read()
29 {
30     int x=0,f=1;char ch=getchar();
31     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
32     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}
33     return x*f;
34 }
35 struct seg{int lx,rx,sum;}t[maxm];
36 int n,tot,b[5],rt[maxn],ls[maxm],rs[maxm];
37 pa a[maxn];
38 inline void build(int &k,int l,int r)
39 {
40     if(!k)k=++tot;
41     t[k]=(seg){r-l+1,r-l+1,r-l+1};
42     if(l==r)return;
43     build(lch);build(rch);
44 }
45 inline seg operator +(seg l,seg r)
46 {
47     return (seg){max(l.lx,l.sum+r.lx),max(r.rx,r.sum+l.rx),l.sum+r.sum};
48 }
49 inline void update(int x,int &y,int l,int r,int z)
50 {
51     y=++tot;
52     if(l==r){t[y]=(seg){-1,-1,-1};return;}
53     ls[y]=ls[x];rs[y]=rs[x];
54     if(z<=mid)update(ls[x],ls[y],l,mid,z);
55     else update(rs[x],rs[y],mid+1,r,z);
56     t[y]=t[ls[y]]+t[rs[y]];
57 }
58 inline seg ask(int k,int l,int r,int x,int y)
59 {
60     if(x>y)return (seg){0,0,0};
61     if(l==x&&r==y)return t[k];
62     if(y<=mid)return ask(lch,x,y);
63     else if(x>mid)return ask(rch,x,y);
64     else return ask(lch,x,mid)+ask(rch,mid+1,y);
65 }
66 inline bool check(int x)
67 {
68     return ask(rt[x],1,n,b[1],b[2]).rx+ask(rt[x],1,n,b[2]+1,b[3]-1).sum+ask(rt[x],1,n,b[3],b[4]).lx>=0;
69 }
70 int main()
71 {
72     freopen("input.txt","r",stdin);
73     freopen("output.txt","w",stdout);
74     n=read();
75     for1(i,n)a[a[i].second=i].first=read();
76     sort(a+1,a+n+1);
77     build(rt[0],1,n);
78     for1(i,n)update(rt[i-1],rt[i],1,n,a[i].second);
79     int T=read(),ans=0;
80     while(T--)
81     {
82         for1(i,4)b[i]=(read()+ans)%n+1;
83         sort(b+1,b+4+1);
84         int l=1,r=n;
85         while(l<=r)if(check(mid-1))l=mid+1;else r=mid-1;
86         printf("%d\n",ans=a[r].first);
87     }
88     return 0;
89 }