제출 #1257770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257770		pasta	ZIGZAG (INOI20_zigzag)	C++20	100 / 100	717 ms	86580 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define lc (id * 2)
#define rc (lc + 1)
#define int long long
const int maxn = 3e5 + 10;

struct Node {
	int ans, L, R, sz, LI, LD, RI, RD;
};

struct Lazy {
	int sum;
	bool mul;
};


Node seg[maxn * 4];
Lazy lazy[maxn * 4];
int n, q, a[maxn];

Node merge(Node a, Node b) {
	Node ret;
	ret.sz = a.sz + b.sz;
	ret.L = a.L;
	ret.R = b.R;
	
	if (a.R < b.L) {
		ret.ans = a.ans + b.ans + (a.RI * b.LD);
		ret.LD = a.LD + ((a.LD == a.sz && a.sz % 2 == 0)? b.LD : 0);
		ret.LI = a.LI + ((a.LI == a.sz && a.sz % 2 == 1)? b.LD : 0);
		
		ret.RI = b.RI + ((b.RI == b.sz && b.sz % 2 == 0)? a.RI : 0);
		ret.RD = b.RD + ((b.RD == b.sz && b.sz % 2 == 1)? a.RI : 0);		
	}
	else if (a.R > b.L) {
		ret.ans = a.ans + b.ans + (a.RD * b.LI);
		ret.LD = a.LD + ((a.LD == a.sz && a.sz % 2 == 1)? b.LI : 0);
		ret.LI = a.LI + ((a.LI == a.sz && a.sz % 2 == 0)? b.LI : 0);
		
		ret.RI = b.RI + ((b.RI == b.sz && b.sz % 2 == 1)? a.RD : 0);
		ret.RD = b.RD + ((b.RD == b.sz && b.sz % 2 == 0)? a.RD : 0);
	}
	else {
		// a.r == b.l
		ret.ans = a.ans + b.ans;
		ret.LD = a.LD;
		ret.LI = a.LI;
		ret.RD = b.RD;
		ret.RI = b.RI;
	}
	
	return ret;
}



void build(int id = 1, int l = 1, int r = n + 1) {
	lazy[id].sum = 0;
	lazy[id].mul = 0;
	if (l + 1 == r) {
		seg[id].ans = 1;
		seg[id].sz = 1;
		seg[id].LD = seg[id].LI = seg[id].RD = seg[id].RI = 1;
		seg[id].L = seg[id].R = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(lc, l, mid);
	build(rc, mid, r);
	seg[id] = merge(seg[lc], seg[rc]);
}


void Apply(int id, Lazy lz) {
	if (lz.mul) {
		swap(seg[id].LI, seg[id].LD);
		swap(seg[id].RI, seg[id].RD);
		seg[id].L *= -1;
		seg[id].R *= -1;
		lazy[id].mul ^= 1;
		lazy[id].sum *= -1;
				
	}
	seg[id].L += lz.sum;
	seg[id].R += lz.sum;
	lazy[id].sum += lz.sum;
	return;
}

void Push(int id) {
	Apply(lc, lazy[id]);
	Apply(rc, lazy[id]);
	lazy[id].sum = 0;
	lazy[id].mul = 0;
	return;
}


void update(int ql, int qr, Lazy x, int id = 1, int l = 1, int r = n + 1) {
	if (r <= ql || qr <= l)
		return;
		
	if (ql <= l && r <= qr) {
		Apply(id, x);
		return;
	}
	
	Push(id);
	int mid = (l + r) / 2;
	update(ql, qr, x, lc, l, mid);
	update(ql, qr, x, rc, mid, r);
	seg[id] = merge(seg[lc], seg[rc]);
}


Node get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
//	if (r <= ql || qr <= l)
//		return 0;
		
	if (ql <= l && r <= qr) {
		return seg[id];
	}
	
	Push(id);
	int mid = (l + r) / 2;
	if (qr <= mid) {
		return get(ql, qr, lc, l, mid);
	}
	else if (mid <= ql) {
		return get(ql, qr, rc, mid, r);
	}
	else {
		return merge(get(ql, qr, lc, l, mid), get(ql, qr, rc, mid, r));
	}
}

signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build();
	while (q--) {
		string cmd; cin >> cmd;
		if (cmd == "+") {
			int l, r, x; cin >> l >> r >> x;
			Lazy lz;
			lz.sum = x;
			lz.mul = 0;
			update(l, r + 1, lz);
		}
		else if (cmd == "?") {
			int l, r;
			cin >> l >> r;
//			cout << seg[1].ans << '\n';
			cout << get(l, r + 1).ans << '\n';
		}
		else {
			int l, r; cin >> l >> r;
			Lazy lz;
			lz.sum = 0;
			lz.mul = 1;
			update(l, r + 1, lz);
		}
	}	
}

/*
6 5
-2 7 3 4 1 6
+ 3 5 4
\* 1 6
? 2 5
+ 5 6 -3
? 2 5
*/

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15