henrytb 的博客

henrytb 的博客

题解 P1198 【[JSOI2008]最大数】

posted on 2018-11-19 18:04:53 | under 题解 |

这道题就是线段树的简单应用啦~

因为一开始数组里一个数都没有,所以不用建树

标记也不用打qwq

注意区间长度为 $0$ 的情况就AC啦qwq

附上代码:

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
long long d,t;
long long s[8*N];
void pluss(int l,int r,int x,int a,long long pl){
    if(l==r){
        s[x]+=pl;
        return;
    }
    int midd=(l+r)/2;
    if(a<=midd)pluss(l,midd,x*2,a,pl);
    if(a>midd)pluss(midd+1,r,x*2+1,a,pl);
    s[x]=max(s[x*2],s[x*2+1]);
}
long long ask(int l,int r,int x,int a,int b){
    if((a<=l)&&(b>=r))return s[x];
    long long summ=-2147483647;
    int midd=(l+r)/2;
    if (a<=midd)summ=max(summ,ask(l,midd,x*2,a,b));
    if (b>midd)summ=max(summ,ask(midd+1,r,x*2+1,a,b));
    return summ;
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d %lld\n",&m,&d);
    for(int i=1;i<=m;i++){
        char kkk;
        scanf("%c ",&kkk);
        if(kkk=='A'){
            n++;
            long long x;
            scanf("%lld\n",&x);
            pluss(1,m,1,n,(x+t)%d);
        }
        if(kkk=='Q'){
            int x;
            scanf("%d\n",&x);
            if(x==0){
                printf("0\n");
                continue;
            }
            t=ask(1,m,1,n-x+1,n);
            printf("%lld\n",t);
        }
    }
    return 0;
}