首页 > 代码库 > BZOJ1012: [JSOI2008]最大数maxnumber [线段树]

BZOJ1012: [JSOI2008]最大数maxnumber [线段树]

2024-08-21 02:30:33   212人阅读

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 8748  Solved: 3835
[Submit][Status][Discuss]

Description

　　现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96
按2e5建树，单点修改+区间最大值
 
一开始愚蠢的n+MOD防止n为负反而溢出了
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define m ((l+r)>>1)#define lson o<<1,l,m#define rson o<<1|1,m+1,r#define lc o<<1#define rc o<<1|1using namespace std;typedef long long ll;const int N=2e5+5,INF=2e9+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}int n,nn,MOD;char c[2]; int x;int t[N<<2];void build(int o,int l,int r){    if(l==r) t[o]=-INF;    else{        build(lson);        build(rson);    }}void change(int o,int l,int r,int p,int v){    if(l==r) t[o]=v;    else{        if(p<=m) change(lson,p,v);        if(m<p) change(rson,p,v);        t[o]=max(t[lc],t[rc]);    }}int query(int o,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return t[o];    else{        int mx=-INF;        if(ql<=m) mx=max(mx,query(lson,ql,qr));        if(m<qr) mx=max(mx,query(rson,ql,qr));         return mx;    }}int main(){    n=read();MOD=read();    nn=2e5;    build(1,1,nn);    int last=0,len=0;    for(int i=1;i<=n;i++){        scanf("%s",c); x=read();        if(c[0]==‘Q‘){            last=query(1,1,nn,len-x+1,len);            printf("%d\n",last);        }else{            x=(x+last)%MOD;            len++;            change(1,1,nn,len,x);        }    }}

 

 

BZOJ1012: [JSOI2008]最大数maxnumber [线段树]


联系
我们