GSS1
线段树最大子段和裸题，不带修改，注意pushup。
然而并不会猫树之类的东西
#include<bits/stdc++.h>
#define MAXN 50001
using namespace std;
struct node{
int l , r , sum , lMax , rMax , midMax;
}Tree[MAXN << ];
int a[MAXN] , rMax , allMax , N;
inline int max(int a , int b){
return a > b ? a : b;
}
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
if(l == r)
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = Tree[dir].sum = a[l];
else{
init(dir << , l , (l + r) >> );
init(dir << | , ((l + r) >> ) + , r);
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].lMax = max(Tree[dir << ].lMax , Tree[dir << ].sum + Tree[dir << | ].lMax);
Tree[dir].rMax = max(Tree[dir << | ].rMax , Tree[dir << | ].sum + Tree[dir << ].rMax);
Tree[dir].midMax = max(max(Tree[dir << ].midMax , Tree[dir << | ].midMax) , Tree[dir << ].rMax + Tree[dir << | ].lMax);
}
}
void findMax(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , max(rMax + Tree[dir].lMax , Tree[dir].midMax));
rMax = max(max(Tree[dir].rMax , Tree[dir].sum + rMax) , );
return;
}
)
findMax(dir << , l , r);
)
findMax(dir << | , l , r);
}
inline void work(int x , int y){
allMax = -0x7fffffff;
rMax = ;
findMax( , x , y);
printf("%d\n" , allMax);
}
int main(){
scanf("%d" , &N);
; i <= N ; i++)
scanf("%d" , a + i);
init( , , N);
int T;
for(scanf("%d" , &T) ; T ; T--){
int a , b;
scanf("%d%d" , &a , &b);
work(a , b);
}
;
}
GSS1
GSS2
因为不是传统的最大子段和所以单独开了一页：Sol
GSS3
带修改的GSS1
其实也没什么区别只是莫名代码长了很多
#include<bits/stdc++.h>
#define MAXN 50001
#define ll long long
using namespace std;
inline ll read(){
ll a = ;
char c = getchar();
;
while(!isdigit(c)){
;
c = getchar();
}
) + (a << ) + (c ^ ') , c = getchar();
return f ? -a : a;
}
inline void print(ll x){
] , dirN = ;
){
putchar('-');
x = -x;
}
while(x){
num[dirN++] = x % ;
x /= ;
}
) putchar(');
);
putchar('\n');
}
struct node{
ll l , r , lMax , rMax , sum , midMax;
}Tree[MAXN << ];
ll num[MAXN] , N , nowMaxLeft , nowMax;
inline ll max(ll a , ll b){return a > b ? a : b;}
void build(ll dir , ll l , ll r){
Tree[dir].l = l; Tree[dir].r = r;
if(l == r)
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = Tree[dir].sum = num[l];
else{
build(dir << , l , l + r >> );
build(dir << | , (l + r >> ) + , r);
Tree[dir].lMax = max(Tree[dir << ].sum + Tree[dir << | ].lMax , Tree[dir << ].lMax);
Tree[dir].rMax = max(Tree[dir << | ].sum + Tree[dir << ].rMax , Tree[dir << | ].rMax);
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].midMax = max(Tree[dir << | ].lMax + Tree[dir << ].rMax , max(Tree[dir << ].midMax , Tree[dir << | ].midMax));
}
}
void change(ll dir , ll a , ll b){
if(Tree[dir].l == a && Tree[dir].r == a){
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = Tree[dir].sum = b;
return;
}
) change(dir << | , a , b);
, a , b);
Tree[dir].lMax = max(Tree[dir << ].sum + Tree[dir << | ].lMax , Tree[dir << ].lMax);
Tree[dir].rMax = max(Tree[dir << | ].sum + Tree[dir << ].rMax , Tree[dir << | ].rMax);
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].midMax = max(Tree[dir << | ].lMax + Tree[dir << ].rMax , max(Tree[dir << ].midMax , Tree[dir << | ].midMax));
}
void findMax(ll dir , ll a , ll b){
if(Tree[dir].l >= a && Tree[dir].r <= b){
nowMax = max(nowMax , max(max(nowMaxLeft , ) + Tree[dir].lMax , Tree[dir].midMax));
nowMaxLeft = max(nowMaxLeft + Tree[dir].sum , Tree[dir].rMax);
return;
}
) findMax(dir << , a , b);
) findMax(dir << | , a , b);
}
int main(){
N = read();
; i <= N ; i++) num[i] = read();
build( , , N);
register int a , b , M = read();
while(M--)
){
a = read(); b = read();
nowMaxLeft = nowMax = -0x7f7f7f7f;
findMax( , a , b);
print(max(nowMax , nowMaxLeft));
}
else{
a = read(); b = read();
change( , a , b);
}
;
}
GSS3
GSS4
话说这东西似乎叫做势能线段树？
$10^{18}$开$6-7$次根就会变成$1$，而$\sqrt{1} = 1$，所以我们可以建一棵这样子的线段树：最开始几次修改暴力到叶子节点进行修改，在之后的某一次修改中，如果某一个节点所表示的区间中所有数就变成了$1$，就不往下走
#include<bits/stdc++.h>
#define MAXN 100010
#define int unsigned long long
using namespace std;
inline int read(){
;
char c = getchar();
while(c != EOF && !isdigit(c))
c = getchar();
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return a;
}
struct node{
int sum;
bool f;
}Tree[MAXN << ];
inline void pushup(int now){
Tree[now].sum = Tree[now << ].sum + Tree[now << | ].sum;
Tree[now].f = Tree[now << ].f && Tree[now << | ].f;
}
void init(int now , int l , int r){
if(l == r){
Tree[now].sum = read();
Tree[now].f = Tree[now].sum == ;
return;
}
init(now << , l , l + r >> );
init(now << | , (l + r >> ) + , r);
pushup(now);
}
void change(int now , int l , int r , int L , int R){
if(Tree[now].f)
return;
if(l == r){
Tree[now].sum = sqrt(Tree[now].sum);
Tree[now].f = Tree[now].sum == ;
return;
}
>= L)
change(now << , l , l + r >> , L , R);
< R)
change(now << | , (l + r >> ) + , r , L , R);
pushup(now);
}
int getAns(int now , int l , int r , int L , int R){
if(l >= L && r <= R)
return Tree[now].sum;
;
>= L)
sum += getAns(now << , l , l + r >> , L , R);
< R)
sum += getAns(now << | , (l + r >> ) + , r , L , R);
return sum;
}
main()
{
ios::sync_with_stdio();
cin.tie();
cout.tie();
;
while((N = read()) && N){
init( , , N);
cout << "Case #" << ++c << ":" << endl;
for(int M = read() ; M ; M--)
){
int a = read() , b = read();
if(a > b)
swap(a , b);
change( , , N , a , b);
}
else{
int a = read() , b = read();
if(a > b)
swap(a , b);
cout << getAns( , , N , a , b) << endl;
}
cout << endl;
}
;
}
GSS4
GSS5
设左区间为$[a,b]$，右区间为$[c,d]$，满足$b \geq c$
分类讨论：
①左端点在$[a,c)$，答案为$[a,c)$的最大后缀与$[c,d]$的最大前缀
②右端点在$(b,d]$，答案为$[a,b]$的最大后缀与$(b,d]$的最大前缀
③左右端点都在$[b,c]$，答案为$[b,c]$的最大子段和
#include<bits/stdc++.h>
#define MAXN 10001
using namespace std;
inline int max(int a , int b){
return a > b ? a : b;
}
inline int min(int a , int b){
return a < b ? a : b;
}
struct node{
int l , r , lMax , rMax , midMax , sum;
}Tree[MAXN << ];
int a[MAXN] , N , lMax , rMax , allMax;
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
if(l == r)
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = Tree[dir].sum = a[l];
else{
init(dir << , l , (l + r) >> );
init(dir << | , ((l + r) >> ) + , r);
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].lMax = max(Tree[dir << ].lMax , Tree[dir << ].sum + Tree[dir << | ].lMax);
Tree[dir].rMax = max(Tree[dir << | ].rMax , Tree[dir << ].rMax + Tree[dir << | ].sum);
Tree[dir].midMax = max(Tree[dir << ].rMax + Tree[dir << | ].lMax , max(Tree[dir << ].midMax , Tree[dir << | ].midMax));
}
}
int findSum(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r)
return Tree[dir].sum;
;
)
sum += findSum(dir << , l , r);
)
sum += findSum(dir << | , l , r);
return sum;
}
void findRightMax(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , Tree[dir].rMax + rMax);
rMax += Tree[dir].sum;
return;
}
)
findRightMax(dir << | , l , r);
)
findRightMax(dir << , l , r);
}
void findLeftMax(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , Tree[dir].lMax + lMax);
lMax += Tree[dir].sum;
return;
}
)
findLeftMax(dir << , l , r);
)
findLeftMax(dir << | , l , r);
}
void findMax(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , max(Tree[dir].lMax + rMax , Tree[dir].midMax));
rMax = max( , max(Tree[dir].sum + rMax , Tree[dir].rMax));
return;
}
)
findMax(dir << , l , r);
)
findMax(dir << | , l , r);
}
inline int getAns(int a , int b , int c , int d){
;
< c)
t += findSum( , b + , c - );
if(a <= b){
allMax = -0x7fffffff;
rMax = ;
findRightMax( , a , b);
t += allMax;
}
if(c <= d){
allMax = -0x7fffffff;
lMax = ;
findLeftMax( , c , d);
t += allMax;
}
return t;
}
inline int work(int a , int b , int c , int d){
c = max(a , c);
b = min(b , d);
if(b < c)
return getAns(a , b , c , d);
else{
allMax = -0x7fffffff;
rMax = ;
findMax( , c , b);
int t = allMax;
, c , d) , getAns(c , b , b + , d)) , t);
}
}
int main(){
int T;
for(cin >> T ; T ; T--){
cin >> N;
; i <= N ; i++)
cin >> a[i];
init( , , N);
int M;
for(cin >> M ; M ; M--){
int a , b , c , d;
cin >> a >> b >> c >> d;
printf("%d\n" , work(a , b , c , d));
}
}
;
}
GSS5
GSS6
维护数列削弱版本
因为$remove$的一个智障失误调了$3h$
#include<bits/stdc++.h>
#define root Tree[0].ch[0]
#define lch Tree[x].ch[0]
#define rch Tree[x].ch[1]
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
inline int max(int a , int b){
return a > b ? a : b;
}
inline int min(int a , int b){
return a < b ? a : b;
}
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
];
inline void print(int x){
){
putchar('-');
x = -x;
}
if(!x)
putchar(');
;
while(x){
output[dirN++] = x % + ;
x /= ;
}
while(dirN)
putchar(output[--dirN]);
putchar('\n');
}
;
struct node{
] , allMax , lMax , rMax , val , sum;
}Tree[MAXN];
int num[MAXN] , N , cntNode , y , z , w;
inline bool son(const int& x){
] == x;
}
void pushup(int x){
Tree[x].lMax = max(Tree[lch].lMax , Tree[lch].sum + Tree[x].val + max(Tree[rch].lMax , ));
Tree[x].rMax = max(Tree[rch].rMax , Tree[rch].sum + Tree[x].val + max(Tree[lch].rMax , ));
Tree[x].allMax = max(max(Tree[lch].allMax , Tree[rch].allMax) , max(Tree[lch].rMax , ) + max(Tree[rch].lMax , ) + Tree[x].val);
Tree[x].sum = Tree[lch].sum + Tree[rch].sum + Tree[x].val;
Tree[x].size = Tree[lch].size + Tree[rch].size + ;
}
inline void ZigZag(int x){
bool f = son(x);
y = Tree[x].fa;
z = Tree[y].fa;
w = Tree[x].ch[f ^ ];
Tree[z].ch[son(y)] = x;
Tree[x].fa = z;
Tree[x].ch[f ^ ] = y;
Tree[y].fa = x;
Tree[y].ch[f] = w;
if(w)
Tree[w].fa = y;
pushup(y);
}
inline void Splay(int x , int tar){
while(Tree[x].fa != tar){
if(Tree[Tree[x].fa].fa != tar)
ZigZag(son(x) == son(Tree[x].fa) ? Tree[x].fa : x);
ZigZag(x);
}
pushup(x);
}
void insert(int& x , int fa , int rk , int val){
if(!x){
x = ++cntNode;
Tree[x].fa = fa;
Tree[x].lMax = Tree[x].rMax = Tree[x].allMax = Tree[x].val = Tree[x].sum = val;
Tree[x].size = ;
Splay(x , );
return;
}
if(rk > Tree[lch].size)
insert(rch , x , rk - Tree[lch].size - , val);
else
insert(lch , x , rk , val);
}
void getKth(int x , int rk , int tar){
if(rk == Tree[lch].size)
Splay(x , tar);
else
if(rk > Tree[lch].size)
getKth(rch , rk - Tree[lch].size - , tar);
else
getKth(lch , rk , tar);
}
inline void remove(int rk){
getKth(root , rk , );
getKth(root , rk - , root);
int t = root;
root = Tree[t].ch[];
Tree[root].ch[] = Tree[t].ch[];
Tree[root].fa = ;
Tree[Tree[t].ch[]].fa = root;
pushup(Tree[t].ch[]);
}
inline void change(int rk , int val){
getKth(root , rk , );
Tree[root].val = val;
pushup(root);
}
inline void query(int l , int r){
getKth(root , l - , );
getKth(root , r + , root);
print(Tree[Tree[Tree[root].ch[]].ch[]].allMax);
}
inline char getc(){
char c = getchar();
while(!isupper(c))
c = getchar();
return c;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4487.in" , "r" , stdin);
freopen("4487.out" , "w" , stdout);
#endif
insert(root , , , );
insert(root , , , );
Tree[].allMax = Tree[].allMax = Tree[].allMax = -INF;
N = read();
; i <= N ; ++i)
insert(root , , i , read());
int a , b;
for(register int M = read() ; M ; --M){
].fa)
Tree[].fa = ;
switch(getc()){
case 'I':
a = read();
b = read();
insert(root , , a , b);
break;
case 'D':
remove(read());
break;
case 'R':
a = read();
b = read();
change(a , b);
break;
case 'Q':
a = read();
b = read();
query(a , b);
break;
}
}
;
}
GSS6
GSS7
树剖+最大子段和
实际上也没什么区别只是莫名码量大了非常多
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
];
inline void print(int x){
;
)
fwrite( , stdout);
else{
){
x = -x;
fwrite( , stdout);
}
while(x){
output[--dirN] = x % + ;
x /= ;
}
fwrite(output + dirN , , strlen(output + dirN) , stdout);
}
fwrite( , , stdout);
}
struct node{
int l , r , lMax , rMax , midMax , sum , mark;
}Tree[MAXN << ];
struct Edge{
int end , upEd;
}Ed[MAXN << ];
int val[MAXN] , head[MAXN] , size[MAXN] , son[MAXN] , fa[MAXN] , dep[MAXN];
int top[MAXN] , ind[MAXN] , rk[MAXN] , N , ts , cntEd , allMax , lMax , rMax;
inline void addEd(int a , int b){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
head[a] = cntEd;
}
void dfs1(int dir , int father){
size[dir] = ;
dep[dir] = dep[fa[dir] = father] + ;
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(!dep[Ed[i].end]){
dfs1(Ed[i].end , dir);
size[dir] += size[Ed[i].end];
if(size[son[dir]] < size[Ed[i].end])
son[dir] = Ed[i].end;
}
}
void dfs2(int dir , int t){
top[dir] = t;
rk[ind[dir] = ++ts] = dir;
if(!son[dir])
return;
dfs2(son[dir] , t);
for(int i = head[dir] ; i ; i = Ed[i].upEd)
if(Ed[i].end != son[dir] && Ed[i].end != fa[dir])
dfs2(Ed[i].end , Ed[i].end);
}
inline void pushup(int dir){
Tree[dir].lMax = max(Tree[dir << ].lMax , Tree[dir << ].sum + Tree[dir << | ].lMax);
Tree[dir].rMax = max(Tree[dir << | ].rMax , Tree[dir << ].rMax + Tree[dir << | ].sum);
Tree[dir].sum = Tree[dir << ].sum + Tree[dir << | ].sum;
Tree[dir].midMax = max(max(Tree[dir << ].midMax , Tree[dir << | ].midMax) , Tree[dir << ].rMax + Tree[dir << | ].lMax);
}
inline void pushdown(int dir){
){
Tree[dir << ].lMax = Tree[dir << ].rMax = Tree[dir << ].midMax = max(Tree[dir << ].sum = Tree[dir].mark * (Tree[dir << ].r - Tree[dir << ].l + ) , );
Tree[dir << | ].lMax = Tree[dir << | ].rMax = Tree[dir << | ].midMax = max(Tree[dir << | ].sum = Tree[dir].mark * (Tree[dir << | ].r - Tree[dir << | ].l + ) , );
Tree[dir << ].mark = Tree[dir << | ].mark = Tree[dir].mark;
Tree[dir].mark = -;
}
}
void init(int dir , int l , int r){
Tree[dir].l = l;
Tree[dir].r = r;
Tree[dir].mark = -;
if(l == r)
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = max(Tree[dir].sum = val[rk[l]] , );
else{
init(dir << , l , (l + r) >> );
init(dir << | , ((l + r) >> ) + , r);
pushup(dir);
}
}
void change(int dir , int l , int r , int val){
if(Tree[dir].l >= l && Tree[dir].r <= r){
Tree[dir].lMax = Tree[dir].rMax = Tree[dir].midMax = max(Tree[dir].sum = (Tree[dir].mark = val) * (Tree[dir].r - Tree[dir].l + ) , );
return;
}
pushdown(dir);
)
change(dir << , l , r , val);
)
change(dir << | , l , r , val);
pushup(dir);
}
void askLeft(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , max(lMax + Tree[dir].rMax , Tree[dir].midMax));
lMax = max(Tree[dir].lMax , Tree[dir].sum + lMax);
return;
}
pushdown(dir);
)
askLeft(dir << | , l , r);
)
askLeft(dir << , l , r);
}
void askRight(int dir , int l , int r){
if(Tree[dir].l >= l && Tree[dir].r <= r){
allMax = max(allMax , max(rMax + Tree[dir].rMax , Tree[dir].midMax));
rMax = max(Tree[dir].lMax , Tree[dir].sum + rMax);
return;
}
pushdown(dir);
)
askRight(dir << | , l , r);
)
askRight(dir << , l , r);
}
inline void work1(int l , int r , int val){
int tl = top[l] , tr = top[r];
while(tl != tr)
if(dep[tl] >= dep[tr]){
change( , ind[tl] , ind[l] , val);
tl = top[l = fa[tl]];
}
else{
change( , ind[tr] , ind[r] , val);
tr = top[r = fa[tr]];
}
if(ind[l] < ind[r])
change( , ind[l] , ind[r] , val);
else
change( , ind[r] , ind[l] , val);
}
inline void work2(int l , int r){
allMax = lMax = rMax = ;
int tl = top[l] , tr = top[r];
while(tl != tr)
if(dep[tl] >= dep[tr]){
askLeft( , ind[tl] , ind[l]);
tl = top[l = fa[tl]];
}
else{
askRight( , ind[tr] , ind[r]);
tr = top[r = fa[tr]];
}
if(ind[l] < ind[r])
askRight( , ind[l] , ind[r]);
else
askLeft( , ind[r] , ind[l]);
print(max(allMax , lMax + rMax));
}
int main(){
N = read();
; i <= N ; i++)
val[i] = read();
; i < N ; i++){
int a = read() , b = read();
addEd(a , b);
addEd(b , a);
}
dfs1( , );
dfs2( , );
init( , , N);
for(int Q = read() ; Q ; Q--){
int a = read() , b = read() , c = read();
)
work1(b , c , read());
else
work2(b , c);
}
;
}
GSS7