[BZOJ] [P3110] [ZJOI 2013] [K 대수 조회] [문제 풀이] [나무 세트 트 리]
오후 내 내 썼 는데 + 밤새 A 가 없 네 아아 아아 아아 아아 아아
수정 log ^ 2n 조회 log ^ 3n T 성상 아아 아아 아아 아아 아아 아아
팀 원 들 이 나무 모양 의 수 조 를 보면 서 함부로 학대 하 는 구나 아아 아아 아아 아아
자기 라인 트 리, 밸 런 스 트 리, T 성상 아 아아 아아 아아 아아
Code:
#include<cstdio>
#include<cctype>
#include<climits>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long LL;
const int maxn=50001;
int getint(){
int res=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();
return res;
}
int n,m;
int rnd(){
static int KEY=978654321;
return KEY+=KEY<<2|1;
}
int maxx=0;
struct node;
struct node{
int val,key,size,s;
node *c[2];
void set(int _val=0,int _key=rnd(),int _size=1,int _s=1,node *C=NULL){
val=_val;key=_key;size=_size;s=_s;c[0]=c[1]=C;
}
void rz(){
size=c[0]->size+s+c[1]->size;
}
};
node pool[maxn*65];
node *newnode(){
static int tot=0;
if(tot<maxn*65)return &pool[tot++];
return new node();
}
struct Treap{
node *root,*Null;
Treap(){
Null=newnode();
Null->set(0,INT_MAX,0,0,Null);
root=Null;
}
void rot(node *&t,bool d){
node *p=t->c[d];t->c[d]=p->c[!d];
p->c[!d]=t;t->rz();p->rz();t=p;
}
void _insert(node *&t,int x,int siz){
if(t==Null){t=newnode();t->set(x,rnd(),siz,siz,Null);return;}
if(t->val==x){t->size+=siz;t->s+=siz;return;}
_insert(t->c[x>t->val],x,siz);
if(t->c[x>t->val]->key<t->key)rot(t,x>t->val);
else t->rz();
}
int _find(node *t,int &x){
if(t==Null)return 0;
if(t->val==x)return t->s;
return _find(t->c[x>t->val],x);
}
int _rank(node *t,int &x){
int res=0,s;
for(node *t=root;t!=Null;){
s=t->c[0]->size+t->s;
if(x>t->val)res+=s,t=t->c[1];
else t=t->c[0];
}return res;
}
void insert(int x,int siz){_insert(root,x,siz);}
int rank(int x){return _rank(root,x);}
int size(){return root->size;}
int find(int x){return _find(root,x);}
};
int Ranks,Finds;
unsigned int Size;
struct seg_tree{
Treap loc[maxn<<2];
Treap lazy[maxn<<2];
void change(int i,int l,int r,int l0,int r0,int c){
if(l0<=l&&r0>=r){
lazy[i].insert(c,r-l+1);
return;
}
int mid=(l+r)>>1;
loc[i].insert(c,min(r,r0)-max(l,l0)+1);
if(l0<=mid)change(i<<1,l,mid,l0,r0,c);
if(r0>mid)change(i<<1|1,mid+1,r,l0,r0,c);
}
void _rank(int i,int l,int r,int l0,int r0,int x){
Ranks+=(LL)lazy[i].rank(x)*(min(r,r0)-max(l,l0)+1)/(r-l+1);
if(l0<=l&&r0>=r){
Ranks+=loc[i].rank(x);
return;
}int mid=(l+r)>>1;
if(l0<=mid)_rank(i<<1,l,mid,l0,r0,x);
if(r0>mid)_rank(i<<1|1,mid+1,r,l0,r0,x);
}
int rank(int l,int r,int x){
Ranks=0;
_rank(1,1,n,l,r,x);
return Ranks;
}
void _size(int i,int l,int r,int l0,int r0){
Size+=lazy[i].size()/(r-l+1)*(min(r,r0)-max(l,l0)+1);
if(l0<=l&&r0>=r){
Size+=loc[i].size();
return ;
}int mid=(l+r)>>1;
if(l0<=mid)_size(i<<1,l,mid,l0,r0);
if(r0>mid)_size(i<<1|1,mid+1,r,l0,r0);
}
unsigned int size(int l,int r){
Size=0;
_size(1,1,n,l,r);
return Size;
}
void _find(int i,int l,int r,int l0,int r0,int x){
Finds+=lazy[i].find(x)/(r-l+1)*(min(r,r0)-max(l,l0)+1);
if(l0<=l&&r0>=r){
Finds+=loc[i].find(x);
return ;
}int mid=(l+r)>>1;
if(l0<=mid)_find(i<<1,l,mid,l0,r0,x);
if(r0>mid)_find(i<<1|1,mid+1,r,l0,r0,x);
}
int find(int l,int r,int x){
Finds=0;
_find(1,1,n,l,r,x);
return Finds;
}
}T;
void Change(int l,int r,int k){
T.change(1,1,n,l,r,k);
}
int Kth(int l0,int r0,int k){
unsigned int siz=T.size(l0,r0);
k=siz-k+1;
unsigned int l=1,r=maxx,mid;
while(l<r){
mid=(l+r)>>1;
int ra=T.rank(l0,r0,mid);
int s=T.find(l0,r0,mid);
if(!ra&&!s)ra=-1;
if(ra==siz&&!s)ra=ra+1;
if(ra+1<=k&&k<=ra+s)return mid;
if(ra<k)
l=mid+1;
else
r=mid;
}return l;
}
void putint(int x){
if(x<10)
putchar(x+'0');
else{
putint(x/10);
putchar(x%10+'0');
}
}
int main(){
int res,op,l,r,k;
n=getint();m=getint();
while(m--){
op=getint();
l=getint(),r=getint(),k=getint();
if(op==1){
Change(l,r,k);
maxx=max(maxx,k);
}else{
res=Kth(l,r,k);
putint(res);
puts("");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.