0分呀 我用树状数组做的
查看原帖
0分呀 我用树状数组做的
520264
Clement_D_Alger楼主2024/8/20 15:02

请帮我看看为啥不能用树状数组。

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

int val[400005];
int tree[400005];
long long t, n, m, k, l;
int lowbit(int x)
{
	return x & (-x);
}
void add(int id)
{
	for(int i = id; i; i -= lowbit(i))
	{
		tree[i] = max(tree[i], val[id]);
	}
}
int find(int id)
{
	int ma = val[id];
	for(int i = id; i <= l; i += lowbit(i))
	{
		ma = max(ma, tree[i]);
	}
	return ma;
}

int main()
{ 
	cin >> n >> m;
	char c;
	while(n--)
	{
		cin >> c >> k;
		if(c  ==  'A')
		{
			t += k;
			t %= m;
			val[++l] = t;
			add(l);
		}
		else
		{
			t = find(l - k + 1);
			cout << t << '\n';
		}
	}
	return 0; 
}

2024/8/20 15:02
加载中...