hdu 5412 CRB and Queries Dynamic 구간 K-작은 트리 트리
트리 그룹 + 균형 트리입니다.나는 두 개의 코드를 썼다. 트리 그룹 + SBT, 트리 그룹 + Treap 코드:
//author: CHC
//First Edit Time: 2015-08-20 14:10
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
#include <time.h>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct SBT
{
int left,right,size,key;
void Init()
{
left=right=0;
size=1;
}
}tree[MAXN*30];
int tot,root[MAXN<<2],n;
void left_rotate(int &x)//
{
int y=tree[x].right;
tree[x].right=tree[y].left;
tree[y].left=x;
tree[y].size=tree[x].size;
tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
x=y;
}
void right_rotate(int &x)//
{
int y=tree[x].left;
tree[x].left=tree[y].right;
tree[y].right=x;
tree[y].size=tree[x].size;
tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
x=y;
}
void maintain(int &x,int flag)
{
if(flag==0)
{
if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)
right_rotate(x);
else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)
left_rotate(tree[x].left),right_rotate(x);
else return;
}
else
{
if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)
left_rotate(x);
else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)
right_rotate(tree[x].right),left_rotate(x);
else return;
}
maintain(tree[x].left,0);
maintain(tree[x].right,1);
maintain(x,0);
maintain(x,1);
}
// ,
void insert(int &x,int key)
{
if(x==0)
{
x=++tot;
tree[x].Init();
tree[x].key=key;
}
else
{
tree[x].size++;
if(key<tree[x].key)insert(tree[x].left,key);
else insert(tree[x].right,key);
maintain(x,key>=tree[x].key);
}
}
// key
int del(int &x,int key)
{
if(!x)return 0;
tree[x].size--;
if(key==tree[x].key || (key<tree[x].key&&tree[x].left==0)
|| (key>tree[x].key&&tree[x].right==0))
{
if(tree[x].left && tree[x].right)
{
int p=del(tree[x].left,key+1);
tree[x].key=tree[p].key;
return p;
}
else
{
int p=x;
x=tree[x].left+tree[x].right;
return p;
}
}
else return del(key<tree[x].key?tree[x].left:tree[x].right,key);
}
int _rank(int x,int val){
if(x==0)return 0;
if(tree[x].key<=val)return tree[tree[x].left].size+1+_rank(tree[x].right,val);
return _rank(tree[x].left,val);
}
void print(int x,int d){
if(!x)return ;
printf("%d %d
",tree[x].key,d);
print(tree[x].left,d+1);print(tree[x].right,d+1);
}
int A[MAXN];
void Add(int x,int v){
while(x<=n){
//printf("x:%d
",x);
insert(root[x],v);
x+=x&-x;
}
}
void Del(int x,int v){
while(x<=n){
del(root[x],v);
x+=x&-x;
}
}
int Sum(int x,int v){
int cnt=0;
while(x>0){
cnt+=_rank(root[x],v);
x-=x&-x;
}
return cnt;
}
struct Q {
int type,l,r,v;
}cs[MAXN];
int res[MAXN*2];
int main()
{
//int size = 256 << 20; // 256MB
//char *p = (char*)malloc(size) + size;
//__asm__("movl %0, %%esp
" :: "r"(p));
//freopen("1007.in","r",stdin);
//freopen("10071.out","w",stdout);
//time_t now=clock();
int q;
while(~scanf("%d",&n)){
memset(root,0,sizeof(root));
tot=0;
res[0]=0;
for(int i=1;i<=n;i++)scanf("%d",&A[i]),res[++res[0]]=A[i];
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&cs[i].type);
if(cs[i].type==1){
scanf("%d%d",&cs[i].l,&cs[i].v);
res[++res[0]]=cs[i].v;
}
else {
scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].v);
}
}
sort(res+1,res+1+res[0]);
res[0]=unique(res+1,res+1+res[0])-res-1;
for(int i=0;i<q;i++){
if(cs[i].type==1){
cs[i].v=lower_bound(res+1,res+1+res[0],cs[i].v)-res;
}
}
//printf("res0:%d
",res[0]);
//for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
//puts("");
for(int i=1;i<=n;i++)A[i]=lower_bound(res+1,res+1+res[0],A[i])-res;
//for(int i=1;i<=n;i++)printf("%d ",A[i]);
//puts("");
//build(1,n,1);
//print(root[1],0);
//puts("here__");
for(int i=1;i<=n;i++){
Add(i,A[i]);
}
//puts("here");
for(int i=0;i<q;i++){
if(cs[i].type==1){
//update(1,n,1,cs[i].l,cs[i].v);
Del(cs[i].l,A[cs[i].l]);
Add(cs[i].l,cs[i].v);
A[cs[i].l]=cs[i].v;
}
else {
int l=1,r=res[0],ans=res[0];
while(l<=r){
int mid=(l+r)>>1;
int t=Sum(cs[i].r,mid)-Sum(cs[i].l-1,mid);
if(t>=cs[i].v){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d
",res[ans]);
}
}
}
//printf("%.2lf
",1.0*(clock()-now)/CLOCKS_PER_SEC);
return 0;
}
코드 2:
//author: CHC
//First Edit Time: 2015-08-20 12:15
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
class Treap {
public:
struct node {
node *ch[2];
int v,p,sz;
node(int _v,node *_n){ v=_v; ch[0]=ch[1]=_n; p=rand(); sz=1; }
void update(){sz=ch[0]->sz+ch[1]->sz+1;}
void fixch(node *left,node *right){ch[0]=left;ch[1]=right;}
};
node *root,*null;
Treap(){
null=new node(0,0);
null->fixch(null,null); null->sz=0;
root=null;
}
void rotate(node *&t,bool d){
node *_t=t->ch[d];
t->ch[d]=_t->ch[!d];
_t->ch[!d]=t;
t->update();
_t->update();
t=_t;
}
void __insert(node *&t,int val){
if(t==null){
t=new node(val,null);
return ;
}
bool d=(t->v < val);
__insert(t->ch[d],val);
if(t->ch[d]->p < t->p)rotate(t,d);
t->update();
}
void __del(node *&t,int val){
if(t==null)return ;
if(t->v==val){
node *tmp=t;
if(t->ch[0]==null){
t=t->ch[1];
delete tmp;
return ;
}
if(t->ch[1]==null){
t=t->ch[0];
delete tmp;
return ;
}
bool d=t->ch[1]->p < t->ch[0]->p;
rotate(t,d);
__del(t->ch[!d],val);
}
else {
bool d=(t->v < val);
__del(t->ch[d],val);
}
t->update();
}
int __rank(node *t,int val){
if(t==null)return 0;
if(t->v <= val)return t->ch[0]->sz+1+__rank(t->ch[1],val);
//return t->ch[1]->sz+1+__rank(t->ch[0],val);
return __rank(t->ch[0],val);
}
void __clean(node *&t){
if(t==null)return ;
if(t->ch[0]!=null)__clean(t->ch[0]);
if(t->ch[1]!=null)__clean(t->ch[1]);
delete t;
t=null;
}
void insert(int val){ __insert(root,val); }
void del(int val){ __del(root,val); }
int rank(int val){ return __rank(root,val);}
void clean(){ __clean(root); }
~Treap(){ clean(); delete null; }
}tr[MAXN];
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
int A[MAXN],n;
void Add(int pos,int v){
while(pos<=n){
tr[pos].insert(v);
pos+=pos&-pos;
}
}
void Del(int pos,int v){
while(pos<=n){
tr[pos].del(v);
pos+=pos&-pos;
}
}
int Sum(int pos,int v){
int cnt=0;
while(pos>0){
cnt+=tr[pos].rank(v);
pos-=pos&-pos;
}
return cnt;
}
struct Q {
int type,l,r,v;
}cs[MAXN];
int res[MAXN*2];
int main()
{
//int size = 256 << 20; // 256MB
//char *p = (char*)malloc(size) + size;
//__asm__("movl %0, %%esp
" :: "r"(p));
//freopen("1007.in","r",stdin);
//freopen("10071.out","w",stdout);
while(~scanf("%d",&n)){
res[0]=0;
for(int i=1;i<=n;i++)scanf("%d",&A[i]),res[++res[0]]=A[i];
int q;
//printf("%d
",query(1,n,1,1,n,4));
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&cs[i].type);
if(cs[i].type==1){
scanf("%d%d",&cs[i].l,&cs[i].v);
res[++res[0]]=cs[i].v;
}
else {
scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].v);
}
}
sort(res+1,res+1+res[0]);
res[0]=unique(res+1,res+1+res[0])-res-1;
//printf("res0:%d
",res[0]);
//for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
//puts("");
for(int i=1;i<=n;i++){
A[i]=lower_bound(res+1,res+1+res[0],A[i])-res;
}
//build(1,n,1);
for(int i=0;i<q;i++){
if(cs[i].type==1){
cs[i].v=lower_bound(res+1,res+1+res[0],cs[i].v)-res;
}
}
for(int i=0;i<=n;i++)tr[i].clean();
for(int i=1;i<=n;i++){
Add(i,A[i]);
}
for(int i=0;i<q;i++){
if(cs[i].type==1){
//while(A[cs[i].l]<=0||A[cs[i].l]>res[0]);
Del(cs[i].l,A[cs[i].l]);
Add(cs[i].l,cs[i].v);
A[cs[i].l]=cs[i].v;
//update(1,n,1,cs[i].l,cs[i].v);
}
else {
int l=1,r=res[0],ans=res[0];
while(l<=r){
int mid=(l+r)>>1;
int t=Sum(cs[i].r,mid)-Sum(cs[i].l-1,mid);
//if(query(1,n,1,cs[i].l,cs[i].r,mid)>=cs[i].v){
if(t>=cs[i].v){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d
",res[ans]);
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Windows】 sbt 버전이 1.4.6 이상이라면 프로젝트 바로 아래에 "null"이라는 폴더가 만들어 버린다.정보공유겸비망록입니다. Windows에서 sbt 1.4.6 (또는 1.4.7)를 시작하면 프로젝트 바로 아래에 null라는 폴더가 생겼습니다. 덧붙여서 커맨드 라인 경유라면 null/Coursier/cache/v1라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.