Luogu P4247 [清华集训]序列操作
祭第五道黑题
叫序列操作的题怎么都这么恶心
coding30min，debug三小时，线段树你值得拥有
太久不写博客了，本来想集训完回家再一起写，但是de了线段树的bug真的敲不动主席树了，写（水）篇题解吧。
题意如下：
给定一个长度为n的序列。
有m次操作，操作分为：
1.区间加；
2.区间取负；
3.询问区间中选c个数乘积的和。
n,m<=50000，c<=10。
题目来源：bzoj2962
区间操作问题，很容易想到用线段树。
先放一下闫神讲的极简做法：（不是做法极简是说的极简）
维护区间选0~c个数的答案。
合并时枚举两边各选几个数。
区间加和区间取反都可以打标记。
时间复杂度O(mc2logn)
orz
反正我没完全懂，于是把这做法具体一点讲：
在题解里看到一篇讲了写线段树要思考的五个问题，觉得很好理解，这里借鉴一下思路来讲：
1.考虑每个区间维护哪些值？
构成线段树的基本元素之一，显然要考虑：
一般来说，维护的值，取决于题目询问的是什么。对于这题来说，就是维护每个区间选0~c(20)个数的答案。
2.需要添加哪些标记？
取决于会涉及如何修改树中的数据，加用常规的懒标记实现即可，区间取负可以直接标记。
3.标记如何叠加？
同区间若取了两次负，视为不取。
关于优先级，其实这道题哪个标记优先都可以写，本蒟蒻为了方便定义取负优先。
4.如何整体修改区间？
（1）：加法：假设区间 an—am +x
计算贡献为：(an+x)(a(n+1)+x)...(am+x)
=(an*a(n+1)+x*(an+a(n+1))+x^2)....(am+x)
=an*a(n+1)*a(n+2)*...*am+x*(an+a(n+1)+...+a(m-1))+...+x^n
找到规律了吧：结果为 sigma (j=0~i) x^(i-j)·随机 j 个a
不怎么方便，考虑一下优化。
右眼观察（滑稽）发现，特定的随机的j个a在计算过程中会被多次求值，因此只要直接计算它被包含了多少次就行了。
什么情况下这j个a会被选呢？从(p-j)个数中任意选出(i-j)个数的时候啊，因为这时，显然已经有j个数确定了，这时能选择多少种，最有多少种情况包括了这j个a。
so：ans[i] = sigma(j=0~i) x^(i-j)·ans[j]·C(p-j,i-j)
预处理组合数就行咯。
（2）取负：上面的神仙推导您都看懂了那理解这个应该相当简单了：
对于奇数个-1相乘，结果为-1，对于偶数个，结果是1，所以若考虑的是区间内奇数个元素，则取负，偶数个直接跳过，它好我也好。
5.区间如何合并？
ans[now][i]= sigma (j=0~i) ans[ls][j] * ans[rs][i-j]
毕竟是黑题，再附一些要注意的点：
1.处理加操作时，ans要从小到大维护。
2.选数时，要特判选0个时直接return。
上代码吧，这码量很线段树，很序列操作：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; #define gc c=getchar() #define r(x) read(x) #define ll long long #define ls (rt<<1) #define rs (rt<<1|1) template<typename T> inline void read(T&x){ x=0;T k=1;char gc; while(!isdigit(c)){if(c=='-')k=-1;gc;} while(isdigit(c)){x=x*10+c-'0';gc;}x*=k; } const int N=1e5+7; const int p=19940417; ll C[N][21]; struct Seg { bool tag1; ll tag2,a[21]; int siz; Seg() { tag1=0; tag2=0; memset(a,0,sizeof(a)); siz=1; } inline const ll& operator [](const int &x)const { return a[x]; } inline ll& operator [](const int &x) { return a[x]; } inline void reverse() { tag1^=1; if(tag2)tag2=p-tag2; for(int i=1;i<20;i+=2)if(a[i])a[i]=p-a[i]; } inline void increase(int x) { (tag2+=x)%=p; for(int i=min(20,siz);i;--i) { ll Tmp=x; for(int j=i-1;j;--j,(Tmp*=x)%=p) { (a[i]+=Tmp*a[j]%p*C[siz-j][i-j]%p)%=p; } (a[i]+=C[siz][i]*Tmp)%=p; } } }tr[N<<2]; inline Seg operator + (const Seg &a,const Seg &b) { Seg ret; ret[0]=1; ret.siz=a.siz+b.siz; for(int i=1;i<=min(ret.siz,20);++i) { ret[i]=(a[i]+b[i])%p; for(int j=1;j<i;++j) { (ret[i]+=a[j]*b[i-j])%=p; } } return ret; } inline void update(int rt) { tr[rt]=tr[ls]+tr[rs]; } inline void pushdown(int rt) { if(tr[rt].tag1) { tr[ls].reverse(); tr[rs].reverse(); tr[rt].tag1=0; } if(tr[rt].tag2){ tr[ls].increase(tr[rt].tag2); tr[rs].increase(tr[rt].tag2); tr[rt].tag2=0; } } int a[N]; void build(int rt,int l,int r) { if(l==r) { tr[rt][0]=1; tr[rt][1]=a[l]; return ; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); update(rt); } void reverse(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y){ tr[rt].reverse(); return; } pushdown(rt); int mid=(l+r)>>1; if(x<=mid)reverse(ls,l,mid,x,y); if(y>mid)reverse(rs,mid+1,r,x,y); update(rt); } void increase(int rt,int l,int r,int x,int y,int v) { if(x<=l&&r<=y){ tr[rt].increase(v); return; } pushdown(rt); int mid=(l+r)>>1; if(x<=mid)increase(ls,l,mid,x,y,v); if(y>mid)increase(rs,mid+1,r,x,y,v); update(rt); } Seg query(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y)return tr[rt]; pushdown(rt); int mid=(l+r)>>1; if(y<=mid)return query(ls,l,mid,x,y); else if(x>mid)return query(rs,mid+1,r,x,y); else return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y); } inline void pre(int n) { for(int i=0;i<=n;++i { C[i][0]=C[i][i]=1; for(int j=1;j<=min(i-1,20);++j) { C[i][j]=(C[i-1][j]+C[i-1][j-1])%p; } } } int main() { int n,q;r(n),r(q);pre(n); for(int i=1;i<=n;++i)r(a[i]),a[i]=(a[i]%p+p)%p; build(1,1,n); while(q--) { char opt[5];scanf("%s",opt); int l,r,x;r(l),r(r); switch(opt[0]) { case 'I':{r(x);x=(x%p+p)%p;increase(1,1,n,l,r,x);break;} case 'R':{reverse(1,1,n,l,r);break;} case 'Q':{r(x),printf("%lld ",query(1,1,n,l,r)[x]);break;} } } }
滚回寝室睡觉了，不然又要“晚上不要睡，早上不要起，你反了你了！”
祝各位黑题+1A