CF484E Sign on Fence
#include<bits/stdc++.h>
#define RG register
#define IL inline
#define _ 100100
#define inf 1e9+7
using namespace std;
IL int gi(){
RG int data = 0 , m = 1; RG char ch = 0;
while(ch != '-' && (ch<'0' || ch > '9')) ch = getchar();
if(ch == '-'){m = 0; ch = getchar();}
while(ch>='0' && ch<='9'){data = (data<<1) + (data<<3) + ch - '0' ; ch = getchar();}
return (m) ? data : -data ;
}
struct Num{
int h,p;
bool operator < (const Num & B) const{
return h < B.h ;
}
}I[_] ;
int n,X[_],xox,L,R,ret,Q,rt[_],tot;
struct Result{
int lx,rx,Ex,sum; bool jd;
IL void Mem(int d){lx = rx = Ex = sum = d; jd = (d ^ 1) ; }
}; Result Ans ;
struct Node{int ls,rs; Result E; }t[20*_];
Result operator + (Result A,Result B){
RG Result C;
C.Ex = max(A.Ex ,B.Ex) ;
C.lx = A.lx; C.rx = B.rx ;
if(!A.jd)C.lx = A.sum + B.lx;
if(!B.jd)C.rx = B.sum + A.rx;
C.sum = A.sum + B.sum ;
C.jd = ( A.jd | B.jd );
C.Ex = max(A.rx + B.lx , C.Ex) ;
return C ;
}
void Build(int &o,int l,int r){
o = ++ tot;
if(l == r){t[o].E.Mem(0) ; return ; }
RG int mid = (l + r) >> 1;
Build(t[o].ls , l , mid) ; Build(t[o].rs , mid + 1 , r) ;
t[o].E = t[t[o].ls].E + t[t[o].rs].E ;
}
void Update(int &o,int l,int r,int p){
t[++tot] = t[o]; o = tot ;
if(l == r){t[o].E.Mem(1) ; return ; }
RG int mid = (l + r) >> 1;
if(p <= mid) Update(t[o].ls , l , mid , p) ;
else if(p > mid) Update(t[o].rs , mid + 1 , r , p) ;
t[o].E = t[t[o].ls].E + t[t[o].rs].E ;
}
Result Query(int o,int l,int r,int ql,int qr){
if(ql == l && r == qr)return t[o].E ;
RG int mid = (l + r) >> 1;
if(qr <= mid) return Query(t[o].ls,l,mid,ql,qr) ;
else if(ql > mid) return Query(t[o].rs,mid+1,r,ql,qr) ;
else return Query(t[o].ls,l,mid,ql,mid) + Query(t[o].rs,mid+1,r,mid+1,qr) ;
}
int main(){
n = gi() ;
for(RG int i = 1; i <= n; i ++) I[i].h = gi() , I[i].p = i ;
sort(I + 1 , I + n + 1) ;
for(RG int i = 1; i <= n; i ++) X[i] = I[i].h ;
xox = unique(X + 1, X + n + 1) - X - 1 ;
for(RG int i = 1; i <= n; i ++)
I[i].h = lower_bound(X + 1 , X + xox + 1 , I[i].h) - X ;
Build(rt[n+1] , 1 , n) ;
for(RG int i = n; i >= 1; i --)
rt[i] = rt[i+1] , Update(rt[i] , 1 , n , I[i].p) ;
Q = gi() ;
while(Q--){
RG int qL = gi() , qR = gi() , qK = gi() ;
//cout << "Query [" << qL << "," << qR << "] k="<<qK<<endl;
L = 1; R = n; ret = 0;
while(L <= R){
RG int mid = (L + R) >> 1;
Ans = Query(rt[mid] , 1 , n , qL , qR) ;
if(Ans.Ex >= qK){ret = mid; L = mid + 1;}
else R = mid - 1;
}
printf("%d\n" , X[I[ret].h]) ;
}return 0;
}
[国家集训队]middle
#include<bits/stdc++.h>
#define RG register
#define IL inline
#define _ 25005
#define inf 1e9+7
using namespace std;
IL int gi(){
RG int data = 0 , m = 1; RG char ch = 0;
while(ch != '-' && (ch<'0' || ch > '9')) ch = getchar();
if(ch == '-'){m = 0; ch = getchar();}
while(ch>='0' && ch<='9'){data = (data<<1) + (data<<3) + ch - '0' ; ch = getchar();}
return (m) ? data : -data ;
}
struct Result{int sum,ls,rs,lm,rm; }t[20*_] , Set ;
int n,m,a[_],X[_],xox,tot,ans,Q,A,B,C,D,rt[_]; struct Num{int d,p;}num[_] ;
IL void PushUp(int o){
RG int lc = t[o].ls , rc = t[o].rs ;
t[o].sum = t[lc].sum + t[rc].sum ;
t[o].lm = max(t[lc].lm , t[lc].sum + t[rc].lm) ;
t[o].rm = max(t[rc].rm , t[rc].sum + t[lc].rm) ;
}
void Mem(int &o,int l,int r){
o = ++ tot ;
if(l == r) { t[o].lm = t[o].rm = t[o].sum = 1; return ;}
RG int mid = (l + r) >> 1;
Mem(t[o].ls , l , mid) ; Mem(t[o].rs , mid + 1 , r) ;
PushUp(o) ;
}
void Build(int &o,int l,int r,int ps){
t[++tot] = t[o]; o = tot ;
if(l == r){ t[o].lm = t[o].rm = t[o].sum = -1; return ; }
RG int mid = (l + r) >> 1;
if(ps <= mid) Build(t[o].ls , l , mid , ps) ;
else if(ps > mid) Build(t[o].rs , mid + 1 , r , ps) ;
PushUp(o) ;
}
IL Result Merge(Result AA , Result BB){
Result CC ;
CC.sum = AA.sum + BB.sum ;
CC.lm = max(AA.lm , AA.sum + BB.lm) ;
CC.rm = max(BB.rm , BB.sum + AA.rm) ;
return CC ;
}
Result Query(int o,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) {
Result Tmp = (Result){t[o].sum , 0 , 0 , t[o].lm , t[o].rm } ;
return Tmp ;
}
RG int mid = (l + r) >> 1;
if(qr <= mid) {return Query(t[o].ls , l , mid , ql , qr) ; }
else if(ql > mid) return Query(t[o].rs , mid + 1 , r , ql , qr) ;
else return
Merge(Query(t[o].ls , l , mid , ql , mid) , Query(t[o].rs , mid+1 , r , mid+1 , qr)) ;
}
IL bool cmp(Num AA,Num BB){return AA.d < BB.d ; }
int main(){
n = gi(); xox = 0;
for(RG int i = 1; i <= n; i ++)
X[++xox] = num[i].d = gi() , num[i].p = i;
sort(X + 1 , X + xox + 1) ;
xox = unique(X + 1 , X + xox + 1) - X - 1 ;
for(RG int i = 1; i <= n; i ++)
num[i].d = lower_bound(X + 1 , X + xox + 1 , num[i].d) - X;
sort(num + 1 , num + n + 1 , cmp) ;
Mem(rt[1] , 1 , n) ;
for(RG int i = 2; i <= n; i ++){
rt[i] = rt[i - 1] ;
Build(rt[i] , 1 , n , num[i-1].p) ;
}
ans = 0; Q = gi() ; RG int tmp[4] ;
while(Q --){
A = gi(); B = gi(); C = gi(); D = gi() ;
tmp[0] = (A + ans) % n + 1; tmp[1] = (B + ans) % n + 1;
tmp[2] = (C + ans) % n + 1; tmp[3] = (D + ans) % n + 1;
sort(tmp , tmp + 4) ;
A = tmp[0] ; B = tmp[1] ;
C = tmp[2] ; D = tmp[3] ;
//cout << " Query ["<<A<<","<<B<<"] && [" <<C<<","<<D<<"]"<<endl;
RG int ret = 0 , Data , L = 1 , R = n ;
while(L <= R){
RG int mid = (L + R) >> 1;
if(B+1 <= C-1)Data = ( Query(rt[mid] , 1 , n , B+1 , C-1).sum ) ;
else Data = 0;
Set = Query(rt[mid] , 1 , n , A , B) ;
Data += Set.rm ;
//cout <<"mid="<<mid<<" "<<" Set.rm = " <<Set.rm<<endl;
Set = Query(rt[mid] , 1 , n , C , D) ;
Data += Set.lm ;
if(Data >= 0){ret = num[mid].d; L = mid + 1; }
else R = mid - 1;
}
ans = X[ret] ;
printf("%d\n" , ans) ;
}return 0;
}