| 记录编号 |
357327 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
1594.[模板]平衡树(树套树) |
最终得分 |
100 |
| 用户昵称 |
 Cydiater |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.787 s |
| 提交时间 |
2016-12-10 16:33:12 |
内存使用 |
39.61 MiB |
显示代码纯文本
//BZOJ 3196
//by Cydiater
//2016.12.10
#include <iostream>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define FILE "psh"
const int MAXN=5e4+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,root[MAXN<<1],arr[MAXN],fsort[MAXN<<1],rnum,cnt=0,top[2],preL[MAXN],preR[MAXN],tmpL[MAXN],tmpR[MAXN],TMP;
struct Chair_man_Tree{
int son[2],sum;
}t[MAXN<<6];
struct Query{
int opt,L,R,pos,K;
}query[MAXN];
namespace solution{
inline int lowbit(int i){return ((i)&(-i));}
int NewNode(int sum,int son0,int son1){
t[++cnt].sum=sum;t[cnt].son[0]=son0;t[cnt].son[1]=son1;
return cnt;
}
void insert(int leftt,int rightt,int &Root,int last,int pos){
Root=NewNode(t[last].sum+1,t[last].son[0],t[last].son[1]);
int mid=(leftt+rightt)>>1;
if(leftt==rightt) return;
if(pos<=mid) insert(leftt,mid,t[Root].son[0],t[last].son[0],pos);
else insert(mid+1,rightt,t[Root].son[1],t[last].son[1],pos);
}
void PushTree(int L,int R){
top[0]=top[1]=0;
preL[++top[0]]=root[(L-1==0?0:(N+L-1))];
preR[++top[1]]=root[R+N];
for(int j=L-1;j>=1;j-=lowbit(j)) preL[++top[0]]=root[j];
for(int j=R;j>=1;j-=lowbit(j)) preR[++top[1]]=root[j];
}
void ChooseLeft(){
up(i,1,top[0])preL[i]=t[preL[i]].son[0];
up(i,1,top[1])preR[i]=t[preR[i]].son[0];
}
void ChooseRight(){
up(i,1,top[0])preL[i]=t[preL[i]].son[1];
up(i,1,top[1])preR[i]=t[preR[i]].son[1];
}
int Col(){
int sum=0;
up(i,1,top[0])sum-=t[t[preL[i]].son[0]].sum;
up(i,1,top[1])sum+=t[t[preR[i]].son[0]].sum;
return sum;
}
void Prepare(){
rnum=N=read();M=read();
up(i,1,N)arr[i]=fsort[i]=read();
up(i,1,M){
query[i].opt=read();
if(query[i].opt==3){
query[i].pos=read();query[i].K=read();
fsort[++rnum]=query[i].K;continue;
}
query[i].L=read();query[i].R=read();query[i].K=read();
if(query[i].opt==4||query[i].opt==5)
fsort[++rnum]=query[i].K;
}
sort(fsort+1,fsort+rnum+1);
rnum=unique(fsort+1,fsort+rnum+1)-(fsort+1);
up(i,1,N){
arr[i]=lower_bound(fsort+1,fsort+rnum+1,arr[i])-fsort;
insert(1,rnum,root[i+N],root[i+N-1],arr[i]);
}
}
int Rank(int leftt,int rightt,int pos){
if(leftt==rightt){
TMP=0;
up(i,1,top[0])TMP-=t[preL[i]].sum;
up(i,1,top[1])TMP+=t[preR[i]].sum;
return 1;
}
int sum=0,mid=(leftt+rightt)>>1;
sum=Col();
if(pos<=mid){
ChooseLeft();
return Rank(leftt,mid,pos);
}else{
ChooseRight();
return sum+Rank(mid+1,rightt,pos);
}
}
int Get(int leftt,int rightt,int rnk){
int sum,mid=(leftt+rightt)>>1;
if(leftt==rightt) return fsort[leftt];
sum=Col();
if(rnk<=sum){
ChooseLeft();
return Get(leftt,mid,rnk);
}else{
ChooseRight();
return Get(mid+1,rightt,rnk-sum);
}
}
void Insert(int leftt,int rightt,int &Root,int pos,int tag){
if(!Root)Root=NewNode(0,0,0);
t[Root].sum+=tag;
if(leftt==rightt) return;
int mid=(leftt+rightt)>>1;
if(pos<=mid) Insert(leftt,mid,t[Root].son[0],pos,tag);
else Insert(mid+1,rightt,t[Root].son[1],pos,tag);
}
void Slove(){
up(i,1,M){
int opt=query[i].opt;
if(opt==1){
int L=query[i].L,R=query[i].R,K=lower_bound(fsort+1,fsort+rnum+1,query[i].K)-fsort;
PushTree(L,R);
printf("%d\n",Rank(1,rnum,K));
}
if(opt==2){
int L=query[i].L,R=query[i].R,K=query[i].K;
PushTree(L,R);
printf("%d\n",Get(1,rnum,K));
}
if(opt==3){
int Pos=query[i].pos,K=query[i].K;
for(int j=Pos;j<=N;j+=lowbit(j))
Insert(1,rnum,root[j],arr[Pos],-1);
arr[Pos]=lower_bound(fsort+1,fsort+rnum+1,K)-fsort;
for(int j=Pos;j<=N;j+=lowbit(j))
Insert(1,rnum,root[j],arr[Pos],1);
}
if(opt==4){
int L=query[i].L,R=query[i].R,K=lower_bound(fsort+1,fsort+rnum+1,query[i].K)-fsort;
PushTree(L,R);
int rank=Rank(1,rnum,K);
PushTree(L,R);
printf("%d\n",Get(1,rnum,rank-1));
}
if(opt==5){
int L=query[i].L,R=query[i].R,K=lower_bound(fsort+1,fsort+rnum+1,query[i].K)-fsort;
PushTree(L,R);
int rank=Rank(1,rnum,K);
PushTree(L,R);
printf("%d\n",Get(1,rnum,rank+TMP));
}
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
Prepare();
Slove();
return 0;
}