可持久化线段树练习题
Bzoj 2653
题⽬描述：
⼀个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号，除法取下整。给你⼀个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间，右端点在[c,d]之间的⼦序列中，最⼤的中位数。
其中a < b < c < d。位置也从0开始标号。我会使⽤⼀些⽅式强制你在线。
#include <bits/stdc++.h>
using namespace std;
const int maxn=20007;
int a[maxn],n,q;
pair<int,int>ord[maxn];
struct node{
int lc,rc;
int sum,lmax,rmax;
}tree[maxn*22];
int head[maxn];
int sz=0;
int opt[4];
int newnode(){
++sz;
tree[sz].lc=tree[sz].rc=0;
return sz;
}
node Union(node a,node b){
node ret;
ret.sum=a.sum+b.sum;
ret.lmax=max(a.lmax,a.sum+b.lmax);
return ret;
}
void pushup(int u){
node tmp=Union(tree[tree[u].lc],tree[tree[u].rc]);
tree[u].sum=tmp.sum;
tree[u].lmax=tmp.lmax;
tree[u].ax;
}
void build(int u,int l,int r){
说法语的国家if(l==r){
tree[u].sum=tree[u].lmax=tree[u].rmax=1;
return;
}
int mid=(l+r)/2;
tree[u].lc=newnode();
tree[u].rc=newnode();
培训瑜伽教练
build(tree[u].lc,l,mid);
build(tree[u].rc,mid+1,r);
pushup(u);
quintus
}
void inrt(int u,int v,int l,int r,int x){
if(l==r){
tree[u].sum=-1;
tree[u].lmax=tree[u].rmax=0;
return;
}
int mid=(l+r)/2;
if(x<=mid){
as long as you love me歌词tree[u].rc=tree[v].rc;
tree[u].lc=newnode();
inrt(tree[u].lc,tree[v].lc,l,mid,x);
}
el {
tree[u].lc=tree[v].lc;
tree[u].lc=tree[v].lc;
tree[u].rc=newnode();
inrt(tree[u].rc,tree[v].rc,mid+1,r,x);
}
pushup(u);
}
node query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return tree[u];
int mid=(l+r)/2;
if(mid>=qr)return query(tree[u].lc,l,mid,ql,qr);
el if(mid<ql)return query(tree[u].rc,mid+1,r,ql,qr);
el {
return Union(query(tree[u].lc,l,mid,ql,qr),query(tree[u].rc,mid+1,r,ql,qr));
}
}
bool check(int x){
int sum=query(head[x],1,n,opt[0]+1,opt[1]).rmax
+query(head[x],1,n,opt[1]+1,opt[2]+1).sum
+query(head[x],1,n,opt[2]+2,opt[3]+1).lmax;
return sum>=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ord[i]=make_pair(a[i],i);
}
sort(ord+1,ord+1+n);
head[1]=newnode();
build(1,1,n);
for(int i=2;i<=n+1;i++){
head[i]=newnode();
inrt(head[i],head[i-1],1,n,ord[i-1].cond);
}
scanf("%d",&q);
int last=0;
while(q--){
for(int i=0;i<4;i++){
scanf("%d",&opt[i]);新东方精英英语官网
opt[i]=(opt[i]+last)%n;
}
sort(opt,opt+4);
int l=1,r=n,tag;
while(1){
if(r-l<=1){
if(check(r))tag=r;
el tag=l;
break;
}
int mid=(l+r)/2;
if(check(mid))l=mid;
el r=mid;
}
last=ord[tag].first;
printf("%d\n",last);
}
}
CF 484E
题⽬描述：
给⼀个数组，多次询问⼀个区间内所有长度为w的区间最⼩值的最⼤值。#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
const int maxn=100007;
int n,q;
int a[maxn];
pair<int,int>ord[maxn];
struct node{
int lc,rc;
int lmx,rmx,mx,len;
}tree[maxn*22];
int head[maxn];
int sz;
int newnode(){
return ++sz;
}
void pushup(int u){
int lc=tree[u].lc,rc=tree[u].rc;
tree[u].len=tree[lc].len+tree[rc].len;
tree[u].lmx=tree[lc].lmx==tree[lc].len?tree[lc].lmx+tree[rc].lmx:tree[lc].lmx; tree[u].rmx=tree[rc].rmx==tree[rc].len?tree[rc].rmx+tree[lc].rmx:tree[rc].rmx; tree[u].mx=max(tree[lc].mx,max(tree[rc].mx,tree[lc].rmx+tree[rc].lmx));
人才培养 英语}
void build(int u,int l,int r){
if(l==r){
tree[u].lmx=tree[u].rmx=tree[u].mx=tree[u].len=1;
return ;
}
tree[u].lc=newnode();
tree[u].rc=newnode();
int mid=(l+r)/2;
build(tree[u].lc,l,mid);
build(tree[u].rc,mid+1,r);
pushup(u);
kewpie
}
void inrt(int u,int v,int l,int r,int x){
if(l==r){
tree[u].lmx=tree[u].rmx=tree[u].mx=0;
tree[u].len=1;
return ;
boxi}
int mid=(l+r)/2;
if(mid>=x){
tree[u].rc=tree[v].rc;
tree[u].lc=newnode();
inrt(tree[u].lc,tree[v].lc,l,mid,x);
}
el {
tree[u].lc=tree[v].lc;
tree[u].rc=newnode();
inrt(tree[u].rc,tree[v].rc,mid+1,r,x);
}
pushup(u);
}
struct atom{
int lmx,rmx,mx,len;
};
atom operator+(const atom& a,const atom& b){
atom ret;
ret.len=a.len+b.len;
ret.lmx=a.lmx==a.len?a.lmx+b.lmx:a.lmx;
<=b.rmx==b.+a.;
<=,,a.rmx+b.lmx));
return ret;
}
atom query(int u,int l,int r,int ql,int qr){
if(ql>r||qr<l)return (atom){0,0,0,0};
if(ql>r||qr<l)return (atom){0,0,0,0};
if(ql<=l&&r<=qr){
return (atom){tree[u].lmx,tree[u].rmx,tree[u].mx,tree[u].len}; }
int mid=(l+r)/2;
return query(tree[u].lc,l,mid,ql,qr)+query(tree[u].rc,mid+1,r,ql,qr); }
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);boolean
ord[i]=make_pair(a[i],i);
}
sort(ord+1,ord+1+n);
build(head[1]=newnode(),1,n);
for(int i=2;i<=n;i++){
inrt(head[i]=newnode(),head[i-1],1,n,ord[i-1].cond);
}
scanf("%d",&q);
while(q--){
int l,r,w;
scanf("%d%d%d",&l,&r,&w);
int dn=1,up=n,tag;
while(1){
if(up-dn<=1){
if(query(head[up],1,n,l,r).mx>=w)tag=up;
el tag=dn;
break;
}
int mid=(up+dn)/2;
autoclaveif(query(head[mid],1,n,l,r).mx>=w)dn=mid;
el up=mid;
}
printf("%d\n",ord[tag].first);
}
}
