[선분 수] LOJ 3043 [ZJOI 2019] 선분 수.

[머리말] 이 문 제 는 생각 할 때 몇 번 잘못 생각 했 는데 뒤에서 다른 사람의 블 로 그 를 보고 나 서 야 편차 가 발견 되 었 습 니 다.
[제목] LOJ 는 처음에 선분 트 리 가 있 었 습 니 다. 표시 되 지 않 았 습 니 다. 한 번 의 조작 [l, r] [l, r] [l, r] 에 대해 모든 선분 트 리 를 복사 하고 홀수 레이 블 의 모든 선분 트 리 에 대해 우 리 는 일반 선분 트 리 처럼 구간 에 표 시 를 합 니 다. pushdown \ text {pushdown} pushdown 함 수 는 표 시 를 아래 에 놓 고 이 노드 의 표시 상황 을 표시 합 니 다.모든 라인 트 리 에 몇 개의 노드 가 표시 되 어 있 는 지 물 어 볼 때마다.
n , Q ≤ 1 0 5 n,Q\leq 10^5 n,Q≤105
[문제 풀이 사고] 모든 조작 에 있어 노드 의 상황 분류 통계 에 기여 하 는 것 을 고려 해 야 한다.아래 에서 "포 지 셔 닝 됨" 을 q l ≤ l ≤ r ≤ q r ql \ \ leq l \ \ leq r \ \ \ leq qr ql ≤ l ≤ r ≤ qr 의 노드 라 고 부 르 며, 우 리 는 대략 조작 구간 에 따라 노드 를 다음 과 같은 몇 가지 유형 으로 나 눌 수 있다.

이 노드 에 접근 하고 이 노드 가 위치

첫 번 째 노드 의 조상 노드 이지 만 이 노드 는 포 지 셔 닝 되 지 않 았 다

이 노드 에 접근 하지 않 았 고 이 노드 의 아버 지 는 방문 하지 않 았 습 니 다

이 노드 에 접근 하지 않 았 지만 이 노드 의 아버 지 는 방문 되 었 습 니 다 (즉, q l > r ql > r ql > r 또는 q r < l qr < l qr < l)

이번 조작 이 공헌 에 미 친 영향 고려:

첫 번 째 노드 에 대해 서 는 반드시 표 시 를 해 야 합 니 다. 그러면 모든 라인 트 리 에서 의 공헌 과 복사 전 공헌 + 2 i - 1 + 2 ^ {i - 1} + 2 i - 1

두 번 째 노드 에 대해 표 시 는 모두 내 려 놓 을 것 입 니 다. 그래서 복사 한 후에 기여 하지 않 았 습 니 다. 기여 와 복사 전 기여

세 번 째 노드 에 대해 그 표 시 는 변화 가 없 기 때문에 복제 전후 공헌 이 같 고 공헌 과 복제 전 공헌 이다.× 2 \times 2 ×2

네 번 째 노드 에 대한 기여 와 조상 이 표시 한 조작 상황 과 관련 이 있 으 므 로 우 리 는 그것 을 f i f 로 설정 해도 무방 하 다.i fi 는 루트 노드 경로 에 표 시 된 위치 1, 1 의 조작 상황 수 를 표시 합 니 다. 이 노드 가 모든 라인 트 리 에 기여 한 총 횟수 에 f i f 를 추가 해 야 합 니 다.i fi​。

유지 보수 고려 fi fi​：

첫 번 째 노드 에 대해 그 f i fi fi 회 + 2 i - 1 + 2 ^ {i - 1} + 2 i - 1, 작 동 하 는 모든 나무 에 이 노드 의 표 시 는 반드시 1 - 1 이기 때 문 입 니 다.

두 번 째 노드 에 대해 그 f i fi fi 는 변 하지 않 습 니 다. 루트 에 있 는 모든 표 시 는 이미 내 려 놓 았 기 때 문 입 니 다.

