[JSOI2008]最大数

妖狐艹你老母 2021-12-21 21:23 198阅读 0赞

这道题是板子题，用来练习线段树。

1 #include <bits/stdc++.h>
     2 
     3 using namespace std;
     4 
     5 #define re register
     6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
     7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
     8 #define maxx(a, b) a = max(a, b);
     9 #define minn(a, b) a = min(a, b);
    10 #define LL long long
    11 #define inf (1 << 30)
    12 
    13 const int maxn = 2e5 + 5, N = 2e5;
    14 
    15 struct Seg_T {
    16 #define lson (o << 1)
    17 #define rson (o << 1 | 1)
    18     int v[maxn << 4];
    19     void pushup(int o) { v[o] = max(v[lson], v[rson]); }
    20     void add(int o, int l, int r, int x, int t) {
    21         if (l == r) { v[o] = t; return; }
    22         int mid = (l + r) >> 1;
    23         if (x <= mid) add(lson, l, mid, x, t);
    24         else add(rson, mid+1, r, x, t);
    25         pushup(o);
    26     }
    27     int query(int o, int l, int r, int ql, int qr) {
    28         if (ql <= l && r <= qr) return v[o];
    29         int mid = (l + r) >> 1, ans = 0;
    30         if (ql <= mid) ans = max(ans, query(lson, l, mid, ql, qr));
    31         if (mid < qr) ans = max(ans, query(rson, mid+1, r, ql, qr));
    32         return ans;
    33     }
    34 } S;
    35 
    36 int n, L = 0;
    37 LL D, t;
    38 
    39 int main() {
    40     scanf("%d %lld", &n, &D);
    41 
    42     rep(i, 1, n) {
    43         char c[2]; LL x;
    44         scanf("%s %lld", c, &x);
    45         if (c[0] == 'Q') printf("%lld\n", t = S.query(1, 1, N, L-x+1, L));
    46         else {
    47             L++;
    48             S.add(1, 1, N, L, (t+x) % D);
    49         }
    50     }
    51 
    52     return 0;
    53 }

转载于:https://www.cnblogs.com/ac-evil/p/10325408.html

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关 [JSOI2015]最大公约数

[题目][Link 1] 一个非常众所周知的结论，一个序列的前缀\\(\\gcd\\)只会有\\(\\log\\)种取值于是考虑一下一些暴力的东西，我们枚举每个点作为左端

╰+攻爆jí腚メ/ 2023年10月11日 11:20/ 0 赞/ 29 阅读

相关 P1197-[JSOI2008]星球大战

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

Myth丶恋晨/ 2023年06月01日 08:47/ 0 赞/ 4 阅读

相关 179. 最大数

> 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。 > > 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。 >

比眉伴天荒/ 2022年10月19日 05:39/ 0 赞/ 163 阅读

相关最大递增数

输入一串数字，找到其中包含的最大递增数。递增数是指相邻的数位从小到大排列的数字。如： 2895345323，递增数有：289，345，23, 那么最大的递增数为345。运行时间

男娘i/ 2022年08月01日 18:28/ 0 赞/ 167 阅读

相关【单调队列】1012: [JSOI2008]最大数maxnumber

Think: 1知识点：单调队列单调栈 2题意：两种操作，操作1：查询当前数列中末尾x个数中的最大值；操作2：输入数x，将x加上前一次查询结果t(初始t默认

我会带着你远行/ 2022年06月09日 02:28/ 0 赞/ 143 阅读

相关 [JSOI2008]最大数

这道题是板子题，用来练习线段树。 1 include <bits/stdc++.h> 2 3 using namespace std;

妖狐艹你老母/ 2021年12月21日 21:23/ 0 赞/ 199 阅读

相关 [JSOI2008]最大数

[题目传送门][Link 1] 这道题需要解决的是区间求值和单点修改，可以用线段树求解，首先构造一颗\[1,m\]的“空树”（序列至多有m个数），即每个节点维护的信息均为0，

野性酷女/ 2021年12月10日 10:15/ 0 赞/ 175 阅读

相关 Luogu P1198 [JSOI2008]最大数单调队列/ST表

开一个单调队列，下标递增，值递减。然后在上面二分最大数。如果加上并查集可以做到接近线性。还有一种是插入一个数然后，从后向前更新ST表。 include<c

布满荆棘的人生/ 2021年11月17日 15:28/ 0 赞/ 245 阅读

相关 BZOJ 1567: [JSOI2008]Blue Mary的战役地图

[传送门][Link 1] 考虑二分答案暴力 $n^4$ 枚举两个矩形右下角，如果能做到 $O(1)$ 判断那么复杂度就可行那么容易想到二维哈希，然后直接搞就好了...

曾经终败给现在/ 2021年10月19日 04:42/ 0 赞/ 194 阅读

相关 [JSOI2010]连通数

这个题目有毒。我同学跟我说这个是强连通分量水题，然后我就打$tarjan$，结果$WA ，WA，WA$ 思考许久没想出来哪里错了。于是仔细思考，可以用BFS做，于是我

曾经终败给现在/ 2021年10月01日 01:18/ 0 赞/ 269 阅读