本文共 4687 字，大约阅读时间需要 15 分钟。

A

题目描述

给定一个序列 \(a\)，保证 \(a_i\) 互不相同。你需要重新排列 \(a\)，使得 \(a\) 中任意两个相邻位置都包含一个奇数和偶数。对于每个数，它的代价是\(|\)初始位置减重排后的位置\(|\) 。请输出保证总代价最小的前提下，字典序最小的 \(a\)

\(1\leq n\leq 10^5,1\leq a_i\leq 10^9\)

B

题目描述

定义 \(f(n)\) 表示将 \(n\) 划分为若干 \(m\) 的非负整数次幂的和的方案数。定义 \(g(n)\) 表示 \(k\) 个 \(f(n)\) 的卷积。给定 \(n,m,k\)，求出 \(\sum_{i=0}^n g(i)\) 对 \(1e9+7\) 取模后的结果。

\(0\leq n\leq 10^{18},2\leq m\leq 10^{18},1\leq k\leq20\)

解法

\(k=1\) 的情况，此时 \(f_m\) 可以使用组合意义生成函数卷积：

有一个小 \(\tt trick\)，因为要求系数和，所以可以把原来的多项式再乘以 \(\frac{1}{1-x}\) 就可以直接求 \([x^n]\)

然后问题变成了求第 \(n\) 项的系数，假如我们加入 \(m^i\) 的物品，那么起作用的只有 \(i=n\mod m^i\) 这些位置的值。所以不难设计出状态，设 \(f(i,j)\) 表示加入了 \(i\) 件物品，容量是 \(jm^i+(n\% m^i)\) 的方案数（有一点点不严谨但是没关系），转移不难写出：

其中 \(bit(n,i-1)\) 表示 \(n\) 在第 \(i-1\) 为上的值，因为 \(jm^i+(n\%m^i)\) 可以从 \(xm^i+(n\%m^i)\) 转移而来，也就是 \(xm\cdot m^{i-1}+(n\% m^{i-1})+bit(n,i-1)\)

这个东西第二维很大，又是那个神奇的套路！我们假设 \(f(i,j)\) 是 \(j\) 的 \(i\) 次多项式，然后归纳证明这个结论。原因就蕴含在转移中，\(f(i-1,xm+bit(n,i-1))\) 是一个关于 \(xm+bit(n,i-1)\) 的多项式，也就是关于 \(x\) 的 \(i-1\) 次多项式。那么我们把这些多项式求了一个前缀和，所以是一个 \(i\) 次多项式。

所以用 \(O(i^3)\) 求出 \(O(i)\) 个点值就可以 \(O(i^2)\) 插值求出这个多项式，因为第一维超级小所以复杂度是对的。

那么如果 \(k>1\) 呢？那么我们把 \(m^i\) 的物品做若干次就行了，转移有点小修改，但是大体思路是一样的，时间复杂度 \(O(k^3\log^3_mn)\)

C

题目描述

定义一个括号序列是合法的，当且仅当它的任意一个前缀满足 ( 的数量不小于 ) 的数量，且整个序列中左括号和右括号的数量相等。（不要以为这句话没有用哦，其实它是一个提示）

定义一个括号序列是好的，当且仅当存在两个并为整个序列的子序列，使得每个子序列都是合法的括号序列。现在给你一个长为 \(n\) 的括号序列，有 \(m\) 次询问，每次询问给定一个区间 \([L,R]\)，你需要求出有多少个子区间是好的括号序列。

\(n,m\leq3e5,1\leq L\leq R\leq n\)

解法

我竟然都能把结论猜出来，但是结论后面的维护也超难的好伐。

结论：一个好的括号序列等价于，把左括号看做 \(2\) 右括号看做 \(-1\)，要求每个前缀都 \(\geq 0\)；把右括号看做 \(2\) 左括号看做 \(-1\)，要求每个后缀都 \(\geq0\)

考虑证明，必要性显然。充分性可以构造方案证明。具体来说，我们考虑先构造出一个满足（的位置为2或1，）的位置为-2或-1的序列，使得它们和为0，且任意前缀和。这个可以考虑将（当成2，）当成-1得到的序列，每次将最后一个还没减小过的括号-1，直到序列总和为0，显然这样是可以达到的，并且任意时刻仍然满足前缀和和后缀和的限制。得到这个序列以后，可以将2和-2当成两个子序列的公共部分，奇数个的1和奇数个的-1分配给第一个序列，偶数个的1和偶数个的-1分配给第二个序列，这样两个序列前缀和的差的绝对值任意时刻不会>1，又知道他们总和，因此显然是合法的方案。

