Problem Specification Value
Time Limit 3 Sec
Memory Limit 162 MB
Submit 7661
Solved 3303

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

HINT

数据如下 http: //pan. baidu. com/s/1i4JxCH3

Source

这道题可以直接用线段树水过......

而且因为并不需要对整个区间进行操作所以change 函数也可以写成自底向上的线段树...... 同时 change 就不需要写成区间修改了.

然而为什么我的代码和 hzwer 的代码对拍了很久还是没有 AC (和他的结果一模一样但是就是不能通过 bzoj, 再者百度盘上的也都测过没问题~

为了让 Atom 不要把_n, __n, ___n 都识别成斜体和粗体害的我把所有_n 都加上了四个下划线 233


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long ll;
const int maxn = 800100;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

class SegmentTree
{
public:
    int pwn, n, lb[maxn], rb[maxn];
    ll mn[maxn];
    void build_tree(int ____n)
    {
        // An optimized segment tree which abandons all unused functions in this problem
        n = 0; pwn = 1; while (pwn < ____n) pwn <<= 1;
        ____n = pwn;
        for (int i = ____n; i <= ____n * 2 - 1; i++) {
            lb[i] = rb[i] = i - ____n + 1;
            mn[i] = inf;
        }
        for (int i = ____n - 1; i >= 1; i--) {
            lb[i] = lb[2 * i];
            rb[i] = rb[2 * i + 1];
            mn[i] = inf;
        }
        return ;
    }
    void append(ll v)
    {
        int p = pwn + n;
        mn[p] = v;
        p >>= 1;
        while (p) {
            mn[p] = max(mn[2 * p], mn[2 * p + 1]);
            p >>= 1;
        }
        n++;
        return ;
    }
    ll query(int p, int l, int r)
    {
        if (lb[p] == l && rb[p] == r)
            return mn[p];
        if (r <= rb[2 * p])
            return query(2 * p, l, r);
        if (l >= lb[2 * p + 1])
            return query(2 * p + 1, l, r);
        return max(query(2 * p, l, rb[2 * p]),
                query(2 * p + 1, lb[2 * p + 1], r));
    }
    ll query(int d)
    {
        return query(1, max(1, n + 1 - d), n);
    }
} st;

int m, D, t = 0;

int main(int argc, char** argv)
{
    scanf("%d%lld", &m, &D);
    st.build_tree(m);
    for (int i = 1; i <= m; i++) {
        char c[100];
        ll v;
        scanf("%s%lld", &c, &v);
        if (c[0] == 'A') {
            st.append((t + v) % D);
        } else if (c[0] == 'Q') {
            t = st.query(v);
            printf("%lld\n", t);
        }
    }
    return 0;
}

这是 hzwer AC 的代码:

#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
int m,mod,last,cnt;
struct data{int l,r,mx;}t[800005];
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;t[k].mx=-inf;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
int ask(int k,int x,int y)
{
    int l=t[k].l,r=t[k].r;
    if(l==x&&r==y)return t[k].mx;
    int mid=(l+r)>>1;
    if(y<=mid)return ask(k<<1,x,y);
    else if(x>mid)return ask(k<<1|1,x,y);
    else return max(ask(k<<1,x,mid),ask(k<<1|1,mid+1,y));
}
void insert(int k,int x,int y)
{
    int l=t[k].l,r=t[k].r;
    if(l==r){t[k].mx=y;return;}
    int mid=(l+r)>>1;
    if(x<=mid)insert(k<<1,x,y);
    else insert(k<<1|1,x,y);
    t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
}
int main()
{
    scanf("%d%d",&m,&mod);
    build(1,1,m);
    for(int i=1;i<=m;i++)
    {
        char ch[5];scanf("%s",ch);
        int x;
        if(ch[0]=='A')
        {
            cnt++;
            scanf("%d",&x);x=(x+last)%mod;
            insert(1,cnt,x);
        }
        else
        {
            scanf("%d",&x);
            last=ask(1,cnt-x+1,cnt);
            printf("%d\n",last);
        }
    }
    return 0;
}
from pydatagen import *
a = randrange(3, 200000)
d = randrange(964, 1047483000)
printf('%d %d\n' % (a, d))
printf('A %d\n' % randrange(1, 1047483647))
sz = 1
for i in range(1, a):
    q = choice(['A', 'Q'])
    if q == 'Q':
        printf('Q %d\n' % randrange(1, sz + 1))
    elif q == 'A':
        printf('A %d\n' % randrange(1, 1047483647))
fclose()