非常水的一道题

懵逼的 题目

传送至 Luogu

扯淡的 题解

线段树棵题…

然后还有一种做法单调栈…要不然老夫才懒得做这破题…
单调栈, 就是要栈内元素保持单调(废话), 这样可以使栈顶元素是当前区间的最值, 一般用于只在末尾插入节点而不再弹出求最值的时候使用(有弹出是不是就是单调队列了)没什么好说的…写起来非常的休闲…
记录一个编号栈保存每个数插入进来的位置, 然后二分这个位置就行
注意细节…不要用scanf读字符不要用scanf读字符不要用scanf读字符(三遍完成)
还有lower_bound返回大于等于
upper_bound返回大于
要记清楚…

沙茶的 代码

线段树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LL long long
using namespace std;
struct node
{
    int le, ri, zh;
}b[MAXN << 2];
int n, ca;
void js(int, int, int);
int cx(int, int, int);
void xg(int, int, int);
inline void pushup(int);
int main()
{
//    scanf("%d%d", &n, &ca);
//    getchar();
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> ca;
    js(1, 1, n);
    int t = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        char src;
        int srx;
//        scanf("%c%d", &src, &srx);
//        getchar();
        cin >> src >> srx;
        if (src == 'A')
            xg(1, ++cnt, (int)(((LL)t + srx) % ca));
        else if (cnt && srx)
//            printf("%d\n", t = cx(1, cnt - srx + 1, cnt));
            cout << (t = cx(1, cnt - srx + 1, cnt)) << endl;
        else
//            puts("0");
            cout << 0 << endl;
    }
    return 0;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].zh = 0;
        return ;
    }
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg(int dq, int wz, int zh)
{
    if (b[dq].le == b[dq].ri && b[dq].le == wz)
    {
        b[dq].zh = zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz > mi)
        xg(RS(dq), wz, zh);
    else if (wz <= mi)
        xg(LS(dq), wz, zh);
    pushup(dq);
}
int cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        return cx(RS(dq), le, ri);
    else if (ri <= mi)
        return cx(LS(dq), le, ri);
    else
        return max(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
inline void pushup(int dq)
{
    b[dq].zh = max(b[LS(dq)].zh, b[RS(dq)].zh);
}

单调栈

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LL long long
#define pii pair<int, int>
using namespace std;
LL n, ca, t = 0;
int dds[MAXN], bh[MAXN], top;
int cnt;
void ins(int);
int cx(int);
int main()
{
//    scanf("%d%d", &n, &ca);
    cin >> n >> ca;
    for (int i = 1; i <= n; i++)
    {
        char srs;
        LL srx;
        cin >> srs >> srx;
        if (srs == 'A')
            ins((int)((LL)srx + t) % ca);
        else if (cnt && srx)
            cout << (t = cx(cnt - srx + 1)) << endl;
        else
            cout << 0 << endl;
    }
    return 0;
}
void ins(int x)
{
    while (top && dds[top] < x)
    { --top; }
    dds[++top] = x;
    bh[top] = ++cnt;
}
int cx(int wz)
{
    int x = lower_bound(bh + 1, bh + top + 1, wz) - bh;
    return dds[x];
}

By 被主席树弄懵逼的 && 把学长弄疯的 && 把期末考砸的 Cansult