一些简单数据结构题，线段树或平衡树，一共八道题，其中 I,II,IV\mathrm{I,II,IV} 过水懒得写。

GSS−III\mathrm{GSS-III}

长度为 nn 的序列 AA，qq 次操作

  1. 操作 0  x  y0\;x\;y 把 AxA_x 修改为 yy
  2. 操作 1  l  r1\;l\;r 询问区间 [l,r][l,r] 的最大子段和(非空)

1≤n,q≤5×104,  ∣y∣,∣Ai∣≤100001\le n,q\le 5\times 10^4,\;\left|y\right|,\left|A_i\right|\le 10000

330ms 1.46GB

线段树维护 区间和、最大子段和、最大前缀和、最大后缀和 ，结构体+重载运算符是个好东西，核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct rec{
    int sum,mx,st,ed; //和，最大子段和、最大前缀和、最大后缀和
    rec() {}
    rec(int _a) {sum=st=ed=mx=_a;}
};
rec operator+(const rec a,const rec b) {
    rec t;
    t.mx=_max(a.ed+b.st,_max(a.mx,b.mx));
    t.st=_max(a.st,a.sum+b.st);
    t.ed=_max(b.ed,a.ed+b.sum);
    t.sum=a.sum+b.sum;
    return t;
}

GSS−V\mathrm{GSS-V}

长度为 nn 的序列 AA，qq 次询问：每次询问左端点在 [x1,y1][x_1, y_1] 之间，且右端点在 [x2,y2][x_2, y_2] 之间的最大子段和，数据保证 x1≤x2,y1≤y2x_1\leq x_2,y_1\leq y_2 ，但是不保证端点所在的区间不重合

1≤n,q≤10000,  ∣Ai∣≤100001\le n,q\le 10000,\;\left|A_i\right|\le 10000

132ms 1.46GB

这道题其实还可以加修改。

和上一道题的区别无非是左右端点不确定了，考虑延续上一题的做法，维护区间和、最大子段和、最大前缀和、最大后缀和，对于询问区间重不重合我们分类讨论。

  1. x1≤y1<x2≤y2x_1\le y_1\lt x_2 \le y_2 ： 那就是 [x1,y1][x_1,y_1] 的最大后缀和 + [y1+1,x2−1][y_1+1,x_2-1] 的区间和 + [x2,y2][x_2,y_2] 的最大前缀和
  2. x1≤x2≤y1≤y2x_1\le x_2 \le y_1 \le y_2 ：再分类讨论一下即可， [x1,y1][x_1,y_1] 的最大后缀 + [y1+1,y2][y_1+1,y_2] 的最大前缀 或 [x1,x2−1][x_1,x_2-1] 的最大后缀 + [x2,y2][x_2,y_2] 的最大前缀 或 [x2,y1][x_2,y_1] 的最大最大子段和。三种情况取 max⁡\max 即可

线段树和上一题一样，所以说待修也是可以的。

GSS−VI\mathrm{GSS-VI}

长度为 nn 的序列 AA，qq 次操作，操作类型如下：

  1. I p x 在 pp 处插入插入一个元素 xx
  2. D p 删除 pp 处的一个元素
  3. R p x 修改 pp 处元素的值为 xx
  4. Q l r 查询一个区间 [l,r][l,r] 的最大子段和

注: 在 pp 处插入 意思是在 p−1p-1 和 pp 之间

1≤n≤105,1≤q≤105,0≤∣Ai∣,∣x∣≤1041\le n \le 10^5,1\le q \le 10^5,0\le |A_i|,|x| \le 10^4

447ms 1.46GB

又是最大子段和。。无非是把它搬到了平衡树上，可以写 fhqTreap 或者 Splay。我菜，只会 fhqTreap ，merge,split 解决一切问题。注意细节，每个节点还要维护当前点的值，在 updata 时把左右孩子和自己的最大子段和信息合并。

还是那句话，重载运算符是个好东西。

GSS−VII\mathrm{GSS-VII}

给定一棵树，有 N(N≤100,000)N(N \le 100,000) 个节点，每一个节点都有一个权值 xi(∣xi∣≤10000)x_i (|x_i| \le 10000) ，你需要执行 Q(Q≤100,000)Q (Q \le 100,000) 次操作：

  1. 1  a  b1\;a\;b ：查询 (a,b)(a,b) 这条链上的最大子段和，可以为空（即输出 00)
  2. 2  a  b  c2\; a\;b\;c ：将 (a,b)(a,b) 这条链上的所有点权变为 c(∣c∣≤10000)c (|c| \le 10000)

