//失踪人口回归系列

1. 题目

传送门=￣ω￣=

2. 题解

没想到一个月没摸过 C++居然 1A 了（C++是什么？俄文吗？）

思路很简单啦，单调栈找出所有的有序对。

维护一个单调递减的栈

对于当前元素，如果栈顶元素小于（或等于）它，那么它们就是一对合法有序对，然后把栈顶元素弹出。如果栈顶比当前元素大的话也说明它们是一对，这种情况下把当前元素丢到栈里就行了。

这样点对的个数不超过 $2n$个

问题就变成了二维数点问题，主席树上就行啦。

代码：

#include <bits/stdc++.h>

#define NS (300005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, tp, A[NS], root[NS], sz;

struct N {int d, l, r;} e[NS * 40];

void Add(int p, int L, int R, int& x, int y)
{
    x = ++sz, e[x] = e[y], e[x].d++;
    if (L == R) return;
    int Mid = (L + R) >> 1;
    if (p <= Mid) Add(p, L, Mid, e[x].l, e[y].l);
    else Add(p, Mid + 1, R, e[x].r, e[y].r);
}

int Query(int l, int r, int L, int R, int a)
{
    if (!a) return 0;
    if (l <= L && R <= r) return e[a].d;
    int Mid = (L + R) >> 1, res = 0;
    if (l <= Mid) res = Query(l, r, L, Mid, e[a].l);
    if (r > Mid) res += Query(l, r, Mid + 1, R, e[a].r);
    return res;
}

PII st[NS];

vector<int> g[NS];

void Init()
{
    int top = 0;
    for (int i = 1; i <= n; i += 1)
    {
        bool flag = 0;
        while (top && st[top].FIR <= A[i])
        {
            g[st[top].SEC].push_back(i);
            if (st[top].FIR == A[i]) flag = 1;
            top--;
        }
        if (!flag && top) g[st[top].SEC].push_back(i);
        st[++top].FIR = A[i], st[top].SEC = i;
    }
    for (int i = 1; i <= n; i += 1)
    {
        root[i] = root[i - 1];
        for (int j = 0; j < g[i].size(); j += 1)
            Add(g[i][j], 1, n, root[i], root[i]);
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(tp);
    for (int i = 1; i <= n; i += 1) IN(A[i]);
    Init();
    for (int i = 1, l, r, ans = 0; i <= m; i += 1)
    {
        IN(l), IN(r);
        if (tp) l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
        if (l > r) swap(l, r);
        ans = Query(l, r, 1, n, root[r]) - Query(l, r, 1, n, root[l - 1]);
        printf("%d\n", ans);
    }
    return 0;
}