洛谷 4247 bzoj 2962 [清华集训2012]序列操作

发表于 | 阅读次数：
本文字数： 1.6k 字 | 阅读时长 ≈ 8 分钟

题意简述

给一个长度为 $n$ 的序列 $a$，支持 $q$ 个操作：
I l r x 区间元素整体 $+x$。

R l r 区间元素整体 $\times (-1)$

Q l r x 询问：从 $[l,r]$ 中选择 $x$ 个数的积的所有方案的和，$\bmod 19940417$。

$n,q\le 5\times 10^4$。

所有操作保证 $[l,r]$ 有意义。操作 I 中，$x\le 10^9$；操作 Q 中，$x\le min(r-l+1,20)$

思路

我们观察到 $x\le 20$。不妨在线段树中维护每一种情况的答案。设 $S[x]$ 表示当前节点中选择 $x$ 个数的积的所有方案的和。为了方便考虑，设 $S[0]=1$。然后，显然还需要维护取相反数的标记和加法标记。

然后开始线段树传 统 艺 能了。

如何合并左右儿子的答案

我们在左半边选 $a$ 个，右半边选 $b$ 个，那就一共选了 $a+b$ 个，贡献是 $lS[a]\times rS[b]$。其中 $lS,rS$ 表示左儿子，右儿子的 $S$ 数组。

如何单节点加值

我们其实就是要考虑这样一个东西：

$a_1\times a_2\cdots \times a_m$ 如何变成 $(a_1+x)(a_2+x)\cdots (a_m+x)$

每个括号里可能是 $a_i$，也可能是 $x$。

枚举 $i$ 个括号出了 $a_i$，剩下 $m-i$ 个括号出了 $x$，贡献为：

(a 中选 i 个数的积的所有方案的和) $\times x^{m-i}$。

那么，$S[m]$ （不要想歪）该怎么算呢？还是不好算。

其实是因为还差一步转换：我们考虑每个 $i$ 给 $m$ 的贡献。

根据上面的式子，当前的 $i$ 会给 $S[m]$ 加上 $S[i]\times x^{m-i}$ 。那么，加了多少遍呢？我们上面假设现在钦定了 $i$ 个括号出了 $a_i$，然后剩下 $m-i$ 个括号出了 $x$。剩下 $m-i$ 个括号显然不是唯一确定的，那么它们有多少种选择呢？显然是 $C_{len-i}^{m-i}$。其中 $len$ 表示线段树当前区间的长度。

于是，

如何单节点取反

显然，取反只会改变正负性，不改变绝对值，而且只有奇数位置会被改变正负性。

即：对于奇数的 $i$，$S[i]$ 变为 $-S[i]$。

到此，这题涉及到的全部操作都解决了。

代码

点击
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 54444
	#define mod 19940417
	#define int long long
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}

	// ==================== 预处理组合数
	int CC[N][30];
	void Init()
	{
		CC[0][0]=1;
		int n=5e4;
		F(i,1,n) 
		{
			CC[i][0]=1;
			F(j,1,min(20ll,i)) CC[i][j]=(CC[i-1][j-1]+CC[i-1][j])%mod;
		}
	}
	// ====================

	struct node{int l,r; bool f; int a,ans[22];};
	node operator+(node ls,node rs) // 合并区间就用重载运算符了
	{
		node cur;
		cur.l=ls.l; cur.r=rs.r; cur.f=0; cur.a=0;
		FK(cur.ans);
		F(i,0,min(20ll,ls.r-ls.l+1)) F(j,0,min(20ll-i,rs.r-rs.l+1))
		{
			cur.ans[i+j]=(cur.ans[i+j]%mod+ls.ans[i]*rs.ans[j]%mod+2*mod)%mod;
            // cur.ans[i+j]+=ls.ans[i]*rs.ans[j]
            // 话说取膜好丑啊...
		}
		return cur;
	}
	class SegmentTree
	{
	public:
		node tree[N<<2];
		#define ls index<<1
		#define rs index<<1|1
		#define L tree[index].l
		#define R tree[index].r
		#define C tree[index].f
		#define A tree[index].a
		#define S tree[index].ans
		#define lL tree[ls].l
		#define lR tree[ls].r
		#define lC tree[ls].f
		#define lA tree[ls].a
		#define lS tree[ls].ans
		#define rL tree[rs].l
		#define rR tree[rs].r
		#define rC tree[rs].f
		#define rA tree[rs].a
		#define rS tree[rs].ans

		#define up(index) tree[index]=tree[ls]+tree[rs]
		void Build(int l,int r,int index)
		{
			L=l,R=r; C=A=0; FK(S);
			if (l==r) 
			{
				S[0]=1; S[1]=(I()%mod+mod)%mod; // 为了方便合并左右，设 S[0]=1
				return;
			}
			int mid=(l+r)>>1;
			Build(l,mid,ls); Build(mid+1,r,rs);
			up(index);
		}
		void AddOne(int x,int index)
		{
			A=(A+x)%mod;

			int p[22]; p[0]=1;
			F(i,1,min(20ll,R-L+1)) p[i]=p[i-1]*x%mod; // 预处理出幂
			S[0]=1;
			D(i,min(20ll,R-L+1),1) F(j,0,i-1) 
			{
				S[i]=(S[i]+S[j]*p[i-j]%mod*CC[R-L+1-j][i-j]%mod)%mod;
                // S[i]+=S[j]*x^(i-j)*CC[len-j][i-j];
			}
			F(i,0,min(20ll,R-L+1)) S[i]=(S[i]%mod+mod)%mod;
		}
		void FlipOne(int index)
		{
			F(i,1,min(20ll,R-L+1)) S[i]=(i&1)?(mod-S[i]):S[i];
            // 奇数位置取反
			A=mod-A;
            // 注意：取反会影响到加法标记的！！！
			C^=1;
		}
		void PushDown(int index)
		{
			if (C)
			{
				FlipOne(ls); FlipOne(rs); C=0;
			}
			if (A)
			{
				AddOne(A,ls); AddOne(A,rs); A=0;
			}
		}
		void Add(int l,int r,int x,int index)
		{
			if (l>R or L>r) return;
			if (l<=L and R<=r) return AddOne(x,index);
			PushDown(index);
			Add(l,r,x,ls); Add(l,r,x,rs);
			up(index); 
		}
		void Flip(int l,int r,int index)
		{
			if (l>R or L>r) return;
			if (l<=L and R<=r) return FlipOne(index);
			PushDown(index);
			Flip(l,r,ls); Flip(l,r,rs);
			up(index);
		}
		node Query(int l,int r,int index)
		{
			if (l<=L and R<=r) return tree[index];

			PushDown(index);
			int mid=(L+R)>>1;
			if (mid<l)  return Query(l,r,rs);
			if (r<=mid) return Query(l,r,ls);
			return Query(l,r,ls)+Query(l,r,rs);
		}
	}T;

	int n,m;
	void Input()
	{
		Rd(2,&n,&m);
		T.Build(1,n,1);
	}
	void Soviet()
	{
		Init();
		F(i,1,m)
		{
			char s[3]; scanf("%s",s);
			if (s[0]=='I')
			{
				int l,r,x; Rd(3,&l,&r,&x);
				T.Add(l,r,x,1);
			}
			if (s[0]=='R')
			{
				int l,r; Rd(2,&l,&r);
				T.Flip(l,r,1);
			}
			if (s[0]=='Q')
			{
				int l,r,k; Rd(3,&l,&r,&k);
				node ans=T.Query(l,r,1);
				printf("%lld\n",ans.ans[k]);
			}
		}
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
	#undef int //long long
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w