3956: Count
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 173 Solved: 99
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
3 2 0
2 1 2
1 1
1 3
2 1 2
1 1
1 3
Sample Output
0
3
3
HINT
M,N<=3*10^5,Ai<=10^9
Source
CH Round#64 MFOI杯水题欢乐赛day1 By Gromah
Solution
思路有了之后，比较好写的一道题
首先我们计算以每个点为区间左端的答案，以及区间右端的答案，利用单调栈可以$O(N)$的处理出来
同样可以预处理出它们的前缀和
然后我们考虑一次询问，假如我们得到$[l,r]$中的最大值位置mp
那么我们的答案，相当于是询问区间$[l,mp]$中所有点作为左端的答案与$[mp+1,r]$中所有点作为右端点的答案
那么显然前缀和计算就好，至于查询最大位置？线段树/ST表都可以处理
这里采用ST表，总复杂度是$O(NlogN+M)$
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 300010
int N,M,T,h[MAXN]; long long last;
inline int GetL (int x,int y) {if (T) return min((x+last-)%N,(y+last-)%N)+; else return min(x,y);}
inline int GetR (int x,int y) {if (T) return max((x+last-)%N,(y+last-)%N)+; else return max(x,y);}
int log2[MAXN],dp[MAXN][];
inline int MaxPos(int x,int y) {return h[x]>h[y]? x:y;}
void ST()
{
log2[]=-;
for (int i=; i<=N; i++)
if (i&(i-)) log2[i]=log2[i-];
else log2[i]=log2[i-]+;
for (int i=; i<=N; i++) dp[i][]=i;
for (int j=; (<<j)<=N; j++)
for (int i=; i+(<<j)-<=N; i++)
dp[i][j]=MaxPos(dp[i][j-],dp[i+(<<(j-))][j-]);
}
inline int RMQ(int l,int r)
{
int tmp=log2[r-l+];
return MaxPos(dp[l][tmp],dp[r-(<<tmp)+][tmp]);
}
long long AnsL[MAXN],AnsR[MAXN];
int stack[MAXN],top;
void PreWork()
{
top=;
stack[++top]=h[];
for (int i=; i<=N; i++)
{
while (top && h[i]>stack[top]) AnsL[i]++,top--;
if (top) AnsL[i]++;
while (top && h[i]>=stack[top]) top--;
stack[++top]=h[i];
}
top=;
stack[++top]=h[N];
for (int i=N-; i>=; i--)
{
while (top && h[i]>stack[top]) AnsR[i]++,top--;
if (top) AnsR[i]++;
while (top && h[i]>=stack[top]) top--;
stack[++top]=h[i];
}
for (int i=; i<=N; i++) AnsL[i]+=AnsL[i-],AnsR[i]+=AnsR[i-];
ST();
}
inline void Solve(int L,int R)
{
int maxp=RMQ(L,R);
printf("%lld\n",last=AnsR[maxp-]-AnsR[L-]+AnsL[R]-AnsL[maxp]);
}
int main()
{
N=read(),M=read(),T=read();
for (int i=; i<=N; i++) h[i]=read();
PreWork();
while (M--)
{
int x=read(),y=read();
int L=GetL(x,y),R=GetR(x,y);
Solve(L,R);
}
return ;
}