A
Moolistar 有一张长长的纸条，上面打满了黑黑的小点。上面有 \(n＝2^k(k\le 30)\) 个均匀分布的点，编号从左到右、从 \(0\) 到 \(n-1\)。Moolistar 开始将这条纸带对折，他把纸带右半边折到了左半边的下面，重复折叠 \(k\) 次后，纸带变成了 \(n\) 层的纸片，记从上到下点的编号为 \(a_0,a_1,...,{n—1}\)。Moolistar 觉得数列 \(\{a_n\}\) 十分有趣，于是想请你对数列进行一些计算。
定义二元函数 \(F(l,r)＝a_l+a_{l+1}\otimes a_{l+2}+a_{l+3}\otimes a_{l+4}+....ar\)，其中当 \(l\) 是偶数时 \(+\) 的优先级 \(\otimes\) 比高，否则 \(\otimes\) 的优先级比 \(+\) 高。
有 \(m(m\le 5e7)\) 个询问，给定 \(l,r\)，回答 \(F(l,r)\).
B
求 \(\sum_{i=0}^n (a^i+b^i+c^i)^k\)
二项式定理展开再等比数列求和。
C
你要把数列分成若干段，且相邻的段最小值差的绝对值必须大于 \(m\).
考虑递推 \(i\)，顺便维护一个数组 \(f_{i,j}\) 表示当前以 \(i\) 结束分了若干段，当前段的最小值是 \(j\).
维护单调栈，考虑处理单调栈中每个数的贡献。
\(f(i,a[st[j]])\leftarrow f(i-1,st[a[j]])+\sum_{p=st[j-1]}^{st[j]-1} (\sum_{k=0}^{a_i-m}f(p,k)+\sum_{k=a_i+m}^{\infty} f(p,k))\)
若单调栈踢出了某数 \(a[st[tp]]\)，其贡献如何减去呢？
\(f(i,a[st[tp]])\leftarrow f(i-1,a[st[tp]])-\sum_{p=st[j-1]}^{st[j]-1} (\sum_{k=0}^{a_i-m}f(p,k)+\sum_{k=a_i+m}^{\infty} f(p,k))\).
我们可以考虑主席树。我们先把 \(f(i-1)\) 复制到 \(f(i)\)，然后再去做贡献就好了。
但是贡献如何计算呢？发现贡献是一个二维前缀和的形式，难道要历史版本和吗？
实则不然，我们直接维护一个前缀和的形式。
可以用类似树状数组维护区间的形式维护。？
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,mod=1e9+7,B=1e9;
int n,m,a[N],st[N],tp;
int rt[N],sum[N<<6],sum2[N<<6],ls[N<<6],rs[N<<6],tot;
int modify(int pre,int l,int r,int x,int v,int v2) {
int p=++tot;
if(l==r) {
sum[p]=(sum[pre]+v)%mod; sum2[p]=(sum2[pre]+v2)%mod;
return p;
}
int mid=(l+r)/2;
ls[p]=ls[pre]; rs[p]=rs[pre];
sum[p]=(sum[pre]+v)%mod; sum2[p]=(sum2[pre]+v2)%mod;
if(x<=mid) ls[p]=modify(ls[pre],l,mid,x,v,v2);
else rs[p]=modify(rs[pre],mid+1,r,x,v,v2);
return p;
}
int query(int p,int q,int l,int r,int x,int y,int k1,int k2) {
if(x<=l&&r<=y)
return ((1ll*sum[p]*k1%mod-sum2[p])%mod-(1ll*sum[q]*k2%mod-sum2[q])%mod+mod)%mod;
int mid=(l+r)/2,res=0;
if(x<=mid) res=(res+query(ls[p],ls[q],l,mid,x,y,k1,k2))%mod;
if(y>mid) res=(res+query(rs[p],rs[q],mid+1,r,x,y,k1,k2))%mod;
return res;
}
int ask(int l,int r,int x,int y) {
if(x>y) return 0;
x=max(x,1); y=min(y,B);
l=max(l,1);
return query(rt[r],rt[l-1],1,B,x,y,r+1,l);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
int root=rt[i-1];
while(tp&&a[i]<=a[st[tp]]) {
int tmp=(ask(st[tp-1],st[tp]-1,1,a[st[tp]]-m)+ask(st[tp-1],st[tp]-1,a[st[tp]]+m,B))%mod;
if(tp==1) tmp=(tmp+1)%mod;
root=modify(root,1,B,a[st[tp]],-tmp,-1ll*tmp*i%mod);
tp--;
}
int tmp=((tp==0?1:0)+ask(st[tp],i-1,1,a[i]-m)+ask(st[tp],i-1,a[i]+m,B))%mod;
tmp=(tmp+mod)%mod;
rt[i]=modify(root,1,B,a[i],tmp,1ll*tmp*i%mod);
st[++tp]=i;
}
printf("%d\n",(ask(n,n,1,B)+mod)%mod);
return 0;
}
D
有若干网线，每个网线只可连接其对应集合里的所有点中的两个。每个点只能被连接一根网线。
求最多有多少网线可以连到两个点。
是一个匹配问题。但是一根网线只能连 \(0\) 或 \(2\) 个点让人头疼。
考虑每根网线建立两个虚点，两个虚点建边，这两个点都连向这根网线的集合里的所有点。
跑一般图最大匹配。
若能匹配到两个点，那么这根网线的贡献为 \(2\),否则为 \(1\).（因为中间会有一个匹配）。