记录编号	583108	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[雅礼集训 2018 Day10] 贪玩蓝月	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.661 s
提交时间	2023-10-04 16:51:26	内存使用	293.99 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

constexpr int maxn = 5e4 + 5;
constexpr int maxm = 505;
constexpr i64 inf = 1e18;

int n, p, tp1, tp2, stk1[maxn], stk2[maxn], cnt, a[maxn], b[maxn];
i64 tmp[maxm << 1];
struct Knapsack {
	i64 g[maxm];
	void init() { memset(g, -0x3f, sizeof(g)); g[0] = 0; }
	void insert(int w, int v) {
		for(int i = 0;i < p;++ i)
			tmp[i] = g[i];
		for(int i = 0;i < p;++ i)
			tmp[(i + w) % p] = std::max(tmp[(i + w) % p], g[i] + v);
		for(int i = 0;i < p;++ i)
			g[i] = tmp[i];
		return ;
	}
} c[maxn], d[maxn];

i64 qry(Knapsack& a, int ql, int qr) {
	i64 ans = -inf;
	for(int i = ql;i <= qr;++ i)
		ans = std::max(ans, a.g[i]);
	return ans;
}
int Q[maxm << 1], hd, tl;
i64 Qry(Knapsack& a, Knapsack& b, int ql, int qr) {
	i64 ans = -inf;
	for(int i = 0;i < p;++ i)
		tmp[i] = tmp[i + p] = b.g[i];
	for(int i = ql;i <= qr;++ i)
		ans = std::max({ans, a.g[i], b.g[i]});
	int l = ql + p, r = qr + p;
	hd = 1; tl = 0; Q[hd] = Q[tl] = 0;
	for(int i = r;i > l;-- i) {
		while(hd <= tl&&tmp[Q[tl]] <= tmp[i]) Q[tl --] = 0;
		Q[++ tl] = i;
	}
	for(int i = 0;i < p;++ i) {
		while(hd <= tl&&Q[hd] > r) Q[hd ++] = 0;
		while(hd <= tl&&tmp[Q[tl]] <= tmp[l]) Q[tl --] = 0;
		Q[++ tl] = l --; -- r;
		ans = std::max(ans, a.g[i] + tmp[Q[hd]]);
	}
	return ans;
}

int main() {
	freopen("tanwan.in", "r", stdin);
	freopen("tanwan.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	int T; std::cin >> T >> n >> p;
	std::string _s; c[0].init(); d[0].init();
	while(n --) {
		std::cin >> _s;
		if(_s == "IF") {
			int w, v; std::cin >> w >> v; w %= p;
			a[++ cnt] = w; b[cnt] = v; stk1[++ tp1] = cnt;
			c[tp1] = c[tp1 - 1]; c[tp1].insert(w, v);
		} else if(_s == "IG") {
			int w, v; std::cin >> w >> v; w %= p;
			a[++ cnt] = w; b[cnt] = v; stk2[++ tp2] = cnt;
			d[tp2] = d[tp2 - 1]; d[tp2].insert(w, v);
		} else if(_s == "DF") {
			if(!tp1) {
				int mid = tp2 >> 1, lst = tp2; tp2 = 0;
				for(int i = std::min(mid + 1, lst);i;-- i) {
					int id = stk2[i];
					stk1[++ tp1] = id; c[tp1] = c[tp1 - 1];
					c[tp1].insert(a[id], b[id]);
				}
				for(int i = std::min(mid + 1, lst) + 1;i <= lst;++ i) {
					int id = stk2[i];
					stk2[++ tp2] = id; d[tp2] = d[tp2 - 1];
					d[tp2].insert(a[id], b[id]);
				}
			}
			stk1[tp1 --] = 0; 
		} else if(_s == "DG") {
			if(!tp2) {
				int mid = tp1 >> 1, lst = tp1; tp1 = 0;
				for(int i = std::min(mid + 1, lst);i;-- i) {
					int id = stk1[i];
					stk2[++ tp2] = id; d[tp2] = d[tp2 - 1];
					d[tp2].insert(a[id], b[id]);
				}
				for(int i = std::min(mid + 1, lst) + 1;i <= lst;++ i) {
					int id = stk1[i];
					stk1[++ tp1] = id; c[tp1] = c[tp1 - 1];
					c[tp1].insert(a[id], b[id]);
				}
			}
			stk2[tp2 --] = 0;
		} else if(_s == "QU") {
			int l, r; std::cin >> l >> r;
			i64 ans = -inf;
			if(!tp1) {
				ans = qry(d[tp2], l, r);
			} else if(!tp2) {
				ans = qry(c[tp1], l, r);
			} else {
				ans = Qry(c[tp1], d[tp2], l, r);
			}
			if(ans < 0) std::cout << "-1\n";
			else std::cout << ans << '\n';
		}
	}
	return 0;
}