洛谷P4247 序列操作 [清华集训] 线段树
正解:线段树
解题报告:
通过这题我get了一个神奇的,叫,线段树五问的东西hhhh
听起来有点中二但感觉真正做题的时候还是比较有用的,,,?感觉会让条理清晰很多呢,所以放一下QwQ
→每个区间需要记录哪些值
→需要哪些标记
→如何叠加标记
→如何对区间进行整体修改
→如何合并区间
然后感觉按照这个思路想题挺好,写题解就jio得太僵硬了,,,思路不连贯,所以就还是不按照一问一答的方式理思路了QAQ
就直接考虑怎么解决两个修改操作和一个查询操作趴
有一定思维难度的应该在查询操作,先说下趴有这个铺垫两个修改都是对应着来的QAQ
可以考虑dp,设f[i,j]:前i个数选j个相乘的∑,转移就是f[i][j]=f[i-1][j]+f[i-1][j-1]*a[k]
然后显然可以先降一维,变成f[i]:选i个数相乘的∑,显然依然是欧克的
那合并就是f[i]=f[j]*f[i-j]
然后想好要维护什么东西之后修改操作打标记什么的肯定都是要以它为核心嘛,下面分别港下
首先是增加操作
可以考虑把增加之后的式子表示出来,大概是这样儿的嘛,(a1+c)*(a2+c)*...*(am+c)(本来操作3给的也是c嘛,名字重了我就define了下,令操作3给定的是m,即m个数相乘
然后暴力展开,再用上面的f表示出来大概就是这样儿的:
f[m]+f[m-1]*c*m+f[m-2]*c*(m-1)*(m-2)/2+...
然后再整理下就是∑f[i]*cm-i*C(i,m)(,,,我布吉岛我C里面的mi写反麻油,反正就是说m个中选i个QwQ
关于f[j]*ci-j都挺好理解的,可能比较突兀的是那个C,但其实这个也是比较好get的,这儿随便说下趴
就现在是有m个数字,然后有i个f会被选出来,剩下的m-i个就都是c嘛,然后就乘一个m个中选i个的组合数
然后取反操作就,比较简单?
可以考虑直接和原来的tag异或一下就好,这样就直接做到改变符号辣
综上,这题应该就写完辣?
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define ri register int
#define rb register bool
#define lc(x) ls(x),l,mid
#define rc(x) rs(x),mid+1,r
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int N=50000+10,inf=1e9,mod=19940417,C=25;
int n,q,c[N][C],tag[N<<2],rev[N<<2];
bool gdgs=1;
struct segtr{int f[C];}tr[N<<2];
il int read()
{
register char ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il char rdch(){register char ch=gc;while(ch!='I' && ch!='R' && ch!='Q')ch=gc;return ch;}
il segtr operator + (segtr gd,segtr gs)
{
segtr gdgs;
rp(i,0,20){gdgs.f[i]=0;rp(j,0,i)gdgs.f[i]=(gdgs.f[i]+gd.f[j]*gs.f[i-j]%mod)%mod;}
return gdgs;
}
il void pre(){c[0][0]=1;rp(i,1,n){c[i][0]=1;rp(j,1,min(i,(int)20))c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}
void build(ri x,ri l,ri r)
{
if(l==r){tr[x].f[0]=1;tr[x].f[1]=(read()%mod+mod)%mod;return;}
ri mid=(l+r)>>1;build(lc(x));build(rc(x));tr[x]=tr[ls(x)]+tr[rs(x)];
}
il void revers(ri x){rp(i,1,20)if(i&1)tr[x].f[i]=mod-tr[x].f[i];rev[x]^=1;tag[x]=mod-tag[x];}
il void cover(ri x,ri l,ri r,ri dat)
{
segtr gdgs;gdgs.f[0]=1;
rp(i,1,20)
{
int poww=1;gdgs.f[i]=0;
my(j,i,0)
{
gdgs.f[i]=(gdgs.f[i]+tr[x].f[j]*c[r-l+1-j][i-j]%mod*poww%mod)%mod;
poww=poww*dat%mod;
}
}
tr[x]=gdgs;tag[x]=(tag[x]+dat)%mod;
}
il void pushdown(ri x,ri l,ri r)
{
if(rev[x]){revers(ls(x));revers(rs(x));rev[x]^=1;}
if(tag[x]){ri mid=(l+r)>>1;cover(lc(x),tag[x]);cover(rc(x),tag[x]);tag[x]=0;}
}
void modify_tag(ri x,ri l,ri r,ri to_l,ri to_r,ri dat)
{
if(to_l<=l && r<=to_r){ cover(x,l,r,dat);return;}
pushdown(x,l,r);ri mid=(l+r)>>1;if(to_l<=mid)modify_tag(lc(x),to_l,to_r,dat);if(to_r>mid)modify_tag(rc(x),to_l,to_r,dat);
tr[x]=tr[ls(x)]+tr[rs(x)];
}
void modify_rev(ri x,ri l,ri r,ri to_l,ri to_r)
{
if(to_l<=l && r<=to_r)return void(revers(x));
pushdown(x,l,r);ri mid=(l+r)>>1;if(to_l<=mid)modify_rev(lc(x),to_l,to_r);if(to_r>mid)modify_rev(rc(x),to_l,to_r);
tr[x]=tr[ls(x)]+tr[rs(x)];
}
segtr query(ri x,ri l,ri r,ri to_l,ri to_r)
{
if(to_l<=l && r<=to_r)return tr[x];
pushdown(x,l,r);ri mid=(l+r)>>1;
if(to_r<=mid)return query(lc(x),to_l,to_r);
if(to_l>mid)return query(rc(x),to_l,to_r);
return query(lc(x),to_l,to_r)+query(rc(x),to_l,to_r);
}
main()
{
// freopen("4247.in","r",stdin);freopen("4247.out","w",stdout);
n=read();pre();q=read();build(1,1,n);
while(q--)
{
register char ch=rdch();
if(ch=='I'){ri x=read(),y=read(),z=(read()%mod+mod)%mod;modify_tag(1,1,n,x,y,z);}
if(ch=='R'){ri x=read(),y=read();modify_rev(1,1,n,x,y);}
if(ch=='Q'){ri x=read(),y=read(),z=read();printf("%lld\n",query(1,1,n,x,y).f[z]);}
}
return 0;
}
/*
然后有个小bug,,,
就cover函数里其实i的循环应该是到max(20,r-l+1)?
但是
反正过了我就懒得改了QAQ
然后注意一下,,,要开ll,,,好像是要不要开的我看别人代码没开
但我不开就麻油满分,,,QAQ不知道是我哪儿写丑了还是怎么QAQ
*/