Riva 12436 Rip Van Winkle 's Code (구간 업데이트, 구간 조회)

제목: 길이 가 250000 인 구간 에 대해 네 가지 조작 을 주 었 습 니 다. A 를 조작 하고 st 에서 ed 까지 구간 의 수 를 각각 1, 2,..., st - ed + 1 을 더 합 니 다.조작 B, st 에서 ed 까지 구간 내의 수 를 각각, st - ed + 1, st - ed,..., 1.C 를 조작 하여 st 에서 ed 구간 의 수 를 x 로 할당 합 니 다.S 를 조작 하여 st 에서 ed 까지 의 이 구간 내의 수의 총 계 를 조회 합 니 다.
조작 A 와 조작 B 는 모두 조작 한 것 이 고 실제로는 등차 수열 이기 때문에 함께 고려 할 수 있다.아니면 선분 트 리 입 니까? AB 를 조작 할 때 온라인 트 리 의 결산 점 에 왼쪽 점 에 추가 할 값 add 1, 오른쪽 점 에 추가 할 값 add 2 를 기록 하고 이 구간 의 공차 step (모두 AB 를 조작 하 는 게 으 른 작업 표시) 를 기록 합 니 다.C 를 조작 하 는 데 있어 서 온라인 트 리 의 결산 점 에 서 는 하나의 flag 로 현재 구간 내의 수가 모두 같 는 지 를 표시 하고, 구간 안의 수가 완전히 같 을 때, 즉 flag = 1 일 때 이 수 는 얼마 인지 (모두 C 를 조작 하 는 게 으 른 작업 표시) 를 valu 로 표시 합 니 다.
쉽게 얻 을 수 있 으 며 등차 수열 을 더 할 지 등차 수열 을 더 할 지 한 구간 에 대해 여러 차례 AB 조작 을 할 수 있다.C 작업 에 대해 서 는 구간 내 할당 값 을 x 로 강제 하기 때문에 이전의 AB 작업 은 모두 실 효 됩 니 다. 즉, 이때 AB 작업 을 나타 내 는 몇 개의 변 수 를 add 1, add 2 와 step 의 모든 할당 값 을 0 으로 해 야 합 니 다.하위 구간 에 기 록 된 값 을 전달 할 때 는 C 조작 표 시 를 우선 해 야 하 는데, AB 조작 과 C 조작 표시 가 동시에 존재 할 때 는 C 조작 을 먼저 하고 AB 조작 을 한 것 이 틀림 없고, 이때 AB 의 표 시 를 먼저 아래로 전달 하고 C 의 표 시 를 전달 하면 결과 가 부정 확 하 게 나 올 수 있 기 때문이다.
WA 오 랜 만 에 저 지 른 두 가지 실수:
1. 시작 할 때 add 1, add 2 만 기록 한 다음 에 하위 구간 에 게 으 른 작업 의 값 을 전달 합 니 다. 즉, add 1 과 add 2 를 전달 할 때 두 구간 으로 분해 하여 (add 1, mid 1), (mid 2, add 2) 로 설정 하고 (add1 + add 2) / 2 를 통 해 mid 1 을 직접 얻 은 다음 에 mid 2 는 점차 증가 하거나 점차 감소 하 는 것 에 따라 1 을 더 해 야 합 니 다. 실제로 여기에 공차 를 더 하거나 빼 야 합 니 다.선분 나무의 결점 에 공차 step 를 추가 한 이유 다.
2. 조작 C 의 표 시 는 valu 만 있 고 flag 가 없습니다. 잘못된 것 은 valu 값 이 0 이 아니라면 아래로 전달 할 값 이 있다 는 것 입 니 다. 실제로 조작 C 는 구간 의 모든 값 을 0 으로 할당 할 수 있 습 니 다. 이때 valu 는 0 이 고 아래로 전달 되 지 않 아 오류 가 발생 하지 않 습 니 다. 그래서 표 시 를 하나 더 추가 하 였 습 니 다.
PS: 어떤 OJ 에 서 는 * 2 가 좀 느 려 요.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=250005;
typedef long long LL;
struct node
{
    bool flag;
	int left,right;
	LL sum,add1,add2,valu,step;
	LL mid(){return left+(right-left)/2;}
	LL len(){return right-left+1;}
	void changeAB(LL a,LL b,LL k)
	{
		add1+=a;    add2+=b;    step+=k;
		sum+=(a+b)*len()/2;
	}
	void changeC(LL a)
	{
	    flag=1;     valu=a;
		add1=0;     add2=0;     step=0;
        sum=valu*len();
	}
};
struct Segtree
{
	node tree[N*4];
	void down(int ind)
	{
		if(tree[ind].flag)
		{
			tree[ind*2].changeC(tree[ind].valu);
			tree[ind*2+1].changeC(tree[ind].valu);
			tree[ind].flag=0;
		}
		if(tree[ind].add1||tree[ind].add2||tree[ind].step)
		{
		    LL add1=tree[ind].add1,add2=tree[ind].add2;
		    LL k=tree[ind].step;
		    LL mid=add1+k*(tree[ind*2].len()-1);

			tree[ind*2].changeAB(add1,mid,k);
			tree[ind*2+1].changeAB(mid+k,add2,k);
			tree[ind].add1=0;	tree[ind].add2=0;
			tree[ind].step=0;
		}
	}
	void build(LL left,LL right,LL ind)
	{
		tree[ind].left=left;	tree[ind].right=right;
		tree[ind].add1=0;		tree[ind].add2=0;
		tree[ind].sum=0;		tree[ind].valu=0;
		tree[ind].step=0;
		if(left!=right)
		{
			LL mid=tree[ind].mid();
			build(left,mid,ind*2);
			build(mid+1,right,ind*2+1);
		}
	}
	void updataAB(LL be,LL end,LL ind,LL step)
	{
		LL left=tree[ind].left,right=tree[ind].right;
		if(be<=left&&right<=end)
		{
		    LL st,ed;
		    if(step>=0) {st=left-be+1;ed=right-be+1;}
		    else {st=end-left+1;ed=end-right+1;}
		    tree[ind].changeAB(st,ed,step);
		}
		else
		{
			down(ind);
			LL mid=tree[ind].mid();
			if(be<=mid) updataAB(be,end,ind*2,step);
			if(end>mid) updataAB(be,end,ind*2+1,step);
			tree[ind].sum=tree[ind*2].sum+tree[ind*2+1].sum;
		}
	}
	void updataC(LL be,LL end,LL ind,LL valu)
	{
		LL left=tree[ind].left,right=tree[ind].right;
		if(be<=left&&right<=end) tree[ind].changeC(valu);
		else
		{
			down(ind);
			LL mid=tree[ind].mid();
			if(be<=mid) updataC(be,end,ind*2,valu);
			if(end>mid) updataC(be,end,ind*2+1,valu);
			tree[ind].sum=tree[ind*2].sum+tree[ind*2+1].sum;
		}
	}
	LL query(LL be,LL end,LL ind)
	{
		LL left=tree[ind].left,right=tree[ind].right;
		if(be<=left&&right<=end) return tree[ind].sum;
		else
		{
			down(ind);
			LL mid=tree[ind].mid();
			LL sum1=0,sum2=0;
			if(be<=mid) sum1=query(be,end,ind*2);
			if(end>mid) sum2=query(be,end,ind*2+1);
			return sum1+sum2;
		}
	}
}seg;
int main()
{

    int n;
    while(scanf("%d",&n)!=EOF)
    {
		seg.build(1,N-5,1);
		for(int i=0;i<n;i++)
		{
			char str[10];
			LL a,b,c;
			scanf("%s",str);
			if(str[0]=='A')
			{
				scanf("%lld%lld",&a,&b);
				seg.updataAB(a,b,1,1);
			}
			else if(str[0]=='B')
			{
				scanf("%lld%lld",&a,&b);
				seg.updataAB(a,b,1,-1);
			}
			else if(str[0]=='C')
			{
				scanf("%lld%lld%lld",&a,&b,&c);
				seg.updataC(a,b,1,c);
			}
			else
			{
				scanf("%lld%lld",&a,&b);
				printf("%lld
",seg.query(a,b,1));
			}
		}
	}
	return 0;
}