1 solutions

  • 0
    @ 2023-11-10 22:59:43

    难度: 绿

    算法: 线段树,或其它数据结构

    单点修改(把在最后插一个数的操作视为将最后一位从 00 改为 xx),区间查询最大值,直接线段树。

    没什么好说的,自己看代码吧。

    #include<bits/stdc++.h>
    using namespace std;
    int q,x,n,a=0,p;
    int s[840000],l[840000],r[840000];
    char c;
    void build(int le,int ri,int id){
    	l[id]=le,r[id]=ri;
    	if(le==ri) return ;
    	build(le,(le+ri)/2,2*id);
    	build((le+ri)/2+1,ri,2*id+1);
    }
    void upd(int pos,int num,int id){
    	int nl=l[id],nr=r[id],mid=(nl+nr)/2;
    	if(nl==pos&&nr==pos){
    		s[id]=max(s[id],num);
    		return;
    	} 
    	if(pos<=mid) upd(pos,num,id*2);
    	if(pos>mid) upd(pos,num,id*2+1);
    	s[id]=max(s[id*2],s[id*2+1]);
    }
    int que(int le,int ri,int id){
    	int nl=l[id],nr=r[id],mid=(nl+nr)/2;
    	if(le<=nl&&nr<=ri) return s[id];
    	int res=0;
    	if(le<=mid) res=max(res,que(le,ri,id*2));
    	if(ri>mid) res=max(res,que(le,ri,id*2+1));
    	return res;
    }
    int main(){
    	ios::sync_with_stdio(0);
    	cin>>q>>p;
    	build(1,q,1);
    	while(q--){
    		cin>>c>>x;
    		if(c=='A'){
    			x=((long long)x+a)%p;
    			upd(++n,x,1);
    		}
    		else{
    			a=que(n-x+1,n,1);
    			printf("%d\n",a);
    		}
    	}
    }
    
    • 1

    Information

    ID
    129
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    9
    Tags
    # Submissions
    9
    Accepted
    4
    Uploaded By