570ms 1.46GB

把最大子段和搬到树上了。。。加一个重链剖分完事呗，区间修改也挺简单，多打个标记呗。

细节在询问，从两条链跳上来，最后合并的时候要把左边的 “reverse” 以下(就是交换最大前缀和,最大后缀和) ，因为两条链上来都是深度低的为左边。

GSS−VIII\mathrm{GSS-VIII}

给你长度为 NN 的序列 A(0≤Ai<232)A (0 \le A_i \lt 2^{32}) 下标从零开始

你需要支持 QQ 次操作

  1. I pos val 插入一个数字在第 pospos 个位置之前，0≤val<2320 \le val \lt 2^{32} 如果 pos=lenpos=len，那么你需要将这个数字放到序列末尾
  2. D pos 删除第 pospos 个元素
  3. R pos val 将第 pospos 个元素变为 val(0≤val<232)val(0 \le val \lt 2^{32})
  4. Q l r k 询问 (∑i=lrA[i]×(i−l+1)k) mod 232\left(\sum\limits_{i=l}^{r} A[i] \times (i - l + 1) ^ k\right) \bmod 2^{32} ，保证 0≤k≤100 \le k \le 10

1≤N,Q≤1051\le N,Q \le 10^5

1.50s 1.46GB

开始毒瘤了，首先这个删除插入肯定要平衡树，那查询的东西怎么维护呢？

发现 k≤10k\le 10 那就暴力维护 这个区间 “k次阶梯和” （自己瞎取的名儿），形式化的定义，（ aa 为一个序列，sizasiza 是 aa 的长度 ）：

g(a,k)=∑i=1sizaik⋅aig(a,k)=\sum_{i=1}^{siza} i^k \cdot a_i

那来考虑怎么维护，怎么合并信息 ，我们要合并 aa 序列和 bb 序列，且让 aa 在 bb 前，定义 g(c,k)=g(a,k)⋆g(b,k)g(c,k)=g(a,k)\star g(b,k) :

g(c,k)=∑i=1sizaik⋅ai+∑i=1sizb(i+siza)k⋅big(c,k)=\sum_{i=1}^{siza} i^k\cdot a_i+\sum_{i=1}^{sizb} (i+siza)^k\cdot b_i\\

然后就是大胆推式子，其实也不难：

∑i=1sizb(i+siza)k⋅bi=∑i=1sizb(∑t=0k(kt)⋅itsizak−t)bi=∑i=1sizb∑t=0k(sizak−t(kt))⋅itbi=∑t=0k(sizak−t(kt))∑i=1sizbit⋅bi=∑t=0k(sizak−t(kt))g(b,t)\begin{aligned} &\sum_{i=1}^{sizb} (i+siza)^k\cdot b_i\\ =&\sum_{i=1}^{sizb} \left(\sum_{t=0}^k \binom{k}{t}\cdot i^tsiza^{k-t}\right)b_i\\ =&\sum_{i=1}^{sizb} \sum_{t=0}^k \left(siza^{k-t}\binom{k}{t}\right) \cdot i^t b_i \\ =&\sum_{t=0}^k \left(siza^{k-t}\binom{k}{t}\right)\sum_{i=1}^{sizb} i^t\cdot b_i \\ =&\sum_{t=0}^k \left(siza^{k-t}\binom{k}{t}\right)g(b,t) \end{aligned}

然后便轻松得到了：

g(c,k)=g(a,k)+∑t=0k(sizak−t(kt))g(b,t)g(c,k)=g(a,k)+\sum_{t=0}^k \left(siza^{k-t}\binom{k}{t}\right)g(b,t)\\

写成结构体+重载运算符，方便调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct rec{
    ui g[11],siz;bool ept;
    rec() {memset(g,0,sizeof(g));siz=0;ept=1;}
    rec(ui val) {for(re int i=0;i<=10;++i) g[i]=val;siz=1;ept=0;}
};
rec operator*(const rec a,const rec b) {
    if(a.ept) return b;if(b.ept) return a;
    rec r;r.siz=a.siz+b.siz;r.ept=0;
    for(int k=0;k<=10;k++) {
        r.g[k]=a.g[k];
        ui pw=1;
        for(int t=0;t<=k;t++,pw*=a.siz) {
            r.g[k]+=pw*C[k][k-t]*b.g[k-t]; // C[n][m] 为组合数
        }
    }
    return r;
}

后记

其实仔细思考，这些数据结构体都不难，主要是难调，封装，重载运算符是个好东西，能是代码简洁，清晰易懂，方便复制，不容易出错