Loj 2251 树状数组

Posted on | Views:

树套树.

手玩一下可以发现,这种写法中, ${\rm Add}(x)$ 对 ${\rm Find}(y)$ 有贡献,当且仅当 $y\ge x$ .

于是 $\rm Add​$ 是单点修改, $\rm Find​$ 是查询后缀和.

记 $sum(l,r)$ 表示 $[l,r]$ 区间内所有数的异或和.

因为 $\rm Find$ 特判了 $l=0$ ,所以对于每次询问 ${\rm Query}(l,r) $ 要分情况讨论.

当 $l=1$ 时,答案正确需要满足 $sum(1,r)=sum(r,n)$ ,即 $sum(1,n)=sum(r)$ .

而 $sum(1,n)$ 已知,需要查询 $r$ 被修改次数为奇/偶的概率.

当 $l\neq 1$ 时,答案正确需要满足 $sum(l,r)=sum(l-1,n)\oplus sum(r,n)$ ,即 $sum(l-1)=sum(r)$ .

需要查询 $l-1,r$ 这两个位置修改总次数为偶数的概率.

因为每次修改时,区间内的两个位置不可能同时被修改,所以不能简单的维护每个位置被修改奇/偶次的概率.

而是需要对于每个点对 $(l,r)$ ,维护它们修改总次数为奇/偶次的概率.

每个点对是二维平面上的一个点,每次修改一个矩形内的点权,查询单点的权值,这可以用标记永久化的树套树维护.

查询 $r$ 被修改次数为奇/偶的概率可以看成是查询 $(0,r)$ 这个点对修改总次数为奇/偶的概率,就不用另外维护了.

时间复杂度 $O(n+m\log^2 n)$ ,空间复杂度 $O(n\log^2 n)$ .

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=1e5+10;
int n,m;
int merge(int x,int y)
{
	return add(mul(x,P+1-y),mul(y,P+1-x));
}
namespace In
{
	struct node
	{
		int ls,rs,val;
	}Tree[MAXN*200];
#define root Tree[o]
	int idx=0;
	void upd(int &o,int l,int r,int L,int R,int c)
	{
		if(!o)
			o=++idx;
		if(L<=l && r<=R)
		{
			root.val=merge(root.val,c);
			return;
		}
		int mid=(l+r)>>1;
		if(L<=mid)
			upd(root.ls,l,mid,L,R,c);
		if(R>mid)
			upd(root.rs,mid+1,r,L,R,c);
	}
	int query(int o,int l,int r,int y)
	{
		if(!o)
			return 0;
		int res=root.val;
		if(l==r)
			return res;
		int mid=(l+r)>>1;
		if(y<=mid)
			return merge(res,query(root.ls,l,mid,y));
		else
			return merge(res,query(root.rs,mid+1,r,y));
	}
}
namespace Out
{
	int rt[MAXN<<2];
	void upd(int o,int l,int r,int Lx,int Rx,int Ly,int Ry,int c)
	{
		if(Lx<=l && r<=Rx)
			return In::upd(rt[o],0,n,Ly,Ry,c);
		int mid=(l+r)>>1;
		if(Lx<=mid)
			upd(o<<1,l,mid,Lx,Rx,Ly,Ry,c);
		if(Rx>mid)
			upd(o<<1|1,mid+1,r,Lx,Rx,Ly,Ry,c);
	}
	int query(int o,int l,int r,int x,int y)
	{
		int res=In::query(rt[o],0,n,y);
		if(l==r)
			return res;
		int mid=(l+r)>>1;
		if(x<=mid)
			return merge(res,query(o<<1,l,mid,x,y));
		else
			return merge(res,query(o<<1|1,mid+1,r,x,y));
	}
}
int main()
{
	n=read(),m=read();
	int sum=0;
	for(int i=1;i<=m;++i)
	{
		int op=read(),l=read(),r=read();
		if(op==1)
		{
			int pr=fpow(r-l+1,P-2);
			Out::upd(1,0,n,l,r,l,r,mul(pr,2));
			Out::upd(1,0,n,0,l-1,l,r,pr);
			if(r+1<=n)
				Out::upd(1,0,n,l,r,r+1,n,pr);
			sum^=1;
		}
		else
		{
			if(l==1 && sum==1)
				printf("%d\n",Out::query(1,0,n,0,r));
			else
				printf("%d\n",add(1-Out::query(1,0,n,l-1,r),P));
		}
	}
	return 0;
}