技术教程 CF280D k-Maximum Subsequence Sum(线段树) 正文

CF280D k-Maximum Subsequence Sum(线段树)

2022-10-15,,,

在做这题时我一开始把\(tag\)写入了结构体

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define QWQ

#ifdef QWQ

#define D_e_Line printf("\n---------------\n")

#define D_e(x) cout << (#x) << " : " << x << "\n"

#define Pause() system("pause")

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define TIME() fprintf(stderr, "\nTIME : %.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define Pause() ;

#define FileOpen() ;

#define FileSave() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> inline ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <='9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Abs(ATP a) {

	return a < 0 ? -a : a;

}

const int N = 1e5 + 7;

int n;

struct RPG {

	int l, r, sum;

	bool operator < (const RPG &com) const {

		return sum < com.sum;

	}

	RPG operator + (const RPG &b) const {

		return (RPG){ l, b.r, sum + b.sum};

	}

};

struct nod {

	RPG lmax, lmin, rmin, rmax, mx, mn, all;

	bool tag;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	bool operator < (const nod &com) const {

		return mx.sum < com.mx.sum;

	}

} t[N << 2];

#define ls rt << 1

#define rs rt << 1 | 1

#define lson rt << 1, l, mid

#define rson rt << 1 | 1, mid + 1, r

inline void Newnode(int rt, int pos, int val) {

	t[rt].lmax = t[rt].lmin = t[rt].rmax = t[rt].rmin = t[rt].mx = t[rt].mn = t[rt].all = (RPG){ pos, pos, val};

}

inline nod Merge(nod x, nod y) {

	nod s;

	s.lmax = max(x.lmax, x.all + y.lmax);

	s.lmin = min(x.lmin, x.all + y.lmin);

	s.rmax = max(y.rmax, x.rmax + y.all);

	s.rmin = min(y.rmin, x.rmin + y.all);

	s.mx = max(max(x.mx, y.mx), x.rmax + y.lmax);

	s.mn = min(min(x.mn, y.mn), x.rmin + y.lmin);

	s.all = x.all + y.all;

	return s;

}

inline void Pushup(int &rt) {

	t[rt] = Merge(t[ls], t[rs]);

}

