首页 > 代码库 > bzoj 3956: Count
bzoj 3956: Count
3956: Count
Description
.png)
Input
.png)
Output
.png)
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
题解：
性质很妙的一道题。
首先可以发现这个所有的点队数是很小的，考虑以把一个点作为两个端点中较小的一个，那么另一个端点肯定是向左向右第一个大于等于它的点，这是很显然的。。。。
我们可以先用单调栈把这些点对都预处理出来。
再考虑如何求区间[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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。