在网上做企业网站怎么做,溧阳网站建设报价,在线制作diy电子印章,两学一做网站条幅正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/E 题目大意
给出一个nnn的排列#xff0c;求有多少个区间[l,r][l,r][l,r]使得最大值是rrr#xff0c;最小值是lll。 解题思路
首先对于一个位置的值作为左端点和右端点都有一段合法区间#xff08;到左边第一个比…正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/E 题目大意
给出一个nnn的排列求有多少个区间[l,r][l,r][l,r]使得最大值是rrr最小值是lll。 解题思路
首先对于一个位置的值作为左端点和右端点都有一段合法区间到左边第一个比他小的和右边第一个比他大的当右端点时同理。可以用树状数组预处理每个的合法区间
然后对于两个点各作为左右端点需要满足左端点在右端点的合法区间内右端点在左端点的合法区间内。
那么有算法就是对于每个右端点我们在他合法区间的左边压入右边弹出然后指针扫描作为左端点的值进行区间查询即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#define lowbit(x) (x-x)
using namespace std;
const int N1e610;
int n,p[N],la[N],ra[N],lp[N],rp[N],num[N];
vectorint ql[N],qr[N];
long long ans;
struct Tree_Array{int t[N];void Change(int x,int val){while(xn){t[x]max(val,t[x]);xlowbit(x);}return;}int Ask(int x){int ans0;while(x){ansmax(t[x],ans);x-lowbit(x);}return ans;}
}Ta,Tp;
struct tTree_Array{int t[N];void Change(int x,int val){while(xn){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}
}T;
bool cmp(int x,int y)
{return p[x]p[y];}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,p[i]),num[i]i;for(int i1;in;i){la[i]Ta.Ask(p[i]);ra[i]Tp.Ask(n-p[i]1);Ta.Change(p[i],i);Tp.Change(n-p[i]1,i);}memset(Ta.t,0,sizeof(Ta.t));memset(Tp.t,0,sizeof(Tp.t));for(int in;i1;i--){lp[i]n-Ta.Ask(p[i])1;rp[i]n-Tp.Ask(n-p[i]1)1;Ta.Change(p[i],n-i1);Tp.Change(n-p[i]1,n-i1);}for(int i1;in;i)if(p[i]ira[i]p[i]p[i]rp[i]){ql[ra[i]].push_back(i);qr[rp[i]].push_back(i);}sort(num1,num1n,cmp);for(int i0;in;i){int xnum[i];for(int j0;jqr[i].size();j)T.Change(p[qr[i][j]],-1);if(p[x]xla[x]p[x]p[x]lp[x])ansT.Ask(lp[x]-1)-T.Ask(x-1);for(int j0;jql[i].size();j)T.Change(p[ql[i][j]],1);}printf(%lld,ans);
}
