珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134249552

http://cplusoj.com/d/senior/p/SS231031C

珂朵莉树有个很好的性质：

任意时刻，所有区间都是不交的

所以我们可以把所有区间先拿珂朵莉树变成一堆小区间，每个区间有个存活时间 [t1,t2][t_1,t_2]

考虑这个区间意义。他会在 l∈[1,t1],r∈[t1,t2]l\in[1,t1],r\in[t1,t2] 的判断区间贡献 lenlen

考虑回到询问区间。我们把这两种区间放在一起扫描线，然后推下式子再拿线段树维护即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//4k
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 2000010
//#define M
#define mo 998244353
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}
void Mod(int &a) { if(a>=mo || a<=-mo) a%=mo; if(a<0) a+=mo; }
void Add(int &a, int b) { a+=b; Mod(a); }
void Mul(int &a, int b) { Mod(b); a*=b; Mod(a); } 
struct node {
	int l, r, t; 
	bool operator < (const node &A) const {
		return l<A.l; 
	}
};
set<node>s; 
struct Node {
	int t1, t2, len; 
};
vector<Node>G; 
int n, m, i, j, k, T;
int l, r, q, ans[N], p[N]; 

struct Segment_tree {
	int sex; 
	int rt, tot, ls[N<<2], rs[N<<2]; 
	int s[N], tag[N]; 
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) return ; 
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); build(rs[k], mid+1, r); 
	}
	void jia(int k, int l, int r, int z) {
		Add(tag[k], z); Add(s[k], z*(r-l+1)); 
	}
	void push_down(int k, int l, int r, int mid) {
		jia(ls[k], l, mid, tag[k]); 
		jia(rs[k], mid+1, r, tag[k]); 
		tag[k]=0; 
	}
	void push_up(int k) {
		s[k]=s[ls[k]]+s[rs[k]]; Mod(s[k]); 
	}
	void add(int k, int l, int r, int x, int y, int z) {
		if(l>=x && r<=y) return jia(k, l, r, z), void(); 
		int mid=(l+r)>>1; push_down(k, l, r, mid); 
		if(x<=mid) add(ls[k], l, mid, x, y, z); 
		if(y>=mid+1) add(rs[k], mid+1, r, x, y, z); 
		push_up(k); 
	}
	int que(int k, int l, int r, int x, int y) {
		if(l>=x && r<=y) return s[k]; 
		int mid=(l+r)>>1, sum=0; push_down(k, l, r, mid); 
		if(x<=mid) Add(sum, que(ls[k], l, mid, x, y)); 
		if(y>=mid+1) Add(sum, que(rs[k], mid+1, r, x, y)); 
		push_up(k); 
		return sum; 
	}
}Seg1, Seg2;

void del(set<node>::iterator it) {
	int l=(it->l), r=(it->r), t=(it->t); 
	if(t==0) return ; 
	if(t==i) return ; 
	if(l<0) return ; 
	if(r>=mo) return ; 
	if(r-l+1<=0) return ; 
//	debug("[%d %d] %d %d\n", l, r, t, i-1); 
	G.pb({t, i-1, r-l+1}); 
}

void split(int x) {
	auto it=s.upper_bound({x, 0, 0}); --it; 
	if((it->l)==x) return ; 
	int l=(it->l), r=(it->r), t=(it->t); 
	s.erase(it); 
	s.insert({l, x-1, t}); 
	s.insert({x, r, t}); 
}

bool cmp(Node x, Node y) {	
	if(x.t1==y.t1) return x.len>y.len; 
	return x.t1>y.t1; 
}

signed main()
{
	freopen("range.in", "r", stdin);
	freopen("range.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	Seg1.sex=1; Seg2.sex=2; 
	n=read(); q=read(); 
	Seg1.build(Seg1.rt, 1, n); 
	Seg2.build(Seg2.rt, 1, n); 
	s.insert({-1, -1, 0}); s.insert({0, mo-1, 0}); s.insert({mo, mo, 0}); 
	for(i=1; i<=n; ++i) {
		l=read()+1; r=read(); 
		split(r+1); split(l); 
		auto it1=s.upper_bound({l, 0, 0}); --it1; 
		auto it2=s.upper_bound({r+1, 0, 0}); --it2; 
		for(auto it=it1; it!=it2; ++it) del(it); 
		s.erase(it1, it2); 
		s.insert({l, r, i}); 
	}
	while(s.begin()!=s.end()) del(s.begin()), s.erase(s.begin()); 
	for(i=1; i<=q; ++i) {
		l=read(); r=read(); 
		G.pb({l, r, -i}); 
		p[i]=(r-l+1)*(r-l+2)/2; Mod(p[i]); 
//		debug(">> %lld\n", p[i]); 
		p[i]=pw(p[i], mo-2); Mod(p[i]); 
	}
	sort(G.begin(), G.end(), cmp); 	
	for(auto t : G) {
		if(t.len>0) {
			Seg1.add(1, 1, n, t.t1, t.t2, t.len*(t.t1+1)); 
			Seg2.add(1, 1, n, t.t1, t.t2, t.len); 
		}
		else {
			int s1=Seg1.que(1, 1, n, t.t1, t.t2); 
			int s2=Seg2.que(1, 1, n, t.t1, t.t2); 
			Add(ans[-t.len], s1-t.t1*s2); Mod(ans[-t.len]); 
		}
	}
	for(i=1; i<=q; ++i) Mul(ans[i], p[i]); 
	for(i=1; i<=q; ++i) printf("%lld\n", ans[i]); 
	return 0;
}