考场上我写的是暴力判断每个区间是否是好的，然后二维数点，时间复杂度 \(O(n^2\log n)\)

这时候要仔细观察限制，前缀\(\geq0\)和后缀\(\geq0\) 其实是两个相对独立的限制条件。现在的思路就是解决这两个限制。

考虑后缀 \(\geq0\) 这个限制条件，固定一个点，那么它延伸到的范围是固定的，而且延伸到的地方合法未延伸到的地方不合法，这就是一个很好的性质了，可以预处理 \(b[i]\) 表示 \(i\) 最多向左延伸多少，这个就相当于找前缀和数组第一个比它大的数，直接用单调栈做就可以了。

前缀 \(\geq0\) 这个限制可以通过离线解决。我们让右端点从左往右扫，考虑到答案是统计 \([L,R]\) 的子区间，有一个骚操作：我们把贡献记在左端点上，可以用线段树去维护左端点的贡献。

具体讲一讲怎么离线，遇到左括号时，它是可以作为左端点的，那我们就激活这个点。遇到右括号时，求 \([1,i]\) 的区间最小值，要删去不合法的左端点。右括号可以作为右端点，所以我们把 \([b[i],i]\) 中的激活左端点贡献\(+1\)，询问就直接区间查询。

线段树都是一些常规操作，具体要维护什么可以扫一眼我的代码。时间复杂度 \(O(n\log n)\)

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int M = 300005;const int inf = 1e9;#define ll long long #define pii pair
       
        int read(){    int x=0,flag=1;char c;    while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();    return x*flag;}int n,m,top,a[M],b[M],p[M];char s[M];int mi[4*M],fl[4*M],pos[4*M],pd[4*M];ll sum[4*M],tag[4*M],ans[M];struct node{	int l,r,id;	bool operator < (const node &b) const	{		return r
        
         >1;down(i); if(mid>=id) fuck(i<<1,l,mid,id,f); else fuck(i<<1|1,mid+1,r,id,f); up(i);}pii get(int i,int l,int r,int L,int R)//求出最小值{ if(l>R || L>r) return make_pair(inf,0); if(L<=l && r<=R) return make_pair(mi[i],pos[i]); int mid=(l+r)>>1;down(i); return min(get(i<<1,l,mid,L,R),get(i<<1|1,mid+1,r,L,R));} void upd(int i,int l,int r,int L,int R,int f)//区间加 { if(l>R || L>r) return ; if(L<=l && r<=R) { mi[i]+=f;fl[i]+=f; return ; } int mid=(l+r)>>1;down(i); upd(i<<1,l,mid,L,R,f); upd(i<<1|1,mid+1,r,L,R,f); up(i);}void add(int i,int l,int r,int L,int R)//区间更新答案{ if(l>R || L>r) return ; if(L<=l && r<=R) { sum[i]+=pd[i]; tag[i]++; return ; } int mid=(l+r)>>1;down(i); add(i<<1,l,mid,L,R); add(i<<1|1,mid+1,r,L,R); up(i);}ll ask(int i,int l,int r,int L,int R)//区间问答案 { if(l>R || L>r) return 0; if(L<=l && r<=R) return sum[i]; int mid=(l+r)>>1;down(i); return ask(i<<1,l,mid,L,R)+ask(i<<1|1,mid+1,r,L,R);}int main(){ n=read();m=read(); scanf("%s",s+1); p[0] = 0; for(int i=1;i<=n;i++)//jzm的手笔 { if(s[i]=='(') a[i]=a[i-1]-1; else a[i]=a[i-1]+2; while(top>=0 && a[p[top]]<=a[i]) top--; if(top == -1) b[i] = 1; else b[i]=p[top]+2;//表示最多能延伸到哪 p[++ top] = i; } for(int i=1;i<=m;i++) { q[i].l=read();q[i].r=read();q[i].id=i; } sort(q+1,q+1+m); for(int i=0;i<=4*n;i++) mi[i]=inf; for(int i=1,j=1;i<=n;i++) { if(s[i]=='(') { fuck(1,1,n,i,1);//激活这个位置 upd(1,1,n,1,i,2); } if(s[i]==')') { upd(1,1,n,1,i,-1); pii tmp=get(1,1,n,1,i); while(tmp.first<0)//删除不行的位置 { fuck(1,1,n,tmp.second,0); tmp=get(1,1,n,1,i); } add(1,1,n,b[i],i);//加答案 } while(j<=m && q[j].r<=i) { ans[q[j].id]=ask(1,1,n,q[j].l,i); j++; } } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);}/*前缀：( 2 ; ) -1 >=0后缀：) 2 ; ( -1 >=0*/