题目

刚开始并没有看懂题意于是痛苦的挣扎了好久

题意是这样的

问\([l,r]\)有多少对\((i,j)\)满足\(a_i\)和\(a_j\)恰好是\(a_i...a_j\)中严格最大的两个数

强制在线

先考虑\(a_j\)是\(a_i...a_j\)严格第二大的那一个

我们可以一个单调栈扫过去找到\(j\)之前第一个大于等于\(a_j\)的，这个位置就是我们要找的\(i\)了

再考虑\(a_j\)是\(a_i...a_j\)最大的那一个

显然如果\(i\)满足\(i<j\)且\(a_j\)是\(a_i\)右边第一个满足\(a_j>=a_i\)的元素就好了

这样的话最终答案显然是\(n\)级别的，不会太大，于是直接用单调栈把这些区间都找出来，每次询问\([l,r]\)完全包含了多个这样的区间就好了

主席树就可以实现

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<set>

#define mp std::make_pair

#define maxn 300005

#define M maxn*42

#define lowbit(x) ((x)&(-x))

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

typedef std::pair<int,int> pii;

std::set<pii> s;

int n,m,q,cnt;

int st[maxn],top,last,rt[maxn];

int a[maxn],L[maxn],R[maxn];

std::vector<int> v[maxn];

int l[M],r[M],d[M];

int change(int pre,int x,int y,int pos)

{

	int root=++cnt;

	d[root]=d[pre]+1;

	if(x==y) return root;

	l[root]=l[pre],r[root]=r[pre];

	int mid=x+y>>1;

	if(pos<=mid) l[root]=change(l[pre],x,mid,pos);

		else r[root]=change(r[pre],mid+1,y,pos);

	return root;

}

int query(int p1,int p2,int x,int y,int k)

{

	if(x==y) return d[p2]-d[p1];

	int mid=x+y>>1;

	if(k<=mid) return query(l[p1],l[p2],x,mid,k)+d[r[p2]]-d[r[p1]];

	return query(r[p1],r[p2],mid+1,y,k);

}

int main()

{

	n=read(),m=read(),q=read();

	for(re int i=1;i<=n;i++) a[i]=read();

	for(re int i=n;i;--i)

	{

		while(top&&a[st[top]]<=a[i]) L[st[top--]]=i;

		st[++top]=i;

	}

	top=0;

	for(re int i=1;i<=n;i++)

	{

		while(top&&a[st[top]]<=a[i]) R[st[top--]]=i;

		st[++top]=i;

	}

	for(re int i=1;i<=n;i++) if(L[i]) s.insert(mp(L[i],i));

	for(re int i=1;i<=n;i++) if(R[i]) s.insert(mp(i,R[i]));

	for(std::set<pii>::iterator i=s.begin();i!=s.end();++i)

	{

		pii t=*i;

		v[t.second].push_back(t.first);

	}

	for(re int i=1;i<=n;i++)

	{

		int now=rt[i-1];

		for(re int j=0;j<v[i].size();j++) now=change(now,1,n,v[i][j]);

		rt[i]=now;

	}

	int x,y;

	while(m--)

	{

		x=read(),y=read();

		if(q) x=(x+last-1)%n,y=(y+last-1)%n,x++,y++;

		if(x>y) std::swap(x,y);

		if(x==y) last=0;

		else last=query(rt[x-1],rt[y],1,n,x);

		printf("%d\n",last);

	}

	return 0;

}