[LOJ \ # 6284. 수열 블록 입문 8] ODT (코 도리 트 리) 해법

제목:
길이 가 \ (n \) 인 수열 과 \ (n \) 인 동작 을 보 여 줍 니 다. 구간 질문 과 같은 요 소 를 조작 하고 이 구간 의 모든 요 소 를 \ (c \) 로 바 꿉 니 다.
이 문 제 는 구간 이 평평 해 지 는 것 을 보 자마자 ODT 가 생각 났 는데, 이것 이 블록 문제 든 전혀 상관 하지 않 는 다.실제로 블록 별로 풀 수 있 는 문 제 는 ODT 도 기본적으로 감당 할 수 있다.
문 제 는 인터넷 블 로그 에서 ODT 조회 조작 에 대해 거의 언급 하지 않 아 문 제 를 베 끼 고 살아 가 는 사람들 이 손 을 쓸 수 없다 는 점 이다.
그래서 모두 가 즐겨 듣 는 블록 을 사 용 했 지만 잘 때 리 지 못 했다.개인 적 으로 코 도리 트 리 의 양 이 적은 것 이 가장 큰 장점 이 라 고 생각 합 니 다. 카드 에 걸 릴 수도 있 습 니 다. 어쨌든 코 도리 가 그렇게 귀 엽 습 니 다.
그리고 모두 가 \ (split \) 와 \ (assign \) 조작 방법 을 안다 고 가정 하면 여기 서 이런 기본 적 인 것들 을 군말 하지 않 을 것 이다.
우선 \ (set \) 내 장 된 함 수 를 고려 하 되 \ (set: count () \) 한 구간 을 지정 하여 계산 할 수 없 기 때문에 이 방법 은 즉시 무산 되 었 다.
set 내장 함 수 는 SPFA 입 니 다.
그리고 안 그 럴 거 야.그 다음 에 구간 에 추 가 된 모드 를 모방 하여 \ (check (l, r, c) \) 의 함 수 를 만 들 었 습 니 다. 다음 과 같 습 니 다.

#define IT set::iterator
int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
	for (; itl != itr; ++itl) if(itl->v==val) ans++;
    return ans;
}

즐 거 웠 습 니 다. 이 문 제 를 베 끼 고 살아 가 는 쓰레기 는 WA 를 얻 었 습 니 다.
사실 이것 과 푸 시 구간 의 요소 수 를 더 해 야 합 니 다. 즉, \ (Now {iter} \ rightarrow r - Now {iter} \ rightarrow l + 1 \), 즉 itl->r-itl->l+1 입 니 다.
그래서 이렇게 바 꿨 어 요.

int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
	for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
    return ans;
}

전체 코드 는 다음 과 같 습 니 다:

#include 
using namespace std;
typedef long long ll;
struct node{
	int l,r;
	mutable ll v;
	node(int L, int R=-1, ll V=0):l(L), r(R), v(V) {}
	bool operator ODT;
#define IT set::iterator
IT split(int pos){
	IT it = ODT.lower_bound(node(pos));
	if (it != ODT.end() && it->l == pos) return it;
	--it;
	int L = it->l, R = it->r;
	ll V = it->v;
	ODT.erase(it);
	ODT.insert(node(L, pos-1, V));
	return ODT.insert(node(pos, R, V)).first;
}
int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
	for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
    return ans;
}
void assign(int l, int r, ll val=0){
	IT itl = split(l),itr = split(r+1);
	ODT.erase(itl, itr);
	ODT.insert(node(l, r, val));
}
int main(){
    int n,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        ODT.insert(node(i,i,a));
    }for(int i=1;i<=n;i++){
        int l,r;
        ll c;
        scanf("%d%d%lld",&l,&r,&c);
        printf("%d
",check(l,r,c));
        assign(l,r,c);
    }//system("pause");
}