【JSOI2008】最大值

【JSOI2008】最大值

线段树裸题！动态RMQ。

这道题的操作是直接在序列末尾添加数值，所以连\(push_{down}\)，以及建树什么的都不用了。。

这真是写过的最简短的一道\(seg_{tree}\)了2333

（似乎有很多其他做法，不过没有研究qwq（因为太菜））

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

#define ll long long

#define mod d

#define MAXN 200233

#define inf -5223372036854775808

#define leftson cur<<1

#define rightson cur<<1|1

#define mid ((l+r)>>1)

#define push_up ans[cur]=llmax(ans[leftson],ans[rightson])%mod

ll m,d;

int tot=0;

ll llmax(ll x,ll y)

{

	return x>y?x:y;

}

ll ans[MAXN<<2]={};

inline void change(int adc,int cur,int l,int r,int del)

{

	if (l==r)

	{

		ans[cur]=del;

		return;

	}

	if (adc<=mid) change(adc,leftson,l,mid,del);

	if (adc>mid) change(adc,rightson,mid+1,r,del);

	push_up;

}

inline ll query(int adl,int adr,int cur,int l,int r)

{

	if (adl<=l&&r<=adr)

	{

		return ans[cur];

	}

	ll x=inf,y=inf;

	if (adl<=mid) x=query(adl,adr,leftson,l,mid);

	if (adr>mid) y=query(adl,adr,rightson,mid+1,r);

	return llmax(x,y);

}

int main()

{

	scanf("%lld%lld",&m,&d);

	char q;

	ll a,b=0;

	for (int i=1;i<=m;i++)

	{

		cin>>q;

		scanf("%lld",&a);

		if (q=='A')

		{

			change(++tot,1,1,m,(a+b)%mod);

			continue;

		}

		if (a==0) b=0;

		else b=query(tot-a+1,tot,1,1,m);

		printf("%lld\n",b);

	}

	return 0;

}

【JSOI2008】最大值的相关教程结束。