hdu 3577 (선분 트 리 구간 업데이트)


제목: t 그룹 테스트 데이터 가 있 음 을 나타 내 는 t 를 입력 하 십시오.
          다음 줄 에 두 개의 숫자 를 입력 하 십시오. k, m. 그 중에서 k 는 이 차 가 최대 이렇게 많은 사람 을 탈 수 있다 는 것 을 표시 합 니 다. m 는 m 번 에 차 를 탈 수 있 는 지 물 었 습 니 다.
          매번 문의 할 때마다 두 개의 수 a, b 를 입력 하면 해당 승객 이 a 플랫폼 에서 탈 수 있 는 지, b 플랫폼 에서 내 릴 수 있 는 지, 승차 구간 은 (a, b -) 이 고 선후 순서 임 을 나타 낸다.
          즉, 내 가 물 어 볼 때마다 너 는 a 플랫폼 에서 얼마나 많은 사람들 이 차 에 있 는 지 판단 하고 k 보다 작 으 면 차 에 탈 수 있 고 데 이 터 를 업데이트 할 수 있 으 며 그렇지 않 으 면 차 에 탈 수 없다 는 것 을 나타 낸다.
문제 풀이 방향: 이 문 제 는 선분 나무의 구간 업데이트, 즉 선분 의 중첩 횟수 를 판단 하 는 것 이 분명 하 다.
유 여가 책 에 적 힌 코드 WA 에 따 르 면 왜 그런 지 모 르 겠 어 요...

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1e6+5;
int add[maxn<<2],Max[maxn<<2],l,r,_max;
int ans[maxn];

void maintain(int o,int L,int R)
{
	int lc = o*2,rc = o*2+1;
	Max[o] = 0;
	if(R > L){
		Max[o] = max(Max[lc],Max[rc]);
	}
	Max[o] += add[o];
}

void update(int o,int L,int R,int v)
{
	int lc = o*2, rc = o*2+1;
	if(l <= L && R <= r){
		add[o] += v;
	}
	else{
		int M = (L + R) >> 1;
		if(M >= l) update(lc,L,M,v);
		if(r > M) update(rc,M+1,R,v);
	}
	maintain(o,L,R);
}

void query(int o,int L,int R,int addv)
{
	int lc = o*2, rc = o*2+1;
	if(l <= L && R <= r){
		_max = max(_max,Max[o] + addv);
	}
	else{
		int M = (L + R) >> 1;
		if(l <= M) query(lc,L,M,addv+add[lc]);
		if(r > M) query(rc,M+1,R,addv+add[rc]);
	}
}

int main()
{
	int t,cas = 1,len;
	scanf("%d",&t);
	while(t--){
		memset(add,0,sizeof(add));
		memset(Max,0,sizeof(Max));
		len = 0;
		int k,q;
		scanf("%d%d",&k,&q);
		for(int i = 1; i <= q; i++){
			scanf("%d%d",&l,&r);
			r--;
			_max = 0;
			query(1,1,1000000,0);
			if(_max < k){
				update(1,1,1000000,1);
				ans[len++] = i;
			}
		}
		printf("Case %d:
",cas++);
		for(int i = 0; i < len; i++)
			printf("%d ",ans[i]);
		printf("

");
	}
	return 0;
}

다른 사람의 코드 를 보고 레이 지 사상 을 사용 했다. 즉, 한 층 으로 한 층 을 갱신 하 는 것 이다. 만약 에 내 가 특정한 층 에서 요구 에 부합 되 는 구간 을 찾 을 수 있다 면 그의 서브 노드 를 업데이트 하지 않 고 내 가 그의 서브 노드 를 필요 로 할 때 다시 서브 노드 를 업데이트 했다.한 마디 로 하면 이런 사상 입 니 다. 코드 와 결합 하여 많이 생각 하 세 요.

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int ans[N];
struct node
{
    int l,r,v,lazy;
}node[N<<2];    //                4 ；
void build(int l,int r,int numb)    //        ；
{
    node[numb].l=l;
    node[numb].r=r;
    node[numb].v=0;
    node[numb].lazy=0;              //    lazy  ，     ；
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,numb<<1);
    build(mid+1,r,numb<<1|1);
}
void PushUp(int numb)               //              ；            ，     ，       ；
{
    node[numb].v=max(node[numb<<1].v,node[numb<<1|1].v);
}
void PushDown(int numb)             //               ；
{
    node[numb<<1].lazy+=node[numb].lazy;
    node[numb<<1|1].lazy+=node[numb].lazy;
    node[numb<<1].v+=node[numb].lazy;
    node[numb<<1|1].v+=node[numb].lazy;
    node[numb].lazy=0;              //         ；
}
void Insert(int l,int r,int numb)   //        ；
{
    if(node[numb].l>=l&&node[numb].r<=r)    //          ，          ，     ，         （lazy  ）
    {
        node[numb].v+=1;
        node[numb].lazy+=1;
        return;
    }
    if(node[numb].lazy) PushDown(numb);     //               ，           ；
    int mid=(node[numb].r+node[numb].l)>>1;
    if(l>mid) Insert(l,r,numb<<1|1);
    else if(r<=mid) Insert(l,r,numb<<1);
    else{
        Insert(l,mid,numb<<1);
        Insert(mid+1,r,numb<<1|1);
    }
    PushUp(numb);       //          ，       ；
}
int query(int l,int r,int numb)     //      l r；
{
    if(node[numb].l>=l&&node[numb].r<=r){
        return node[numb].v;
    }
    if(node[numb].lazy) PushDown(numb);     //     48 ；
    int mid=(node[numb].r+node[numb].l)>>1;
    if(l>mid) return query(l,r,numb<<1|1);
    else if(r<=mid) return query(l,r,numb<<1);
    else{
        return max(query(l,mid,numb<<1),query(mid+1,r,numb<<1|1));  //     28 ；
    }
}
int main()
{
    int t,Case=1,len=0,k,m,a,b;
    scanf("%d",&t);
    while(t--){
        len=0;
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&k,&m);
        build(1,1000000,1);
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            b--;                    //         ，     a  ，b  ，           （a,b--）;
            if(query(a,b,1)<k){     //        ；
                ans[len++]=i+1;
                Insert(a,b,1);
            }
        }
        printf("Case %d:
",Case++);
        for(int i=0; i<len; i++)    
            printf("%d ",ans[i]);
        printf("

");
    }
    return 0;
}