bzoj 3956: Count

3956: Count

Description

Input

Output

Sample Input

3 2 0
2 1 2
1 1
1 3

Sample Output

0
3

HINT

M,N<=3*10^5,Ai<=10^9

Source

CH Round#64 MFOI杯水题欢乐赛day1 By Gromah

题解：

性质很妙的一道题。

首先可以发现这个所有的点队数是很小的，考虑以把一个点作为两个端点中较小的一个，那么另一个端点肯定是向左向右第一个大于等于它的点，这是很显然的。。。。

我们可以先用单调栈把这些点对都预处理出来。

再考虑如何求区间[L,R]内的答案。

设x为[L,R]中最大值的位置。

显然某个端点在区间内的点对是不可能跨越这个点的。

然后就可以前缀和计算答案了。。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<math.h>

using namespace std;

const int N=300005;

struct node

{

    int a,b;

}p[N<<1];

int n,m,T,i,j,x,y,ans,l,r,k,cnt,a[N],g[N],L[N],R[N],Log[N],f[N][25],F[N][25];

inline int Max(int l,int r)

{

    int x=Log[r-l+1];

    if(f[l][x]>f[r-(1<<x)+1][x]) return F[l][x];else return F[r-(1<<x)+1][x];

}

inline void read(int&v)

{

    char c=getchar();v=0;

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

    while(c>='0'&&c<='9') v=v*10+c-'0',c=getchar();

}

int main()

{

    scanf("%d%d%d",&n,&m,&T);

    for(i=1;i<=n;i++) Log[i]=log2(i);

    for(i=1;i<=n;i++) scanf("%d",&a[i]),f[i][0]=a[i],F[i][0]=i;

    for(j=1;(1<<j)<=n;j++)

     for(i=1;i+(1<<j)-1<=n;i++)

    if(f[i][j-1]>f[i+(1<<j-1)][j-1])

    {

        f[i][j]=f[i][j-1];

        F[i][j]=F[i][j-1];

    } else

    {

        f[i][j]=f[i+(1<<j-1)][j-1];

        F[i][j]=F[i+(1<<j-1)][j-1];

    }

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

    {

        while(k>0&&a[i]>a[g[k]]) k--;

        if(g[k]>0)

        {

            p[++cnt].a=g[k];

            p[cnt].b=i;

        }

        g[++k]=i;

    }

    k=0;

    for(i=n;i>=1;i--)

    {

        while(k>0&&a[i]>a[g[k]]) k--;

        if(g[k]>0&&a[i]!=a[g[k]])

        {

            p[++cnt].a=i;

            p[cnt].b=g[k];

        }

        g[++k]=i;

    }

    for(i=1;i<=cnt;i++) L[p[i].a]++,R[p[i].b]++;

    for(i=1;i<=n;i++) L[i]+=L[i-1],R[i]+=R[i-1];

    while(m--)

    {

        read(x),read(y);

        if(T==1) l=(x+ans-1)%n+1,r=(y+ans-1)%n+1;else l=x,r=y;

        if(l>r) swap(l,r);

        int id=Max(l,r);

        ans=L[id-1]-L[l-1]+R[r]-R[id];

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

    }

    return 0;

}

巴特西