本文共 2527 字，大约阅读时间需要 8 分钟。

题目

题解

题意

给一数组$a$，记录下每个连续子数组的最大值

分析

既然要求子数组最大值

Code

#include
   
    #include
    
     #include
     
      using namespace std;int n,m,i,l,r,mid,bj;long long s1,s2,x,ans,ans1,ans2,pre[100005],suf[100005],tree[400005];char ch;struct node{   	long long val,sum;}a[100005];bool cmp(node x,node y){   	return x.val
      
       >1;	biuld(now<<1,l,mid);	biuld(now<<1|1,mid+1,r);	tree[now]=max(tree[now<<1],tree[now<<1|1]);}long long query(int now,int l,int r,int p,int q){   	if (l>=p&&r<=q) return tree[now];	int mid=(l+r)>>1;	long long res;	res=0;	if (p<=mid) res=max(res,query(now<<1,l,mid,p,q));	if (q>mid) res=max(res,query(now<<1|1,mid+1,r,p,q));	return res;}int main(){   	freopen("jxthree.in","r",stdin);	freopen("jxthree.out","w",stdout);	scanf("%d%d",&n,&m);	for (i=1;i<=n;i++)		scanf("%lld",&a[i].val);	biuld(1,1,n);	for (i=1;i<=n;i++)	{   		l=1;		r=i-1;		s1=i;		s2=i;		while (l<=r)		{   			mid=(l+r)>>1;			if (query(1,1,n,mid,i-1)
       
        >1;			if (query(1,1,n,i+1,mid)<=a[i].val)			{   				s2=mid;				l=mid+1;			}			else r=mid-1;		}		a[i].sum=(long long)(i-s1+1)*(long long)(s2-i+1);	}	sort(a+1,a+n+1,cmp);	for (i=1;i<=n;i++)		pre[i]=pre[i-1]+a[i].sum;	for (i=n;i>=1;i--)		suf[i]=suf[i+1]+a[i].sum;	for (i=1;i<=m;i++)	{   		ch=getchar();		while (ch!='>'&&ch!='='&&ch!='<') ch=getchar();		if (ch=='<') bj=1;		if (ch=='=') bj=2;		if (ch=='>') bj=3;		scanf("%lld",&x);		ans=0;		ans1=0;		ans2=0;		if (bj==1)		{   			l=1;			r=n;			while (l<=r)			{   				mid=(l+r)>>1;				if (a[mid].val
        
         >1; if (a[mid].val<=x) { ans1=mid; l=mid+1; } else r=mid-1; } l=1; r=n; while (l<=r) { mid=(l+r)>>1; if (a[mid].val
         
          >1; if (a[mid].val>x) { ans=mid; r=mid-1; } else l=mid+1; } printf("%lld\n",suf[ans]); } } fclose(stdin); fclose(stdout); return 0;}