bzoj1012

let-dream-fly 2017-11-22 原文

bzoj1012

1012: [JSOI2008]最大数maxnumber

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
 
————————————我是华丽的分割线——————————————–

Too water!!!

线段树瞎搞。

/**************************************************************
    Problem: 1012
    User: xialan
    Language: C++
    Result: Accepted
    Time:964 ms
    Memory:4412 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int M=200001;
int MAX[M<<2]={0};
void getup(int rt){
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void modify(int l,int r,int rt,int x,int v){
    if(l==r){
        MAX[rt]=v;
        return;
    }
    int m=(l+r)>>1;
    if(x<=m)modify(lson,x,v);
    else modify(rson,x,v);
    getup(rt);
}
int query(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R)return MAX[rt];
    int ans=0;
    int m=(l+r)>>1;
    if(L<=m)ans=max(ans,query(lson,L,R));
    if(m<R)ans=max(ans,query(rson,L,R));
    return ans;
}
 
int main(){
    int m,p;
    scanf("%d%d",&m,&p);
    int t=0,tot=0;
    rep(i,1,m){
        char ch=getchar();int x;
        while(ch!='A'&&ch!='Q')ch=getchar();
        scanf("%d",&x);
        if(ch=='A'){
            modify(1,m,1,++tot,((unsigned)x+t)%p);
        }
        else{
            t=query(1,m,1,tot-x+1,tot);
            printf("%d\n",t);
        }
         
    }
    return 0;
}

 

发表于 2017-11-22 19:11 侠岚sgy 阅读() 评论() 编辑 收藏

 

版权声明:本文为let-dream-fly原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:http://www.cnblogs.com/let-dream-fly/p/7880802.html

bzoj1012的更多相关文章

随机推荐

  1. 安装Archlinux+UEFI启动

    为了安装Arch自己也走了很多弯路,找了很多教程,最后探索出了这样一个安装方法,不一定适用于每个人。ArchW […]...

  2. Python的scrapy之爬取顶点小说网的所有小说

    闲来无事用Python的scrapy框架练练手,爬取顶点小说网的所有小说的详细信息。 看一下网页的构造: tr […]...

  3. 虚拟机(VMware Workstation)的使用方法(转)

    虚拟机(VMware Workstation)的使用方法:http://www.aboutyun.com/th […]...

  4. 【Access】数据库四门功课–[增删改查]基础篇

    一、增 以userinfo为例   1.增加一条完整的数据   INSERT INTO userinfo VA […]...

  5. 主要Linux 平台高可用HA集群软件简介及软件下载

    主要Linux 平台高可用集群软件(High Availability Cluster- HA)简介及软件下载 […]...

  6. C#-Xamarin的Android项目开发(三)——发布、部署、打包

    前言 部署,通常的情况下,它其实也是项目开发的一个难点。 为什么这么说呢?因为,它不是代码开发,所以很多开发者 […]...

  7. 报表如何批量导出成 excel 文件 – IBelieve002

    报表如何批量导出成 excel 文件 批量导出excel 需求说明 报表展现后可以通过工具栏中的导出按钮将当前 […]...

  8. 【JavaScript】ESlint & Prettier & Flow组合,得此三神助,混沌归太清

    Flow Flow的意义 Flow是faceBook开源的一个JavaScript静态类型检查工具,作用类似T […]...

展开目录

目录导航