inline void Pushrev(int rt) {

	swap(t[rt].lmax, t[rt].lmin);

	swap(t[rt].rmax, t[rt].rmin);

	swap(t[rt].mx, t[rt].mn);

	t[rt].lmax.sum = -t[rt].lmax.sum;

	t[rt].lmin.sum = -t[rt].lmin.sum;

	t[rt].rmax.sum = -t[rt].rmax.sum;

	t[rt].rmin.sum = -t[rt].rmin.sum;

	t[rt].mx.sum = -t[rt].mx.sum;

	t[rt].mn.sum = -t[rt].mn.sum;

	t[rt].all.sum = -t[rt].all.sum;

	t[rt].tag ^= 1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Pushdown(int rt) {

	if(!t[rt].tag) return;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	Pushrev(ls);

	Pushrev(rs);

	t[rt].tag = 0;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Modify(int rt, int l, int r, int x, int w) {

	if(l == r){

		Newnode(rt, x, w);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(x <= mid)

		Modify(lson, x, w);

	else

		Modify(rson, x, w);

	Pushup(rt);

}

inline void Updata(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R){

		Pushrev(rt);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(L <= mid) Updata(lson, L, R);

	if(R > mid) Updata(rson, L, R);

	Pushup(rt);

	return;

}

inline nod Query(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R) return t[rt];

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(R <= mid) return Query(lson, L, R);

	else if(L > mid) return Query(rson, L, R);

	else return Merge(Query(lson, L, R), Query(rson, L, R));

	Pushup(rt);

}

nod sta[N];

int top;

inline int Solve(int l, int r, int K) {

	int ans = 0;

	while(K--){

		nod s = Query(1, 1, n, l, r);

		if(s.mx.sum < 0) break;

		ans += s.mx.sum;

		Updata(1, 1, n, s.mx.l, s.mx.r);

		sta[++top] = s;

	}

	while(top){

		nod s = sta[top--];

		Updata(1, 1, n, s.mx.l, s.mx.r);

	}

	return ans;

}

int main() {

//FileOpen();

	io >> n;

	R(i,1,n){

		int x;

		io >> x;

		Modify(1, 1, n, i, x);

	}

	int m;

	io >> m;

	while(m--){

		int opt;

		io >> opt;

		if(opt){

			int l, r, K;

			io >> l >> r >> K;

			printf("%d\n", Solve(l, r, K));

		}

		else{

			int x, w;

			io >> x >> w;

			Modify(1, 1, n, x, w);

		}

	}

	return 0;

}

(注意打感叹号处)

一直没过样例，后来参考一位大佬的代码把\(tag\)单独放外面

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define QWQ

#ifdef QWQ

#define D_e_Line printf("\n---------------\n")

#define D_e(x) cout << (#x) << " : " << x << "\n"

#define Pause() system("pause")

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define TIME() fprintf(stderr, "\nTIME : %.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define Pause() ;

#define FileOpen() ;

#define FileSave() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> inline ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <='9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Abs(ATP a) {

	return a < 0 ? -a : a;

}

const int N = 1e5 + 7;

int n;

struct RPG {

	int l, r, sum;

	bool operator < (const RPG &com) const {

		return sum < com.sum;

	}

	RPG operator + (const RPG &b) const {

		return (RPG){ l, b.r, sum + b.sum};

	}

};

struct nod {

	RPG lmax, lmin, rmin, rmax, mx, mn, all;

	bool operator < (const nod &com) const {

		return mx.sum < com.mx.sum;

	}

} t[N << 2];

bool tag[N << 2]; //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#define ls rt << 1

#define rs rt << 1 | 1

#define lson rt << 1, l, mid

#define rson rt << 1 | 1, mid + 1, r

inline void Newnode(int rt, int pos, int val) {

	t[rt].lmax = t[rt].lmin = t[rt].rmax = t[rt].rmin = t[rt].mx = t[rt].mn = t[rt].all = (RPG){ pos, pos, val};

}

inline nod Merge(nod x, nod y) {

	nod s;

	s.lmax = max(x.lmax, x.all + y.lmax);

	s.lmin = min(x.lmin, x.all + y.lmin);

	s.rmax = max(y.rmax, x.rmax + y.all);

	s.rmin = min(y.rmin, x.rmin + y.all);

	s.mx = max(max(x.mx, y.mx), x.rmax + y.lmax);

	s.mn = min(min(x.mn, y.mn), x.rmin + y.lmin);

	s.all = x.all + y.all;

	return s;

}

inline void Pushup(int &rt) {

	t[rt] = Merge(t[ls], t[rs]);

}

inline void Pushrev(int rt) {

	swap(t[rt].lmax, t[rt].lmin);

	swap(t[rt].rmax, t[rt].rmin);

	swap(t[rt].mx, t[rt].mn);

	t[rt].lmax.sum = -t[rt].lmax.sum;

	t[rt].lmin.sum = -t[rt].lmin.sum;

	t[rt].rmax.sum = -t[rt].rmax.sum;

	t[rt].rmin.sum = -t[rt].rmin.sum;

	t[rt].mx.sum = -t[rt].mx.sum;

	t[rt].mn.sum = -t[rt].mn.sum;

	t[rt].all.sum = -t[rt].all.sum;

	tag[rt] ^= 1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Pushdown(int rt) {

	if(!tag[rt]) return;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	Pushrev(ls);

	Pushrev(rs);

	tag[rt] = 0;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Modify(int rt, int l, int r, int x, int w) {

	if(l == r){

		Newnode(rt, x, w);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(x <= mid)

		Modify(lson, x, w);

	else

		Modify(rson, x, w);

	Pushup(rt);

}

inline void Updata(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R){

		Pushrev(rt);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(L <= mid) Updata(lson, L, R);

	if(R > mid) Updata(rson, L, R);

	Pushup(rt);

	return;

}

inline nod Query(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R) return t[rt];

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(R <= mid) return Query(lson, L, R);

	else if(L > mid) return Query(rson, L, R);

	else return Merge(Query(lson, L, R), Query(rson, L, R));

	Pushup(rt);

}

nod sta[N];

int top;

inline int Solve(int l, int r, int K) {

	int ans = 0;

	while(K--){

		nod s = Query(1, 1, n, l, r);

		if(s.mx.sum < 0) break;

		ans += s.mx.sum;

		Updata(1, 1, n, s.mx.l, s.mx.r);

		sta[++top] = s;

	}

	while(top){

		nod s = sta[top--];

		Updata(1, 1, n, s.mx.l, s.mx.r);

	}

	return ans;

}

int main() {

//FileOpen();

	io >> n;

	R(i,1,n){

		int x;

		io >> x;

		Modify(1, 1, n, i, x);

	}

	int m;

	io >> m;

	while(m--){

		int opt;

		io >> opt;

		if(opt){

			int l, r, K;

			io >> l >> r >> K;

			printf("%d\n", Solve(l, r, K));

		}

		else{

			int x, w;

			io >> x >> w;

			Modify(1, 1, n, x, w);

		}

	}

	return 0;

}

(注意感叹号处)

就成功过掉了

这是为什么呢？是哪儿影响的呢？

大佬发话

原来是\(Merge()\)处没有初始化！

模拟费用流，线段树维护区间

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define QWQ

#ifdef QWQ

#define D_e_Line printf("\n---------------\n")

#define D_e(x) cout << (#x) << " : " << x << "\n"

#define Pause() system("pause")

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define TIME() fprintf(stderr, "\nTIME : %.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define Pause() ;

#define FileOpen() ;

#define FileSave() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> inline ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <='9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Abs(ATP a) {

	return a < 0 ? -a : a;

}

const int N = 1e5 + 7;

int n;

struct RPG {

	int l, r, sum;

	bool operator < (const RPG &com) const {

		return sum < com.sum;

	}

	RPG operator + (const RPG &b) const {

		return (RPG){ l, b.r, sum + b.sum};

	}

};

struct nod {

	RPG lmax, lmin, rmin, rmax, mx, mn, all;

	bool tag;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	bool operator < (const nod &com) const {

		return mx.sum < com.mx.sum;

	}

} t[N << 2];

#define ls rt << 1

#define rs rt << 1 | 1

#define lson rt << 1, l, mid

#define rson rt << 1 | 1, mid + 1, r

inline void ChangeNode(int rt, int pos, int val) {

	t[rt].lmax = t[rt].lmin = t[rt].rmax = t[rt].rmin = t[rt].mx = t[rt].mn = t[rt].all = (RPG){ pos, pos, val};

}

inline nod Merge(nod x, nod y) {

	nod s;

	s.lmax = max(x.lmax, x.all + y.lmax);

	s.lmin = min(x.lmin, x.all + y.lmin);

	s.rmax = max(y.rmax, x.rmax + y.all);

	s.rmin = min(y.rmin, x.rmin + y.all);

	s.mx = max(max(x.mx, y.mx), x.rmax + y.lmax);

	s.mn = min(min(x.mn, y.mn), x.rmin + y.lmin);

	s.all = x.all + y.all;

	s.tag = false;

	return s;

}

inline void Pushup(int &rt) {

	t[rt] = Merge(t[ls], t[rs]);

}

inline void Pushrev(int rt) {

	swap(t[rt].lmax, t[rt].lmin);

	swap(t[rt].rmax, t[rt].rmin);

	swap(t[rt].mx, t[rt].mn);

	t[rt].lmax.sum = -t[rt].lmax.sum;

	t[rt].lmin.sum = -t[rt].lmin.sum;

	t[rt].rmax.sum = -t[rt].rmax.sum;

	t[rt].rmin.sum = -t[rt].rmin.sum;

	t[rt].mx.sum = -t[rt].mx.sum;

	t[rt].mn.sum = -t[rt].mn.sum;

	t[rt].all.sum = -t[rt].all.sum;

	t[rt].tag ^= 1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Pushdown(int rt) {

	if(!t[rt].tag) return;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	Pushrev(ls);

	Pushrev(rs);

	t[rt].tag = 0;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

}

inline void Modify(int rt, int l, int r, int x, int w) {

	if(l == r){

		ChangeNode(rt, x, w);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(x <= mid)

		Modify(lson, x, w);

	else

		Modify(rson, x, w);

	Pushup(rt);

}

inline void Updata(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R){

		Pushrev(rt);

		return;

	}

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(L <= mid) Updata(lson, L, R);

	if(R > mid) Updata(rson, L, R);

	Pushup(rt);

	return;

}

inline nod Query(int rt, int l, int r, int L, int R) {

	if(L <= l && r <= R) return t[rt];

	Pushdown(rt);

	int mid = (l + r) >> 1;

	if(R <= mid) return Query(lson, L, R);

	else if(L > mid) return Query(rson, L, R);

	else return Merge(Query(lson, L, R), Query(rson, L, R));

	Pushup(rt);

}

nod sta[N];

int top;

inline int Solve(int l, int r, int K) {

	int ans = 0;

	while(K--){

		nod s = Query(1, 1, n, l, r);

		if(s.mx.sum < 0) break;

		ans += s.mx.sum;

		Updata(1, 1, n, s.mx.l, s.mx.r);

		sta[++top] = s;

	}

	while(top){

		nod s = sta[top--];

		Updata(1, 1, n, s.mx.l, s.mx.r);

	}

	return ans;

}

int main() {

//FileOpen();

	io >> n;

	R(i,1,n){

		int x;

		io >> x;

		Modify(1, 1, n, i, x);

	}

	int m;

	io >> m;

	while(m--){

		int opt;

		io >> opt;

		if(opt){

			int l, r, K;

			io >> l >> r >> K;

			printf("%d\n", Solve(l, r, K));

		}

		else{

			int x, w;

			io >> x >> w;

			Modify(1, 1, n, x, w);

		}

	}

	return 0;

}

CF280D k-Maximum Subsequence Sum(线段树)的相关教程结束。

《CF280D k-Maximum Subsequence Sum(线段树).doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!