欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[线段树] 洛谷P1198

程序员文章站 2022-03-22 13:12:26
...

题目

[线段树] 洛谷P1198
题目链接:https://www.luogu.com.cn/problemnew/solution/P1198

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int tree[800010];
int mod;
 void add(int s,int k,int o,int l,int r)
    {
        if(l==r)
        {
            tree[o]=k;
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=s) add(s,k,o<<1,l,mid);
        if(mid<s) add(s,k,o<<1|1,mid+1,r);
        tree[o]=max(tree[o<<1],tree[o<<1|1])%mod;
    }
int query(int ll,int rr,int o,int l,int r)
    {
        if(ll<=l&&rr>=r) return tree[o];
        int mid=(l+r)>>1;
        int a=-INF,b=-INF;
        if(mid>=ll) a=query(ll,rr,o<<1,l,mid);
        if(mid<rr) b=query(ll,rr,o<<1|1,mid+1,r);
        return max(a,b);
}
int cnt,t;	char s[2];int x;
signed main(){
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	scanf("%lld%lld",&n,&mod);
	memset(tree,0,sizeof tree);
	int t1=n;
	while(t1--){
		scanf("%s %lld",s,&x);
		if(s[0]=='A'){
			add(cnt+1,(x+t)%mod,1,1,n);
            cnt++;
		//	for(int i=1;i<=cnt;i++) printf("%lld\n",tree[i]);
		}
	
		if(s[0]=='Q'){
			if(x==0) t=0;
			else t=query(cnt-x+1,cnt,1,1,n)%mod;
			//for(int i=1;i<=n*4;i++) printf("%lld\n",tree[i]);
		//	printf("")
			printf("%lld\n",t); 
		}
	}
    return 0;
}