题面
解题思路
这种题目本质上先获得维护确定区间的方法，然后利用一种奇怪的方式扩展到任意子区间。
令ans[l,r]表示把[l,r]区间并起来的结果
我们先考虑对于确定的询问[l,r],ans[l,r]如何求解。我们可以枚举r然后维护这样的一个数组，
∑
i
=
l
r
r
e
s
[
i
]
\sum_{i=l}^rres[i]
∑i=lrres[i]表示[l,r]的答案。其实对于确定的r而言，res[i]表示已经添加了[l+1,r]的区间后，加入l这个区间会获得的增量。考虑使用线段树维护，由于势能均摊的性质，我们可以在
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)的复杂度完成维护。
进一步的考虑
∑
i
=
l
r
a
n
s
[
l
,
i
]
\sum_{i=l}^rans[l,i]
∑i=lrans[l,i]。即固定左端点的答案。我们可以通过添加一个时间维度来进行维护。
进一步的考虑
∑
i
=
l
r
∑
j
=
i
r
a
n
s
[
i
,
j
]
\sum_{i=l}^{r}\sum_{j=i}^rans[i,j]
∑i=lr∑j=irans[i,j]。我们在上一步的基础上再添加一个距离维度就可以进行维护。
如果求确定区间的ans，我们只要用一个树状数组去维护。
如果求固定左区间的ans，我们只要用两个树状数组去维护。
如果求子区间的ans，我们只要用四个树状数组去维护。
复杂度
n
l
o
g
2
n
nlog^2n
nlog2n。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define lson rt * 2
#define rson rt * 2 + 1
typedef long long ll;
void read(int &x) {
x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
void write(ll x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int N = 4e5 + 100;
const int MOD = 998244353;
int clock;
int t1[N], t2[N], t3[N], t4[N];
void upd(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
if (a < 0) a += MOD;
}
void add(int *tree, int id, ll x) {
for (; id > 0; id -= id & -id) upd(tree[id], x);
}
int query(int *tree, int id) {
int sum = 0;
for (; id < N; id += id & -id) upd(sum, tree[id]);
return sum;
}
struct node {
int l, r, id;
}qu[N];
bool operator < (node a, node b) {
return a.r < b.r;
}
int n, m;
int sa[N], rev[N];
ll ans[N];
void insert(int id, int x, int t) {
add(t1, id, 1LL * x * id % MOD); add(t2, id, 1LL * (t - 1) * x * id % MOD);
add(t3, id, x); add(t4, id, 1LL * (t - 1) * x % MOD);
}
ll get(int id, ll t) {
return ((query(t1, id) * t - query(t2, id)) - (id - 1) * (query(t3, id) * t % MOD - query(t4, id)) % MOD) % MOD;
}
int ql[N], qr[N];
int tp;
int tree[N * 4], idx[N * 4], has[N];
void push_down(int rt) {
if (idx[rt] == 0) return;
idx[lson] = idx[rson] = idx[rt];
tree[lson] = tree[rson] = 1;
idx[rt] = tree[rt] = 0;
}
void upd(int l, int r, int rt) {
if (tree[rt] == 0) return;
if (idx[rt]) {
insert(idx[rt], -(has[r + 1] - has[l]), clock);
idx[rt] = tree[rt] = 0;
return;
}
int m = (l + r) / 2;
upd(l, m, lson);
upd(m + 1, r, rson);
}
void insert(int x, int rl, int rr, int l, int r, int rt) {
if (rl == l && rr == r) {
upd(l, r, rt);
tree[rt] = 1;
idx[rt] = x;
return;
}
push_down(rt);
int m = (l + r) / 2;
if (rr <= m) insert(x, rl, rr, l, m, lson);
else if (m < rl) insert(x, rl, rr, m + 1, r, rson);
else {
insert(x, rl, m, l, m, lson);
insert(x, m + 1, rr, m + 1, r, rson);
}
tree[rt] = tree[lson] + tree[rson];
}
ll qpow(ll x, ll n) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * x % MOD;
x = x * x % MOD;
n /= 2;
}
return res;
}
int main() {
//freopen("0.txt", "r", stdin);
read(n); read(m);
for (int i = 1; i <= n; i++) {
read(ql[i]); read(qr[i]);
has[++tp] = ql[i];
has[++tp] = qr[i];
}
sort(has + 1, has + tp + 1);
tp = unique(has + 1, has + tp + 1) - has - 1;
for (int i = 1; i <= m; i++) read(qu[i].l), read(qu[i].r), qu[i].id = i;
sort(qu + 1, qu + m + 1);
for (int i = 1, j = 1; i <= n && j <= m; i++) {
int l = lower_bound(has + 1, has + tp + 1, ql[i]) - has;
int r = lower_bound(has + 1, has + tp + 1, qr[i]) - has - 1;
insert(i, qr[i] - ql[i], i);
clock = i;
insert(i, l, r, 1, tp, 1);
while (j <= m && qu[j].r == i) {
ll res = get(qu[j].l, i);
int x = qu[j].r - qu[j].l + 1;
res = (res % MOD + MOD) % MOD;
res = res * qpow(1LL * x * (x + 1) / 2 % MOD, MOD - 2) % MOD;
ans[qu[j].id] = res;
j++;
}
}
for (int i = 1; i <= m; i++) write(ans[i]), puts("");
return 0;
}