首页 > 代码库 > bzoj 3956: Count

bzoj 3956: Count

2024-08-20 20:53:41   224人阅读

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;}

 

　　

 

bzoj 3956: Count


联系
我们