사취 서론 - ODT 코 도리 나무
72825 단어 사기 도 론
코 도리 트 리 (또는 ODT (Old Driver Tree) 라 고도 함) 라 는 독종 알고리즘 은 CodeForces - 896 C Willem, Chtholly and Seniorius 의 정 해 에서 파생 되 었 다.
랜 덤 데이터 에서 뛰 는 경우 가 많 지만 폭력 을 속 이 는 비 정통 알고리즘 사상 은 폭력 을 속 이 는 것 일 뿐 시간 복잡 도 는 정확 하지 않다 는 것 을 명심 해 야 한다.
언제 코 도리 나무 로
코 도리 나 무 는 일반적으로 선분 나무 가 해결 해 야 할 구간 류 문 제 를 해결 하 는 데 쓰 인 다.
그리고 코 도리 나 무 를 폭력 적 으로 초두 거리 로 만 드 는 관건 은 assign 구간 푸 시 작업 이다. 즉, 문제 에 구간 할당 작업 이 있어 야 하고 데이터 가 무 작위 적 인 상황 에서 복잡 도 를 보장 할 수 있다.
코 도리 나무 - 초기 화
일반적으로 코 도리 나 무 는 set 유지보수 수열 set 에서 각 노드 마다 세 개의 값 (l l, r, v a l) (ll, rr, val) (ll, rr, val) 을 선택 합 니 다. [l, r] [ll, rr] [ll, rr] 내의 값 은 모두 v a l val 입 니 다. 즉, 각 노드 마다 연 속 된 값 이 같은 구간 set 에서 각 구간 의 왼쪽 끝 점 으로 정렬 하 는 것 입 니 다.
struct node
{
int ll,rr;
mutable int val;
node(int L,int R=-1,int V=0): ll(L), rr(R), val(V) {}
bool operator < (const node& tt)const { return ll<tt.ll;}//
};
set<node> st;
주의해 야 할 것 은 m u t a b l e mutable mutable 이 v a l val 에 대한 수식 이 없 으 며 다음 add 함수 에서 CE 를 가 져 옵 니 다.
다음은 교체 기 에 대한 조작 을 편리 하 게 하기 위해 매크로 정 의 를 내 립 니 다.
#define IT set::iterator
코 도리 나무 - 분열 스 플 릿
s p l i t (p o s) split (pos) split (pos) 조작 은 원래 pos 위 치 를 포함 하 는 노드 를 두 부분 으로 나 누 어 [l, p o s - 1] [l, pos - 1] [l, pos - 1] 과 [p o s, r] [pos, r] [pos, r] 로 나 누 어 분 단 된 후 p o s pos 를 왼쪽 끝 점 으로 하 는 교체 기 를 말한다.
IT split(int pos)
{
IT it=st.lower_bound(node(pos));// pos
if(it!=st.end()&&it->ll==pos) return it;//pos ，
--it;// pos
int ll=it->ll,rr=it->rr,val=it->val;
st.erase(it);//
st.insert(node(ll,pos-1,val));
return st.insert(node(pos,rr,val)).first;// .first
}
코 도리 트 리 – 구간 할당 할당
코 도리 나 무 는 이 걸 로 부정 확 한 복잡 도 를 유지 하 는 거 야.
void assign(int ll,int rr,int val)
{
IT itr=split(rr+1),itl=split(ll);
st.erase(itl,itr);
st.insert(node(ll,rr,val));
}
필요 한 구간 을 분열 시 키 고 삭제 한 후 새로운 주 의 를 삽입 하여 [l, r] [ll, rr] [ll, rr] 구간 을 분열 시 킬 때 먼저 오른쪽 단점 을 분열 시 키 고 왼쪽 단점 을 분열 시 켜 야 한다.
e r a s e erase erase 방법 은 교체 기 가 설명 한 구간 [f i r s t, l a s t) [first, last) [first, last) 를 삭제 할 수 있 습 니 다. 왼쪽 닫 고 오른쪽 열 림 에 주의 하 십시오.
void erase (iterator first, iterator last)
데이터 가 순 무 작위 인 상황 에서 매번 a s i g n assign assign 의 구간 길 이 는 N / 3 N / 3 N / 3 으로 s e t set 규모 가 급 격 히 떨 어 진 후에 O (m l o g n) O (mlogn) O (mlogn) 에 가 까 운 현학 의 부정 확 한 복잡 도 에 이 르 렀 음 을 증명 할 수 있다.
코 도리 나무 - 기타 폭력 조작
다른 조작 은 정말 규칙 적 인 순 폭력 으로 대응 구간 을 직접 꺼 내 폭력 으로 모든 것 을 조작 하 는 것 이다.
보통 이렇게 생 겼 어 요.
void fun(int ll,int rr)
{
IT itr=split(rr+1),itl=split(ll);
for(;itl!=itr;++itl)
{
//...
}
}
밤 을 삶다
int qsum(int ll,int rr)
{
int res=0;
IT itr=split(rr+1),itl=split(ll);
for(;itl!=itr;++itl) res+=(itl->rr-itl->ll+1)*itl->val;// (itl->rr-itl->ll+1)
return res;
}
좀 더 복잡 한 밤 을 끓 여 라 – 구간 Kth
똑 같은 폭력 이에 요.
#define pir pair코 도리 나무 - 폭력 AC 응용
CodeForces - 896C Willem, Chtholly and Seniorious
독종 ODT 의 근원
#include::iterator
#define pir pair
",kth(ll,rr,x));
else if(op==4) printf("%lld
",qsum(ll,rr,x,y));
}
return 0;
}
낙 곡 P2572 [SCOI 2010] 시퀀스 조작
설명 할 게 없어 요. 폭력 이 니까 요.
#include::iterator
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
const int maxn=100010;
int n,m;
int a[maxn];
struct node
{
int ll,rr;
mutable int val;
node(int L,int R=-1,int V=0): ll(L), rr(R), val(V) {}
bool operator < (const node& tt)const { return ll<tt.ll;}
};
set<node> st;
IT split(int pos)
{
IT it=st.lower_bound(node(pos));
if(it!=st.end()&&it->ll==pos) return it;
--it;
int ll=it->ll,rr=it->rr,val=it->val;
st.erase(it);
st.insert(node(ll,pos-1,val));
return st.insert(node(pos,rr,val)).first;
}
void assign(int ll,int rr,int val)
{
IT itr=split(rr+1),itl=split(ll);
st.erase(itl,itr);
st.insert(node(ll,rr,val));
}
void rev(int ll,int rr)
{
IT itr=split(rr+1),itl=split(ll);
for(;itl!=itr;++itl) itl->val^=1;
}
int qsum(int ll,int rr)
{
int res=0;
IT itr=split(rr+1),itl=split(ll);
for(;itl!=itr;++itl) res+=(itl->rr-itl->ll+1)*itl->val;
return res;
}
int qmax(int ll,int rr)
{
int res=0,tt=0;
IT itr=split(rr+1),itl=split(ll);
for(;itl!=itr;++itl)
{
if(itl->val==0) res=max(res,tt),tt=0;
else tt+=itl->rr-itl->ll+1;
}
return max(res,tt);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
st.insert(node(i,i,a[i]));
}
for(int i=1;i<=m;++i)
{
int k=read(),ll=read()+1,rr=read()+1;
if(k==0) assign(ll,rr,0);
else if(k==1) assign(ll,rr,1);
else if(k==2) rev(ll,rr);
else if(k==3) printf("%lld
",qsum(ll,rr));
else if(k==4) printf("%lld
",qmax(ll,rr));
}
return 0;
}
낙 곡 P2787 국어 1 (chin1) - 이치 사고 문제 풀이
시공 소모량 초두 정 해 는 한 개 수량 급 이 아니다.
다시 한 번 일 깨 워 주다
코 도리 나무 가 실제 적 으로 아무리 우수 하 더 라 도 그것 은 데이터 랜 덤 의 결과 일 뿐이다. 결국은 폭력 적 인 사기 수단 일 뿐이다. ODT AC 를 여러 문제 사용 할 수 있 지만 시간 복잡 도가 정확 하지 않다 는 사실 을 바 꿀 수 없다.
평소에 연습 할 때 적 게 사용 하 는 것 을 권장 합 니 다. 왜냐하면 이것 은 문제 자체 가 풀 고 있 는 정수 시험장 에서 문제 에 대해 생각 이 없 는 것 이 좋 은 사기 수단 이기 때 문 입 니 다.
좋은 웹페이지 즐겨찾기
