双端背包

题意：

有 \(n \leq 5000\) 个操作，支持在前端后端插入或删除一个值\(< K \leq 5000\)，询问价值和模 \(K\) 在 \([l, r]\) 的方案数个数 modulo \(998244353\)。

栈:

如果用线段树类似结构时间复杂度是 \(O(n^2\log n)\)。

考虑开两个栈维护前缀的值和后缀的值，并同时做多版本背包。

如果一边删到空就直接暴力重构。

询问时前缀和类似的优化即可。

设 \(f(x)\) 为现在加入的数个数，\(g(x)\) 为两栈的个数之差，总势能即为 \(f(x) + g(x)\)。

对于加入和删除操作，\(f(x)\) 和 \(g(x)\) 会同时 +1 或 -1,是常数级别的变化。

对于暴力重构，\(f(x)\) 会减半, \(g(x)\) 会为 \(0 / 1\)，两部分只会减小，消费了前面加入操作的势能。

因此总势能的上界是 \(O(n)\) 的，一次操作是 \(O(k)\) 的。

总的时间复杂度就是 \(O(nk)\) 。

代码:

#include
using namespace std;

using ll = long long;
const int MAXN = 5010;
const int INF = 0x7fffffff;
const int mod = 998244353;

template 
void Read(T &x) {
	x = 0; T f = 1; char a = getchar();
	for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
	for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
	x *= f;
}

int add(int a, int b) {
	int c = a + b;
	if (c >= mod) c -= mod;
	if (c < 0) c += mod;
	return c; 
}
int mul(int a, int b) {
	return 1ll * a * b % mod;
}

int Q, K;  

struct Stack {
	stack a; 
	int f[MAXN][MAXN]; 
	void Init() {
		memset(f, 0, sizeof(f));
		f[0][0] = 1; 
	}
}A, B;
void Insert(Stack &a, int x) {
	int now = a.a.size(); 
	for (int i = 0; i < K; i ++)
		a.f[now + 1][i] = a.f[now][i]; 
	for (int i = K - 1; i >= 0; i --)
		a.f[now + 1][(i + x) % K] = add(a.f[now + 1][(i + x) % K], a.f[now][i]);
	a.a.push(x); 
}

void Rebuild(Stack &a, Stack &b) {
	int siz = a.a.size();
	vector  c;
	while (!a.a.empty())
		c.emplace_back(a.a.top()), a.a.pop(); 
	a.Init(); b.Init(); 
	
	for (int i = siz / 2; i < siz; i ++)
		Insert(b, c[i]); 
	for (int i = siz / 2 - 1; i >= 0; i --)
		Insert(a, c[i]);

}
void Delete(Stack &a) {
	int x = a.a.top(), now = a.a.size(); 
	for (int i = 0; i <= K; i ++)	
		a.f[now][i] = 0; 
	a.a.pop();
}
int sum[MAXN];
int Query(int l, int r) {
	int ans = 0, nowa = A.a.size(), nowb = B.a.size(), sum = 0;
	for (int i = l; i <= r; i ++)
		sum = add(sum, B.f[nowb][i]); 
		
	ans = mul(A.f[nowa][0], sum);
	for (int i = 1; i < K; i ++) {
		sum = add(sum, - B.f[nowb][(r - i + 1 + K) % K]);
		sum = add(sum, B.f[nowb][(l - i + K) % K]);
		ans = add(ans, mul(A.f[nowa][i], sum));
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false); 
	cin >> Q >> K;
	A.Init(); B.Init();
	while (Q --) {
		int opt, v, l, r;
		cin >> opt;
		if (opt == 1) {
			cin >> v;
			Insert(A, v); 
		} 
		if (opt == 2) {
			cin >> v;
			Insert(B, v); 
		}
		if (opt == 3) {
			if (A.a.empty()) Rebuild(B, A);  
			Delete(A);
		}
		if (opt == 4) {
			if (B.a.empty()) Rebuild(A, B);  
			Delete(B);
		}
		if (opt == 5) {
			cin >> l >> r;
			cout << Query(l, r) << endl;
		}
	}
	return 0;
}