[bzoj]2962序列操作

标签： 线段树

题目链接

题意

给你一串序列，要你维护三个操作：

1.区间加法

2.区间取相反数

3.区间内任意选k个数相乘的积

题解

第三个操作看起来一脸懵逼啊。

其实是可以合并的。

$ c[o].s[i]=\sum_{j=0}^{20}c[lc].s[j]×c[rc].s[i-j]\(
跟\)C_m^n=\sum_{i=0}n C_n^i×C_{m-n}{n-i} $这个等式是一个道理的吧。

然后想怎么维护加和取反。

取反比较容易，把取奇数个的答案变成相反数。

加法就稍微复杂一点。

假如p是加上的数,s[i]是区间内取k个数的答案。

Code

(不知道为什么常数很大，bzoj上43s才过)

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)

inline int read()

{

	int sum=0,p=1;char ch=getchar();

	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();

	if(ch=='-')p=-1,ch=getchar();

	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();

	return sum*p;

}

const int mod=19940417;

const int maxn=1e5+20;

struct node {

	int s[21];

	int add,rev;

	void Merge(node a,node b)

		{

			REP(i,0,20)

			{

				s[i]=0;

				REP(j,0,i)s[i]=(s[i]+(ll)a.s[j]*b.s[i-j])%mod;

			}

		}

};

node c[maxn*4];

int n;

int a[maxn],C[maxn][25];

#define lc (o<<1)

#define rc (o<<1 | 1)

#define left lc,l,mid

#define right rc,mid+1,r

void Reverse(int o,int l,int r)

{

	c[o].rev^=1;

	c[o].add*=-1;

	REP(i,0,20)

		if(i & 1)c[o].s[i]*=-1;

}

void Add(int o,int l,int r,ll add)

{

	c[o].add=(c[o].add+add)%mod;

	DREP(i,min(20,r-l+1),0)

	{

		ll X=add;

		DREP(j,i-1,0)

		{

			c[o].s[i]=(c[o].s[i]+(ll)c[o].s[j]*X%mod*C[r-l+1-j][i-j])%mod;

			X=(ll)X*add%mod;

		}

	}

}

void pushdown(int o,int l,int r)

{

	int mid=(l+r)>>1;

	if(c[o].rev)

	{

		c[o].rev=0;

		Reverse(lc,l,mid);

		Reverse(rc,mid+1,r);

	}

	if(c[o].add)

	{

		Add(lc,l,mid,c[o].add);

		Add(rc,mid+1,r,c[o].add);

		c[o].add=0;

	}

}

void make_tree(int o,int l,int r)

{

	if(l==r)

	{

		c[o].s[0]=1;c[o].s[1]=a[l];

		c[o].add=c[o].rev=0;

		return;

	}

	int mid=(l+r)>>1;

	make_tree(left);

	make_tree(right);

	c[o].Merge(c[lc],c[rc]);

}

int q;

void init()

{

	n=read();q=read();

	REP(i,1,n)a[i]=read();

	C[0][0]=1;

	REP(i,1,n)

	{

		C[i][0]=1;

		REP(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

	}

	make_tree(1,1,n);

}

void updatea(int ql,int qr,ll x,int o,int l,int r)

{

	if(ql<=l && r<=qr)

	{

		Add(o,l,r,x);

		return;

	}

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(ql<=mid )updatea(ql,qr,x,left);

	if(qr>mid)updatea(ql,qr,x,right);

	c[o].Merge(c[lc],c[rc]);

}

void updater(int ql,int qr,int o,int l,int r)

{

	if(ql<=l && r<=qr)

	{

		Reverse(o,l,r);

		return;

	}

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(ql<=mid)updater(ql,qr,left);

	if(qr>mid)updater(ql,qr,right);

	c[o].Merge(c[lc],c[rc]);

}

node query(int ql,int qr,int o,int l,int r)

{

	if(ql<=l && r<=qr)return c[o];

	int mid=(l+r)>>1;

	pushdown(o,l,r);

	if(ql>mid)return query(ql,qr,right);

	else if(qr<=mid)return query(ql,qr,left);

	else

	{

		node a=query(ql,mid,left),b=query(mid+1,qr,right);

		node c;c.Merge(a,b);

		return c;

	}

}

void doing()

{

	REP(i,1,q)

	{

		char ch;

		//cin>>ch;

		scanf("\n%c",&ch);

		if(ch=='I')

		{

			int l=read(),r=read();ll x=read();

			updatea(l,r,x,1,1,n);

		}

		else if(ch=='R')

		{

			int l=read(),r=read();

			updater(l,r,1,1,n);

		}else

		{

			int l=read(),r=read(),k=read();

			node x=query(l,r,1,1,n);

			printf("%d\n",(x.s[k]+mod)%mod);

		}

	}

}

int main()

{

	freopen("sequence.in","r",stdin);

	freopen("sequence.out","w",stdout);

	init();

	doing();

	return 0;

}