M_sea

洛谷1198 [JSOI2008]最大数
LuoguBZOJ算法线段树。Q操作就是普通查询,A操作可以看做单点赋值。维护一下$lastans$和最后位置就行...
扫描右侧二维码阅读全文
28
2017/12

洛谷1198 [JSOI2008]最大数

Luogu

BZOJ

算法

线段树。

Q操作就是普通查询,A操作可以看做单点赋值。

维护一下$lastans$和最后位置就行。

我竟然在这题上爆0数次,身败名裂

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int MAXN=200000+10;
const int INF=2e9+10;

struct Segment_Tree {
    ll maxv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) { maxv[o]=max(maxv[lson],maxv[rson]); }
    inline void build(int o,int l,int r) {
        if (l==r) { maxv[o]=-INF; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid); build(rson,mid+1,r);
        pushup(o);
    }
    inline void change(int o,int l,int r,int v,ll w) {
        if (l==r) { maxv[o]=w; return; }
        int mid=(l+r)>>1;
        if (v<=mid) change(lson,l,mid,v,w);
        else change(rson,mid+1,r,v,w);
        pushup(o);
    }
    inline ll query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return maxv[o];
        int mid=(l+r)>>1; ll rt=-INF;
        if (ql<=mid) rt=max(rt,query(lson,l,mid,ql,qr));
        if (qr>mid) rt=max(rt,query(rson,mid+1,r,ql,qr));
        pushup(o); return rt;
    }
} T;

int pos;
ll t;

int main() {
    int m,d; scanf("%d%d",&m,&d);
    T.build(1,1,m);
    for (re int i=1;i<=m;++i) {
        char op[5];
        scanf("%s",op);
        if (op[0]=='Q') {
            int L; scanf("%d",&L);
            printf("%lld\n",t=T.query(1,1,m,pos-L+1,pos));
        }
        else {
            ll n; scanf("%lld",&n);
            ++pos;
            T.change(1,1,m,pos,(t+n+d)%d);
        }
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 24 PM

1 条评论

  1. wsm000

    这题不是可以不建树吗?qwq

发表评论