若转载请注明出处！！！
GSS1 —— GSS8 简述做法加代码。
GSS1
给出了序列\(A[1]\)，\(A[2]\)，…，\(A[N]\)。 \((a[i]≤15007,1≤N≤50000)\)。查询定义如下： 查询\((x,y)=max\{a[i]+a[i+1]+...+a[j];x≤i≤j≤y\}\)。 给定M个查询，程序必须输出这些查询的结果。
思路：
我们维护四个值：
sum, lsum, rsum, msum
然后进行更新，静态查询即可。
具体讲解见 这里了啦
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 50010
#define inf 1 << 30
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
struct tree{
int lsum, rsum, sum, msum;
} z[mn << 2];
inline void update(int rt){
z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;
z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1].sum + z[rt << 1 | 1].lsum);
z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1 | 1].sum + z[rt << 1].rsum);
z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = read();
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline tree query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){return z[rt];}
int m = (l + r) >> 1;
bool fl = false, fr = false;
tree tl, tr, res;
if (nowl <= m){
if(m<nowr){
tl = query(lson, nowl, nowr);
tr = query(rson, nowl, nowr);
res.sum = tl.sum + tr.sum;
res.lsum = max(tl.lsum, tl.sum + tr.lsum);
res.rsum = max(tr.rsum, tr.sum + tl.rsum);
res.msum = max(max(tl.msum, tr.msum), tl.rsum + tr.lsum);
return res;
}else{
return query(lson, nowl, nowr);
}
}else{
return query(rson, nowl, nowr);
}
}
int n, m;
int main(){
n = read();
build(root);
m = read();
go(i, 1, m, 1) {
int x = read(), y = read();
cout << query(root, x, y).msum << "\n";
}
return 0;
} GSS2
给出 \(n\) 个数，\(q\) 次询问，求最大子段和，相同的数只算一次。
思路：
因为没有修改，我们考虑离线做。
我们把询问 \([l, r]\) 按照 \(r\) 的升序排序，在线段树内维护 \(sum\) 和 它的历史最大值 \(hmax\)，我们可以记 \(pre[i]\) 作为第 \(i\) 个元素的上一个元素的位置。
我们把原数组按读入顺序加入，我们只需要把这个 \(a[i]\) 在区间 \([pre[i] + 1, i]\) 上区间加即可，然后查询时直接查询 \([l, r]\) 的历史最大值。
记得加上维护左右儿子的 \(sum\) 最大值和左右儿子 \(hmax\) 的最大值，这样我们才能更新 本节点的 \(hmax\)。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
struct Que{
ll l, r, id;
} q[mn];
ll b[mn], ans[mn];
ll pre[mn << 1], suf[mn << 1];
inline bool cmp(Que a,Que b){
return a.r < b.r;
}
struct tree{
ll sum, hsum, cols, hcol;
};
struct SegmentTree{
tree z[mn << 2];
inline tree operation(tree a,tree b){
return (tree){max(a.sum, b.sum), max(a.hsum, b.hsum)};
}
inline void update(int rt){
z[rt].sum = max(z[rt << 1].sum, z[rt << 1 | 1].sum);
z[rt].hsum = max(z[rt << 1].hsum, z[rt << 1 | 1].hsum);
}
inline void color(int l, int r, int rt){
z[rt].hsum = max(z[rt].hsum, z[rt >> 1].hcol + z[rt].sum);
z[rt].sum += z[rt >> 1].cols;
z[rt].hcol = max(z[rt].hcol, z[rt >> 1].hcol + z[rt].cols);
z[rt].cols += z[rt >> 1].cols;
}
inline void coloring(int l,int r,int rt,ll v){
z[rt].sum += v;
z[rt].hsum = max(z[rt].sum, z[rt].hsum);
z[rt].cols += v;
z[rt].hcol = max(z[rt].cols, z[rt].hcol);
}
inline void push_col(int l,int r,int rt){
int m = (l + r) >> 1;
color(lson);
color(rson);
z[rt].hcol = z[rt].cols = 0;
}
inline void modify(int l,int r,int rt,int nowl,int nowr,ll v){
if(nowl<=l && r<=nowr){
coloring(bson,v);
return;
}
int m = (l + r) >> 1;
push_col(bson);
if (nowl <= m)
modify(lson, nowl, nowr, v);
if(m<nowr)
modify(rson, nowl, nowr, v);
update(rt);
}
inline tree query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr)
return z[rt];
int m = (l + r) >> 1;
push_col(bson);
if(nowl<=m){
if(m<nowr)
return operation(query(lson, nowl, nowr), query(rson, nowl, nowr));
else
return query(lson, nowl, nowr);
}else{
return query(rson, nowl, nowr);
}
}
} tr;
int n, m;
int main(){
n = read();
go(i, 1, n, 1) b[i] = read(), pre[i] = suf[b[i] + 100000], suf[b[i] + 100000] = i;
m = read();
go(i, 1, m, 1) q[i].l = read(), q[i].r = read(), q[i].id = i;
sort(q + 1, q + m + 1, cmp);
int y = 1;
go(i, 1, n, 1){
tr.modify(root, pre[i] + 1, i, b[i]);
while(y<=m&&q[y].r<=i){
ans[q[y].id] = tr.query(root, q[y].l, q[y].r).hsum;
y++;
}
}
go(i, 1, m, 1)
printf("%lld\n", ans[i]);
return 0;
} GSS3
\(n\) 个数，\(q\) 次操作
-
0 \(x\) \(y\) 把 \(A_x\) 修改为 \(y\)
-
1 \(l\) \(r\) 询问区间 \([l, r]\) 的最大子段和
思路
直接在GSS1代码里加上单点加就好，没什么其他注意的。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
struct tree{
int sum, lsum, rsum, msum;
} z[mn << 2];
inline void update(int rt){
z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;
z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1 | 1].lsum + z[rt << 1].sum);
z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1].rsum + z[rt << 1 | 1].sum);
z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = read();
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline void modify(int l,int r,int rt,int now,int v){
if(l==r && l==now){
z[rt].sum = z[rt].rsum = z[rt].msum = z[rt].lsum = v;
return;
}
int m = (l + r) >> 1;
//push_col(bson);
if(now<=m)
modify(lson, now, v);
else
modify(rson, now, v);
update(rt);
}
inline tree query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){
//cout << z[rt].msum << " ";
return z[rt];
}
int m = (l + r) >> 1;
//push_col(bson);
tree tl, tr, res;
if(nowl<=m){
if(m<nowr){
tl = query(lson, nowl, nowr);
tr = query(rson, nowl, nowr);
res.sum = tl.sum + tr.sum;
res.lsum = max(tl.lsum, tl.sum + tr.lsum);
res.rsum = max(tr.rsum, tr.sum + tl.rsum);
res.msum = max(max(tl.msum, tr.msum), tl.rsum + tr.lsum);
return res;
}else
return query(lson, nowl, nowr);
}else{
return query(rson, nowl, nowr);
}
}
int n, m;
int main(){
n = read();
build(root);
m = read();
go(i,1,m,1){
int s = read();
if(!s){
int x = read(), y = read();
modify(root, x, y);
}else{
int x = read(), y = read();
cout << query(root, x, y).msum << "\n";
}
}
return 0;
} GSS4
「题意」： \(n\) 个数，和在 \(10 ^ {18}\)
现在有「两种」操作
-
0 \(x\) \(y\) 把区间 \([x,y]\) 内的每个数开方，下取整
-
1 \(x\) \(y\) 询问区间 \([x,y]\) 的每个数的和
「格式」： 有多组数据，数据以EOF结束，对于每组数据，输出数据的序号，每组数据之后输出一个空行。
「注意」： 不保证给出的区间 \([x, y]\) 有 \(x <= y\) ，如果 \(x > y\) 请交换\(x\) ，\(y\) 。
思路
如果数据都在 10 ^ 18 那说明我们如果此次开方的话，肯定在很快的几次开方后变成了 1 ，所以，如果这个区间的数字开方开着开着都变成了 1， 那么就没必要在去开方了。经计算，每个数最多开 7 ~ 8 次（保守说的），所以我们直接暴力在线段树上修改最多会修改 8 * N * logN。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 100010
#define inf 1 << 30
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline ll read(){
ll f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
ll z[mn << 2];
inline void update(int rt){
z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt] = read();
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline void modify(int l,int r,int rt,int nowl,int nowr){
if(r-l+1 == z[rt])
return;
if(l==r){
z[rt] = sqrt(z[rt]);
return;
}
int m = (l + r) >> 1;
if(nowl<=m)
modify(lson, nowl, nowr);
if(m<nowr)
modify(rson, nowl, nowr);
update(rt);
}
inline ll query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){
return z[rt];
}
int m = (l + r) >> 1;
if(nowl<=m){
if(m<nowr)
return query(lson, nowl, nowr) + query(rson, nowl, nowr);
else
return query(lson, nowl, nowr);
}else{
return query(rson, nowl, nowr);
}
}
int n, m, tot;
int main(){
while (scanf("%d", &n) != EOF){
printf("Case #%d:\n", ++tot);
build(root);
m = read();
go(i, 1, m, 1){
int s = read(), x = read(), y = read();
if(x>y)
swap(x, y);
if(!s){
modify(root, x, y);
}else{
printf("%lld\n", query(root, x, y));
}
}
putchar('\n');
}
return 0;
} GSS5
给定一个序列。查询左端点在\([x_1, y_1]\)之间，且右端点在\([x_2, y_2]\)之间的最大子段和，数据保证\(x_1 <= x_2\), \(y_1 <= y_2\)，但是不保证端点所在的区间不重合
思路
我们考虑分类讨论。
首先是\(y_1 <= x_2\)的情况，这种情况说明，\([y_1, x_2]\)必定在答案的和之中，我们要求的就是\([x_1, y_1]\)的最大后缀和，加上\([x_2, y_2]\)的最大前缀和，加上\([y_1, x_2]\)的区间和。
然后就是一个比较麻烦的情况，\(y_1 > x_2\)。
这种情况可能有三种最佳答案。一种是以 \(y_1\) 为分界的最大后缀和（区间\([x_1, y_1]\)）与最大前缀和（\([y_1, y_2]\)），一种是以 \(x_2\) 为分界的最大后缀和（\([x_1, x_2]\)）与最大前缀和（\([x_2, y_2]\)），第三种就是所取答案都在 \([x_2, y_1]\) 中。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 50010
#define inf 1 << 30
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
struct tree{
int lsum, rsum, sum, msum;
} z[mn << 2];
int a[mn];
inline void update(int rt){
z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;
z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1].sum + z[rt << 1 | 1].lsum);
z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1 | 1].sum + z[rt << 1].rsum);
z[rt].msum = max(max(z[rt << 1].msum, z[rt << 1 | 1].msum), z[rt << 1].rsum + z[rt << 1 | 1].lsum);
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt].sum = z[rt].lsum = z[rt].rsum = z[rt].msum = a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline tree query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){return z[rt];}
int m = (l + r) >> 1;
bool fl = false, fr = false;
tree tl, tr, res;
if (nowl <= m){
if(m<nowr){
tl = query(lson, nowl, nowr);
tr = query(rson, nowl, nowr);
res.sum = tl.sum + tr.sum;
res.lsum = max(tl.lsum, tl.sum + tr.lsum);
res.rsum = max(tr.rsum, tr.sum + tl.rsum);
res.msum = max(max(tl.msum, tr.msum), tl.rsum + tr.lsum);
return res;
}else{
return query(lson, nowl, nowr);
}
}else{
return query(rson, nowl, nowr);
}
}
int n, m;
inline void solve() {
n = read();
go(i, 1, n, 1) a[i] = read();
build(root);
m = read();
go(i, 1, m, 1) {
int x = read(), y = read(), xx = read(), yy = read();
if(y < xx) {
int ans = 0;
ans += query(root, x, y).rsum;
if(y + 1 <= xx - 1)
ans += query(root, y + 1, xx - 1).sum;
ans += query(root, xx, yy).lsum;
printf("%d\n", ans);
} else {
int ans = 0;
ans = query(root, xx, y).msum;
if(x < xx) ans = max(ans, query(root, x, xx).rsum + query(root, xx, yy).lsum - a[xx]);
if(y < yy) ans = max(ans, query(root, x, y).rsum + query(root, y, yy).lsum - a[y]);
printf("%d\n", ans);
}
}
}
inline void init() {
memset(z, 0, sizeof z);
}
int main(){
int T = read();
while(T--) {
init();
solve();
}
return 0;
} GSS6
给出一个由 \(N\) 个整数组成的序列 \(A\)，你需要应用 \(M\) 个操作：
- \(I\) \(p\) \(x\) 在 \(p\) 处插入插入一个元素 \(x\)
- \(D\) \(p\) 删除 \(p\) 处的一个元素
- \(R\) \(p\) \(x\) 修改 \(p\) 处元素的值为 \(x\)
- \(Q\) \(l\) \(r\) 查询一个区间 \([l, r]\) 的最大子段和
思路
平衡树呗，记得push up一下刚更新的节点就好啦。
此处给出两个版本：
-
Splay版
-
FHQ Treap版
请自行选择食用QwQ
code1: (Splay)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 200010
#define inf 2147483647
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0') {if (ch == '-') f = -f; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
inline void write(int x){
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
vector<int> ljt;
struct tree{
int ch[2], sze, fa;
ll w, sum, lsum, rsum, msum;
tree(int s, int f, int v, int su, int l, int r, int m)
: sze(s), fa(f), w(v), sum(su), lsum(l), rsum(r), msum(m) { ch[0] = ch[1] = 0; }
tree() : tree(0, 0, 0, 0, 0, 0, 0) {}
};
int n, m, tot, a[mn];
tree z[mn];
inline int newnode(int v = 0){
int rt;
if (ljt.empty())
rt = ++tot;
else
rt = ljt.back(), ljt.pop_back();
z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = 0;
z[rt].sze = 1;
z[rt].w = z[rt].sum = v;
z[rt].lsum = z[rt].rsum = z[rt].msum = max(v, 0);
return rt;
}
inline void deletenode(int rt){
z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = z[rt].w = z[rt].sum = z[rt].msum = z[rt].lsum = z[rt].rsum = 0;
z[rt].sze = 1;
ljt.push_back(rt);
}
inline void update(int rt)
{
z[rt].sum = z[rt].w, z[rt].sze = 1;
if (z[rt].ch[0])
z[rt].sum += z[z[rt].ch[0]].sum, z[rt].sze += z[z[rt].ch[0]].sze;
if (z[rt].ch[1])
z[rt].sum += z[z[rt].ch[1]].sum, z[rt].sze += z[z[rt].ch[1]].sze;
if (z[rt].ch[0] && z[rt].ch[1]) {
z[rt].lsum = max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].w + z[z[rt].ch[1]].lsum);
z[rt].rsum = max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].w + z[z[rt].ch[0]].rsum);
z[rt].msum = max({z[z[rt].ch[0]].msum, z[z[rt].ch[1]].msum, z[z[rt].ch[0]].rsum + z[z[rt].ch[1]].lsum + z[rt].w});
} else if (z[rt].ch[0]) {
z[rt].lsum = max({z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].w, 0ll});
z[rt].rsum = max(z[z[rt].ch[0]].rsum + z[rt].w, 0ll);
z[rt].msum = max(z[z[rt].ch[0]].msum, z[z[rt].ch[0]].rsum + z[rt].w);
} else if (z[rt].ch[1]) {
z[rt].lsum = max(z[z[rt].ch[1]].lsum + z[rt].w, 0ll);
z[rt].rsum = max({z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].w, 0ll});
z[rt].msum = max(z[z[rt].ch[1]].msum, z[z[rt].ch[1]].lsum + z[rt].w);
} else {
z[rt].lsum = z[rt].rsum = max(z[rt].w, 0ll);
z[rt].msum = z[rt].w;
}
}
inline int iden(int rt) {
return z[z[rt].fa].ch[0] == rt ? 0 : 1;
}
inline void connect(int x, int y, int son) {
z[x].fa = y;
z[y].ch[son] = x;
}
inline void rotate(int x) {
int y = z[x].fa;
int moot = z[y].fa;
int yson = iden(x);
int mootson = iden(y);
int B = z[x].ch[yson ^ 1];
connect(B, y, yson), connect(y, x, yson ^ 1), connect(x, moot, mootson);
update(y), update(x);
}
inline void splay(int x, int &k) {
if (x == k)
return;
int p = z[k].fa;
while (z[x].fa != p) {
int y = z[x].fa;
if (z[y].fa != p)
rotate(iden(y) ^ iden(x) ? x : y);
rotate(x);
}
k = x;
}
inline int findkth(int rt, int k) {
while (1119) {
if (z[rt].ch[0] && k <= z[z[rt].ch[0]].sze)
rt = z[rt].ch[0];
else {
if (z[rt].ch[0])
k -= z[z[rt].ch[0]].sze;
if (!--k)
return rt;
rt = z[rt].ch[1];
}
}
}
inline void insert(int &rt, int p, int v) {
int x = findkth(rt, p);
splay(x, rt);
int y = findkth(rt, p + 1);
int ooo = z[rt].ch[1];
splay(y, ooo);
z[y].ch[0] = newnode(v);
z[z[y].ch[0]].fa = y;
update(z[y].ch[0]), update(y), update(x);
}
inline void erase(int &rt, int p) {
int y = findkth(rt, p);
splay(y, rt);
int x = findkth(rt, p + 1);
int ooo = z[rt].ch[1];
splay(x, ooo);
int oo = z[x].ch[1];
z[oo].fa = y;
z[y].ch[1] = oo;
deletenode(x);
update(y);
}
inline int getRange(int &rt, int l, int r) {
int x = findkth(rt, l);
splay(x, rt);
int y = findkth(rt, r + 2);
int ooo = z[rt].ch[1];
splay(y, ooo);
return z[y].ch[0];
}
inline void modify(int &rt, int p, ll v) {
int x = findkth(rt, p + 1);
splay(x, rt);
z[x].w = v;
update(x);
}
inline ll query(int &rt, int l, int r) {
int x = getRange(rt, l, r);
return z[x].msum;
}
inline void build(int rt, int l, int r) {
int m = (l + r) >> 1;
z[rt].w = a[m];
if (l <= m - 1) {
z[rt].ch[0] = newnode();
z[z[rt].ch[0]].fa = rt;
build(z[rt].ch[0], l, m - 1);
}
if (m + 1 <= r) {
z[rt].ch[1] = newnode();
z[z[rt].ch[1]].fa = rt;
build(z[rt].ch[1], m + 1, r);
}
update(rt);
}
int main()
{
n = read();
go(i, 1, n, 1) a[i] = read();
int rot = ++tot;
build(rot, 0, n + 1);
m = read();
go(i, 1, m, 1)
{
char s;
cin >> s;
if (s == 'I') {
int p = read(), v = read();
insert(rot, p, v);
} else if (s == 'D') {
int p = read();
erase(rot, p);
} else if (s == 'R') {
int p = read(), x = read();
modify(rot, p, x);
} else {
int x = read(), y = read();
printf("%lld\n", query(rot, x, y));
}
}
return 0;
} code2: (FHQ Treap)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
#define go(i, j, n, k) for(int i = j; i <= n; i += k)
#define fo(i, j, n, k) for(int i = j; i >= n; i -= k)
#define mn 400010
#define inf 1 << 30
#define ll long long
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -f; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct tree{
int pri, ch[2], sze;
ll x, sum, lsum, rsum, msum;
} z[mn];
inline void update(int rt)
{
z[rt].sum = z[rt].x, z[rt].sze = 1;
if (z[rt].ch[0])
z[rt].sum += z[z[rt].ch[0]].sum, z[rt].sze += z[z[rt].ch[0]].sze;
if (z[rt].ch[1])
z[rt].sum += z[z[rt].ch[1]].sum, z[rt].sze += z[z[rt].ch[1]].sze;
if (z[rt].ch[0] && z[rt].ch[1]) {
z[rt].lsum = max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x + z[z[rt].ch[1]].lsum);
z[rt].rsum = max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x + z[z[rt].ch[0]].rsum);
z[rt].msum = max(max(z[z[rt].ch[0]].msum, z[z[rt].ch[1]].msum), z[z[rt].ch[0]].rsum + z[z[rt].ch[1]].lsum + z[rt].x);
} else if (z[rt].ch[0]) {
z[rt].lsum = max(max(z[z[rt].ch[0]].lsum, z[z[rt].ch[0]].sum + z[rt].x), 0ll);
z[rt].rsum = max(z[z[rt].ch[0]].rsum + z[rt].x, 0ll);
z[rt].msum = max(z[z[rt].ch[0]].msum, z[z[rt].ch[0]].rsum + z[rt].x);
} else if (z[rt].ch[1]) {
z[rt].lsum = max(z[z[rt].ch[1]].lsum + z[rt].x, 0ll);
z[rt].rsum = max(max(z[z[rt].ch[1]].rsum, z[z[rt].ch[1]].sum + z[rt].x), 0ll);
z[rt].msum = max(z[z[rt].ch[1]].msum, z[z[rt].ch[1]].lsum + z[rt].x);
} else {
z[rt].lsum = z[rt].rsum = max(z[rt].x, 0ll);
z[rt].msum = z[rt].x;
}
}
int cnt;
inline int newnode(int v = 0) {
z[++cnt].x = z[cnt].msum = z[cnt].sum = v;
z[cnt].lsum = z[cnt].rsum = max(v, 0);
z[cnt].sze = 1;
z[cnt].pri = rand();
return cnt;
}
inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(z[x].pri < z[y].pri) {
z[x].ch[1] = merge(z[x].ch[1], y);
update(x);
return x;
} else {
z[y].ch[0] = merge(x, z[y].ch[0]);
update(y);
return y;
}
}
inline void split(int rt, int k, int &x, int &y) {
if(!rt) x = y = 0;
else {
if(k <= z[z[rt].ch[0]].sze) {
y = rt, split(z[rt].ch[0], k, x, z[rt].ch[0]);
} else {
x = rt, split(z[rt].ch[1], k - z[z[rt].ch[0]].sze - 1, z[rt].ch[1], y);
}
update(rt);
}
}
int n, m, xx, yy, zz, rot;
inline void debug() {
go(rt, 1, cnt, 1) {
printf("%d: pri:%d, sze:%d, ch[0]:%d, ch[1]:%d, x:%d\n", rt, z[rt].pri, z[rt].sze, z[rt].ch[0], z[rt].ch[1], z[rt].x);
}
printf("\n");
}
int main() {
srand((unsigned)time(NULL));
n = read();
go(i, 1, n, 1) {
int x = read();
split(rot, i, xx, yy);
rot = merge(merge(xx, newnode(x)), yy);
}
m = read();
go(i, 1, m, 1) {
char s;
cin >> s;
int x = read(), v;
if(s == 'I') {
v = read();
split(rot, x - 1, xx, yy);
rot = merge(merge(xx, newnode(v)), yy);
} else if(s == 'D') {
split(rot, x, xx, zz);
split(xx, x - 1, xx, yy);
yy = merge(z[yy].ch[0], z[yy].ch[1]);
rot = merge(merge(xx, yy), zz);
} else if(s == 'R') {
v = read();
split(rot, x, xx, zz);
split(xx, x - 1, xx, yy);
z[yy].x = v;
z[yy].sum = z[yy].msum = v;
z[yy].lsum = z[yy].rsum = max(v, 0);
rot = merge(merge(xx, yy), zz);
} else if(s == 'Q') {
v = read();
split(rot, v, xx, zz);
split(xx, x - 1, xx, yy);
printf("%lld\n", z[yy].msum);
rot = merge(merge(xx, yy), zz);
}
// debug();
}
return 0;
} GSS7
给定一棵树，有$ N (N ≤ 100000) $个节点，每一个节点都有一个权值 \(x[i] (<= 10000)\)
你需要执行 \(Q (Q ≤ 100000)\) 次操作：
- \(1\) \(a\) \(b\) 查询 \((a,b)\) 这条链上的最大子段和，可以为空（即输出\(0\)）
- \(2\) \(a\) \(b\) \(c\) 将 \((a,b)\) 这条链上的所有点权变为 \(c (|c| <= 10000)\)
思路
树链剖分套线段树维护区间最大子段和，基本没啥思路，直接套。不过代码细节较多。代码过长，引起极度不适。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 100020
#define inf 2147483647
#define ll long long
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define bson l, r, rt
inline int read(){
int f = 1, x = 0;char ch = getchar();
while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
inline void write(int x){
if (x < 0)putchar('-'),x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
int n, m, r;
struct tree{
int sum, lsum, rsum, msum;
tree() { sum = lsum = rsum = msum = 0; }
};
int dep[mn], sze[mn], son[mn], fa[mn], id[mn], top[mn], b[mn];
int cnt;
// Array -------------------------------------------------------------------
struct SegmentTree{
tree z[mn << 2];
int col[mn << 2];
int cd[mn << 2];
inline void update(int rt){
z[rt].sum = z[rt << 1].sum + z[rt << 1 | 1].sum;
z[rt].lsum = max(z[rt << 1].lsum, z[rt << 1 | 1].lsum + z[rt << 1].sum);
z[rt].rsum = max(z[rt << 1 | 1].rsum, z[rt << 1].rsum + z[rt << 1 | 1].sum);
z[rt].msum = max({z[rt << 1].msum, z[rt << 1 | 1].msum, z[rt << 1].rsum + z[rt << 1 | 1].lsum});
}
inline tree operation(tree a,tree b){
tree res;
res.sum = a.sum + b.sum;
res.lsum = max(a.lsum, a.sum + b.lsum);
res.rsum = max(b.rsum, b.sum + a.rsum);
res.msum = max({a.msum, b.msum, a.rsum + b.lsum});
return res;
}
inline void push_col(int l,int r,int rt){
if(cd[rt]) {
int m = (l + r) >> 1;
cd[rt << 1] = cd[rt << 1 | 1] = 1;
col[rt << 1] = col[rt << 1 | 1] = col[rt];
z[rt << 1].sum = (m - l + 1) * col[rt];
z[rt << 1 | 1].sum = (r - m) * col[rt];
z[rt << 1].lsum = z[rt << 1].rsum = z[rt << 1].msum = max(z[rt << 1].sum, 0);
z[rt << 1 | 1].lsum = z[rt << 1 | 1].rsum = z[rt << 1 | 1].msum = max(z[rt << 1 | 1].sum, 0);
cd[rt] = 0;
}
}
inline void build(int l,int r,int rt){
if(l==r){
z[rt].sum = b[l];
z[rt].lsum = z[rt].rsum = z[rt].msum = max(z[rt].sum, 0);
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
inline void modify(int l,int r,int rt,int nowl,int nowr,int v){
if(nowl<=l && r<=nowr){
col[rt] = v;
cd[rt] = 1;
z[rt].sum = (r - l + 1) * v;
z[rt].lsum = z[rt].rsum = z[rt].msum = max(z[rt].sum, 0);
return;
}
int m = (l + r) >> 1;
push_col(bson);
if(nowl<=m)
modify(lson, nowl, nowr, v);
if(m<nowr)
modify(rson, nowl, nowr, v);
update(rt);
}
inline tree query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l && r<=nowr){
return z[rt];
}
int m = (l + r) >> 1;
push_col(bson);
if(nowl<=m){
if(m<nowr)
return operation(query(lson, nowl, nowr), query(rson, nowl, nowr));
else
return query(lson, nowl, nowr);
}else{
return query(rson, nowl, nowr);
}
}
} tr;
// Line Segment Tree ------------------------------------------------
struct edge{
int v, nxt;
} e[mn << 1];
int h[mn], w[mn], p;
inline void add(int a,int b){
e[++p].nxt = h[a];
h[a] = p;
e[p].v = b;
}
// Adjacency List ---------------------------------------------------------------
void dfs1(int x,int f,int deep){
dep[x] = deep;
sze[x] = 1;
fa[x] = f;
int maxson = -1;
rep(i,x){
int v = e[i].v;
if(v == f)
continue;
dfs1(v, x, deep + 1);
sze[x] += sze[v];
if (maxson < sze[v])
maxson = sze[v], son[x] = v;
}
}
void dfs2(int x,int topf){
id[x] = ++cnt;
b[id[x]] = w[x];
top[x] = topf;
if(!son[x])
return;
dfs2(son[x], topf);
rep(i,x){
int v = e[i].v;
if(v==fa[x] || v==son[x])
continue;
dfs2(v, v);
}
}
// DFS ----------------------------------------------------------------
/*
inline void modifyTree(int x,int y,int v){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])
swap(x, y);
tr.modify(root, id[top[x]], id[x], v);
x = fa[top[x]];
}
if(dep[x] > dep[y])
swap(x, y);
tr.modify(root, id[x], id[y], v);
}
*/
inline void modifyTree(int x,int y,int v){
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]){
tr.modify(root, id[top[x]], id[x], v);
x = fa[top[x]];
}else{
tr.modify(root, id[top[y]], id[y], v);
y = fa[top[y]];
}
}
if(dep[x] > dep[y])
tr.modify(root, id[y], id[x], v);
else
tr.modify(root, id[x], id[y], v);
}
inline tree queryTree(int x,int y){
tree lt, rt;
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]){
tree get = tr.query(root, id[top[x]], id[x]);
lt.msum = max({lt.msum, get.msum, lt.lsum + get.rsum});
lt.lsum = max(lt.lsum + get.sum, get.lsum);
lt.rsum = max(lt.rsum, get.rsum + lt.sum);
lt.sum += get.sum;
x = fa[top[x]];
}else{
tree get = tr.query(root, id[top[y]], id[y]);
rt.msum = max({rt.msum, get.msum, rt.lsum + get.rsum});
rt.lsum = max(rt.lsum + get.sum, get.lsum);
rt.rsum = max(rt.rsum, rt.sum + get.rsum);
rt.sum += get.sum;
y = fa[top[y]];
}
//cout << "lalala\n";
}
//printf("%d %d %d %d\n%d %d %d %d\n", lt.lsum, lt.rsum, lt.sum, lt.msum, rt.lsum, rt.rsum, rt.sum, rt.msum);
if(dep[x] < dep[y]){
tree get = tr.query(root, id[x], id[y]);
rt.msum = max({rt.msum, get.msum, rt.lsum + get.rsum});
rt.lsum = max(get.lsum, get.sum + rt.lsum);
rt.rsum = max(rt.rsum, rt.sum + get.rsum);
rt.sum += get.sum;
}else{
tree get = tr.query(root, id[y], id[x]);
lt.msum = max({lt.msum, get.msum, lt.lsum + get.rsum});
lt.lsum = max(get.lsum, get.sum + lt.lsum);
lt.rsum = max(lt.rsum, lt.sum + get.rsum);
lt.sum += get.sum;
}
//cout << "lalala\n";
tree res;
res.sum = lt.sum + rt.sum;
res.lsum = max(lt.lsum, lt.sum + rt.rsum);
res.rsum = max(rt.lsum, rt.sum + lt.rsum);
res.msum = max({lt.msum, rt.msum, lt.lsum + rt.lsum});
return res;
}
// Modify and Query ------------------------------------------------------
int main()
{
n = read();
r = 1;
go(i, 1, n, 1) w[i] = read();
go(i, 1, n - 1, 1){
int x = read(), y = read();
add(x, y), add(y, x);
}
dfs1(r, 0, 1);
dfs2(r, r);
tr.build(root);
m = read();
go(i, 1, m, 1){
int s = read(), x = read(), y = read();
if(s==2){
int v = read();
modifyTree(x, y, v);
}else{
cout << queryTree(x, y).msum << "\n";
//cout << "lalala\n";
}
}
return 0;
} GSS8
给你一个序列，\(A[0], A[1]...A[N - 1].\) \((0 \le A[i] \lt 2^{32})\)
你需要支持 Q 次操作
- \(I\) \(pos\) \(val\) 插入一个数字在第 \(pos\) 个位置之前，\(0 \le val \lt 2^{32}\)
, 如果\(pos=current\) \(length\)，那么你需要将这个数字放到序列末尾 - D pos 删除第 \(pos\) 个元素
- R pos val 将第 \(pos\) 个元素变为\(val(0 \le val \lt 2^{32})\)
- Q l r k 询问\((\sum\limits_{i=l}^{r} A[i] * (i - l + 1) ^ k) \mod 2^{32}\)，保证\(0 \le k \le 10\)
思路
对于每一个 k 都维护一个答案。
如果 k = 0, 就是区间和，如果 k = 1，我们可以用这样的式子写：
z[rt].ans[1] = z[z[rt].ch[0]].ans[1] + z[z[rt].ch[1]].ans[1] + (z[z[rt].ch[1]].sum * z[z[rt].ch[0]].sze)
但如果我们考虑 k > 1，我们仍考虑左右合并，但不是左边不动的，我们把表达式化简一下。（以下计算过程参考 hzk_cpp 巨佬的 计算过程）
\(A[i](i - l + 1)^k\)
= \(A[i]((mid - l + 1) + (i - mid))^k\)
另 \(x = i - l + 1\)，实际就是左区间的长度，设 $ rs.ans[j] $ 作为 \([min + 1, r]\) 时 \(k = j\) 的答案。
= \(A[i](x + i - mid)^k\)
由二项式定理得
= \(A[i]\sum_{j=0}^kC_k^jx^{k-j}(i - mid)^j\)
我们右边所有的值加起来，得：
= \(\sum_{i=mid+1}^rA[i]\sum_{j=0}^kC_k^jx^{k-j}(i - mid)^j\)
= \(\sum_{i=mid+1}^r\sum_{j=0}^kA[i]C_k^jx^{k-j}(i - mid)^j\)
= \(\sum_{j=0}^kC_k^jx^{k-j}rs.ans[j]\)
这个式子直接可以暴力在update函数中直接更新，毕竟 \(k <= 10\)，不伤身体。
目前只有Splay版，FHQ Treap版正在调。
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <iostream>
using namespace std;
#define go(i, j, n, k) for (int i = j; i <= n; i += k)
#define fo(i, j, n, k) for (int i = j; i >= n; i -= k)
#define mn 200010
#define inf 2147483647
#define ll unsigned int
inline ll read(){
ll x = 0; char ch = getchar();
while (ch > '9' || ch < '0') { ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x;
}
inline void write(int x){
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
//This is AC head above...
vector<int> ljt;
struct tree{
int ch[2], sze, fa;
ll w, ans[11];
tree(int s, int f, int v)
: sze(s), fa(f), w(v) { ch[0] = ch[1] = 0;
go(i, 0, 10, 1) ans[i] = 0; }
tree() : tree(0, 0, 0) {}
};
int n, m, tot;
ll a[mn];
tree z[mn];
ll po[mn], C[11][11];
inline int newnode(int v = 0){
int rt;
if (ljt.empty())
rt = ++tot;
else
rt = ljt.back(), ljt.pop_back();
z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = 0;
z[rt].sze = 1;
z[rt].w = v;
return rt;
}
inline void deletenode(int rt){
z[rt].fa = z[rt].ch[0] = z[rt].ch[1] = z[rt].w = 0;
go(i, 0, 10, 1) z[rt].ans[i] = 0;
z[rt].sze = 1;
ljt.push_back(rt);
}
inline void update(int rt) {
z[rt].sze = 1;
if(z[rt].ch[0]) z[rt].sze += z[z[rt].ch[0]].sze;
if(z[rt].ch[1]) z[rt].sze += z[z[rt].ch[1]].sze;
po[0] = 1ll;
go(i, 1, 10, 1)
po[i] = po[i - 1] * (z[z[rt].ch[0]].sze + 1);
go(i, 0, 10, 1) {
z[rt].ans[i] = z[z[rt].ch[0]].ans[i] + z[rt].w * po[i];
go(j, 0, i, 1)
z[rt].ans[i] = z[rt].ans[i] + z[z[rt].ch[1]].ans[j] * po[i - j] * C[i][j];
}
}
inline int iden(int rt) {
return z[z[rt].fa].ch[0] == rt ? 0 : 1;
}
inline void connect(int x, int y, int son) {
z[x].fa = y;
z[y].ch[son] = x;
}
inline void rotate(int x) {
int y = z[x].fa;
int moot = z[y].fa;
int yson = iden(x);
int mootson = iden(y);
int B = z[x].ch[yson ^ 1];
connect(B, y, yson), connect(y, x, yson ^ 1), connect(x, moot, mootson);
update(y), update(x);
}
inline void splay(int x, int &k) {
if (x == k)
return;
int p = z[k].fa;
while (z[x].fa != p) {
int y = z[x].fa;
if (z[y].fa != p)
rotate(iden(y) ^ iden(x) ? x : y);
rotate(x);
}
k = x;
}
inline int findkth(int rt, int k) {
while (1119) {
if (z[rt].ch[0] && k <= z[z[rt].ch[0]].sze)
rt = z[rt].ch[0];
else {
if (z[rt].ch[0])
k -= z[z[rt].ch[0]].sze;
if (!--k)
return rt;
rt = z[rt].ch[1];
}
}
}
inline void insert(int &rt, int p, int v) {
int x = findkth(rt, p);
splay(x, rt);
int y = findkth(rt, p + 1);
int ooo = z[rt].ch[1];
splay(y, ooo);
z[y].ch[0] = newnode(v);
z[z[y].ch[0]].fa = y;
update(z[y].ch[0]), update(y), update(x);
}
inline void erase(int &rt, int p) {
int y = findkth(rt, p);
splay(y, rt);
int x = findkth(rt, p + 1);
int ooo = z[rt].ch[1];
splay(x, ooo);
int oo = z[x].ch[1];
z[oo].fa = y;
z[y].ch[1] = oo;
deletenode(x);
update(y);
}
inline int getRange(int &rt, int l, int r) {
int x = findkth(rt, l);
splay(x, rt);
int y = findkth(rt, r + 2);
int ooo = z[rt].ch[1];
splay(y, ooo);
return z[y].ch[0];
}
inline void modify(int &rt, int p, ll v) {
int x = findkth(rt, p + 1);
splay(x, rt);
z[x].w = v;
update(x);
}
inline ll query(int &rt, int l, int r, int k) {
int x = getRange(rt, l, r);
return z[x].ans[k];
}
inline void build(int rt, int l, int r) {
int m = (l + r) >> 1;
z[rt].w = a[m];
if (l <= m - 1) {
z[rt].ch[0] = newnode();
z[z[rt].ch[0]].fa = rt;
build(z[rt].ch[0], l, m - 1);
}
if (m + 1 <= r) {
z[rt].ch[1] = newnode();
z[z[rt].ch[1]].fa = rt;
build(z[rt].ch[1], m + 1, r);
}
update(rt);
}
inline void init()
{
go(i, 0, 10, 1) C[i][0] = C[i][i] = 1;
go(i, 1, 10, 1)
go(j, 1, i, 1)
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
// go(i, 0, 10, 1)
// go(j, 0, 10, 1)
// printf("%5d%c", C[i][j], (j == 10) ? '\n' : ' ');
}
int main()
{
init();
n = read();
go(i, 1, n, 1) a[i] = read();
int rot = ++tot;
build(rot, 0, n + 1);
m = read();
go(i, 1, m, 1)
{
char s;
cin >> s;
if (s == 'I') {
int p = read() + 1, v = read();
insert(rot, p, v);
} else if (s == 'D') {
int p = read() + 1;
erase(rot, p);
} else if (s == 'R') {
int p = read() + 1, x = read();
modify(rot, p, x);
} else {
int x = read() + 1, y = read() + 1, z = read();
printf("%lld\n", query(rot, x, y, z));
}
}
return 0;
} 
京公网安备 11010502036488号