제3 4 류 노드 에 대해 그 f i fi fi 회× 2 \times 2 ×2. 복사 전후 상황 이 같 기 때 문 입 니 다 (이 노드 의 조상 이 표시 되 어 있 으 면 지금 은 한 칸 만 내 려 가기 때 문 입 니 다)

그러면 선분 트 리 는 노드 의 가중치 (곱셈 표 시 를 유지 해 야 합 니 다. 덧셈 은 이 노드 에 만 추가 되 기 때 문 입 니 다) 와 f f f 의 값 (태그 와 곱 하기 표 시 를 유지 해 야 합 니 다) 을 유지 해 야 합 니 다.
복잡 도 O (n log ⁡ n) O (n \ \ log n) O (nlogn)
[참조 코드]

#include
using namespace std;

const int N=1e5+10,mod=998244353;
int pw,ans,delta;

namespace IO
{
	int read()
	{
		int ret=0;char c=getchar();
		while(!isdigit(c)) c=getchar();
		while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
		return ret;
	}
	void write(int x){if(x>9)write(x/10);putchar(x%10^48);}
	void writeln(int x){write(x);putchar('
');}
}
using namespace IO;

namespace Math
{
	int upm(int x){return x>=mod?x-mod:(x<0?x+mod:x);}
	void up(int &x,int y){x=upm(x+y);}
	int mul(int x,int y){return 1ll*x*y%mod;}
}
using namespace Math;

namespace Data_Structure
{
	struct Segment
	{
		#define ls (x<<1)
		#define rs (x<<1|1)
		struct node
		{
			int v,mulv,f,addf,mulf;
		}t[N<<2];
		void build(int x,int l,int r)
		{
			t[x].mulv=t[x].mulf=1;
			if(l==r) return;
			int mid=(l+r)>>1;
			build(ls,l,mid);build(rs,mid+1,r);
		}
		void multv(int x,int v){t[x].v=mul(t[x].v,v);t[x].mulv=mul(t[x].mulv,v);}
		void multf(int x,int v){t[x].f=mul(t[x].f,v);t[x].mulf=mul(t[x].mulf,v);t[x].addf=mul(t[x].addf,v);}
		void addtf(int x,int v){up(t[x].f,v);up(t[x].addf,v);}
		void pushdown(int x)
		{
			if(t[x].mulv>1) multv(ls,t[x].mulv),multv(rs,t[x].mulv),t[x].mulv=1;
			if(t[x].mulf>1) multf(ls,t[x].mulf),multf(rs,t[x].mulf),t[x].mulf=1;
			if(t[x].addf>0) addtf(ls,t[x].addf),addtf(rs,t[x].addf),t[x].addf=0;
		}
		void update(int x,int l,int r,int L,int R)
		{
			if(L<=l && r<=R)
			{
				up(ans,-t[x].v);up(t[x].v,pw);up(t[x].mulv,t[x].mulv);
				addtf(x,pw);up(delta,t[x].v);
				return;
			}
			if(L>r || R<l) 
			{
				up(ans,-t[x].v);up(t[x].v,t[x].f);up(t[x].mulv,t[x].mulv);
				multf(x,2);up(delta,t[x].v);
				return;
			}
			pushdown(x);up(ans,-t[x].v);up(delta,t[x].v);
			int mid=(l+r)>>1;
			update(ls,l,mid,L,R);update(rs,mid+1,r,L,R);
		}
		#undef ls
		#undef rs
	}T;
}
using namespace Data_Structure;

namespace DreamLolita
{
	int n,Q;
	void solution()
	{
		n=read();Q=read();pw=1;
		T.build(1,1,n);
		while(Q--)
		{
			int op=read(),l,r;
			if(op&1) 
			{
				l=read();r=read();delta=0;
				T.update(1,1,n,l,r);//printf("%d %d %d
",ans,delta,pw);
				up(ans,ans);up(ans,delta);up(pw,pw);
			}
			else writeln(ans);
		}
	}
}

int main()
{
#ifdef Durant_Lee
	freopen("LOJ3043.in","r",stdin);
	freopen("LOJ3043.out","w",stdout);
#endif
	DreamLolita::solution();
	return 0;
}