# Bzoj 2653: middle

Q行依次给出询问的答案。

5

170337785

271451044

22430280

969056313

206452321

3

3 1 0 2

2 3 1 4

3 1 4 0

271451044

271451044

969056313

#### HINT

n<=20000,Q<=25000

```  1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 #include<iostream>
5 #include<cmath>
6 using namespace std;
7 struct node{
8     int id,val;
9     friend bool operator <(const node &a,const node &b){
10         return a.val<b.val;
11     }
12 }in[20010];
13 struct seg{int lson,rson,sum,ll,rr;}tree[400010];
14 int q[4],root[20010],st,ed,n,ans,fz,cnt=1;
15 void merge(seg &pos,seg &lson,seg &rson){
16     pos.ll=max(lson.ll,lson.sum+rson.ll);
17     pos.rr=max(rson.rr,rson.sum+lson.rr);
18     pos.sum=lson.sum+rson.sum;
19     return;
20 }
21 void build(int l,int r,int pos){
22     tree[pos].ll=tree[pos].rr=tree[pos].sum=r-l+1;
23     if(l==r) return;
24     int mid=(l+r)/2;
25     tree[pos].lson=++cnt;
26     tree[pos].rson=++cnt;
27     build(l,mid,tree[pos].lson);
28     build(mid+1,r,tree[pos].rson);
29     return;
30 }
31 void insert(int l,int r,int pos,int las){
32     if(l==r){
33         tree[pos].ll=tree[pos].rr=tree[pos].sum=-1;
34         return;
35     }
36     int mid=(l+r)/2;
37     if(st<=mid){
38         tree[pos].lson=++cnt;
39         tree[pos].rson=tree[las].rson;
40         insert(l,mid,tree[pos].lson,tree[las].lson);
41     }
42     else{
43         tree[pos].rson=++cnt;
44         tree[pos].lson=tree[las].lson;
45         insert(mid+1,r,tree[pos].rson,tree[las].rson);
46     }
47     merge(tree[pos],tree[tree[pos].lson],tree[tree[pos].rson]);
48     return;
49 }
50 int find(int l,int r,int pos){
51     if(st<=l&&r<=ed) return tree[pos].sum;
52     int mid=(l+r)/2;
53     if(ed<=mid) return find(l,mid,tree[pos].lson);
54     if(mid<st) return find(mid+1,r,tree[pos].rson);
55     return find(l,mid,tree[pos].lson)+find(mid+1,r,tree[pos].rson);
56 }
57 void findl(int l,int r,int pos){
58      if(st<=l&&r<=ed){
59          ans=max(ans,fz+tree[pos].rr);
60          fz+=tree[pos].sum;
61          return;
62      }
63      int mid=(l+r)/2;
64      if(mid<ed) findl(mid+1,r,tree[pos].rson);
65      if(st<=mid) findl(l,mid,tree[pos].lson);
66      return;
67 }
68 void findr(int l,int r,int pos){
69     if(st<=l&&r<=ed){
70         ans=max(ans,fz+tree[pos].ll);
71         fz+=tree[pos].sum;
72         return;
73     }
74     int mid=(l+r)/2;
75     if(st<=mid) findr(l,mid,tree[pos].lson);
76     if(mid<ed) findr(mid+1,r,tree[pos].rson);
77     return;
78 }
79 int erfen(){
80     int l=0,r=n+1,mid,val;
81     while(l<r){
82         mid=(l+r)/2;
83         st=q[1],ed=q[2];
84         if(st<=ed) val=find(1,n,root[mid]);
85         else val=0;
86         st=q[0],ed=q[1]-1,ans=fz=0;
87         if(st<=ed) findl(1,n,root[mid]);
88         val+=ans;
89         st=q[2]+1,ed=q[3],ans=fz=0;
90         if(st<=ed) findr(1,n,root[mid]);
91         val+=ans;
92         if(val>=0) l=mid+1;
93         else r=mid;
94     }
95     printf("%d\n",in[l].val);
96     return in[l].val;
97 }
98 int main()
99 {
100     int m,i,las=0;
101     scanf("%d",&n);
102     for(i=1;i<=n;i++){
103         scanf("%d",&in[i].val);
104         in[i].id=i;
105     }
106     sort(in+1,in+n+1);
107     root[0]=1;
108     build(1,n,1);
109     for(i=1;i<=n;i++){
110         root[i]=++cnt;
111         st=in[i].id;
112         insert(1,n,root[i],root[i-1]);
113     }
114     scanf("%d",&m);
115     for(i=1;i<=m;i++){
116         scanf("%d%d%d%d",&q[0],&q[1],&q[2],&q[3]);
117         q[0]=(q[0]+las)%n+1,q[1]=(q[1]+las)%n+1;
118         q[2]=(q[2]+las)%n+1,q[3]=(q[3]+las)%n+1;
119         sort(q,q+4);
120         las=erfen();
121     }
122     return 0;
123 }```

Bzoj 2653: middle

(0)
(0)

0条