登录—专业IT笔试面试备考平台_牛客网 2020江西省H
主要是询问
答案是
找到小于a[x]的第一个位置(1,x-1) L
找到小于a[x]的第一个位置(x+1,n) R
有单调性，范围越大，最小值越小，因此可以二分
时间复杂度 600ms
// Problem: Sequence
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/8827/H
// Memory Limit: 262144 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//线段树
#include<iostream>
using namespace std;
const int N=1e5+9;
int a[N];
struct SEG{#define INF (1<<31)#define ll long long#define tl(id) (id<<1)#define tr(id) (id<<1|1)#define li inlinestruct node{int l,r;ll mn,index;}seg[N<<2];li bool inrange(int L,int R,int l,int r){return l<=L && R<=r;}li bool outofrange(int L,int R,int l,int r){return L>r || R<l;}li void pushup(node &id,node &l,node &r){id.mn=min(l.mn,r.mn);}li void pushup(const int id){pushup(seg[id],seg[tl(id)],seg[tr(id)]);}li void build(const int id,int l,int r){seg[id]={l,r};if(l==r){seg[id].mn=a[l];seg[id].index=l;return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li auto query(int id,int l,int r){//一开始想直接找位置所以写了一个结构体...if(inrange(seg[id].l,seg[id].r,l,r)){return seg[id];}else{int mid=(seg[id].l+seg[id].r)>>1;if(mid>=r){return query(tl(id),l,r);}else if(mid<l){return query(tr(id),l,r);}else{node res;node left=query(tl(id),l,mid);node right=query(tr(id),mid+1,r);pushup(res,left,right);return res;}}}li void update(int id,int l,int r,int pos,ll v){if(l==r){seg[id].mn=v;return;}int mid=(l+r)>>1;if(mid>=pos){update(tl(id),l,mid,pos,v);}else{update(tr(id),mid+1,r,pos,v);}pushup(id);}li ll ask(int id,int l,int r,int pos){if(l==r){return seg[id].mn;}int mid=(l+r)>>1;if(mid>=pos){return ask(tl(id),l,mid,pos);}else{return ask(tr(id),mid+1,r,pos);}}
}t;
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}t.build(1,1,n);for(int i=1;i<=m;i++){int opt;cin>>opt;if(opt==1){int x,y;cin>>x>>y;t.update(1,1,n,x,y);}else{ll x;cin>>x;int val=t.ask(1,1,n,x);int l=x;int r=n;ll R=0;while(l<=r){int mid=(l+r)>>1;if(t.query(1,x,mid).mn==val){l=mid+1;R=mid;}else{r=mid-1;}}ll L=0;l=1;r=x;while(l<=r){int mid=(l+r)>>1;if(t.query(1,mid,x).mn==val){r=mid-1;L=mid;}else{l=mid+1;}}// cout<<L<<" "<<R<<'\n';ll ans=(x-L+1)*(R-x+1);cout<<ans<<'\n';}}
}可以把二分放到线段树里，时间复杂度 300ms
// Problem: Sequence
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/8827/H
// Memory Limit: 262144 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//线段树
#include<iostream>
using namespace std;
const int N=1e5+9;
int a[N];
int n,m;
struct SEG{#define INF (1<<31)#define ll long long#define tl(id) (id<<1)#define tr(id) (id<<1|1)#define li inlinestruct node{int l,r;ll mn,index;}seg[N<<2];li bool inrange(int L,int R,int l,int r){return l<=L && R<=r;}li bool outofrange(int L,int R,int l,int r){return L>r || R<l;}li void pushup(node &id,node &l,node &r){id.mn=min(l.mn,r.mn);}li void pushup(const int id){pushup(seg[id],seg[tl(id)],seg[tr(id)]);}li void build(const int id,int l,int r){seg[id]={l,r};if(l==r){seg[id].mn=a[l];seg[id].index=l;return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li auto query(int id,int l,int r){if(inrange(seg[id].l,seg[id].r,l,r)){return seg[id];}else{int mid=(seg[id].l+seg[id].r)>>1;if(mid>=r){return query(tl(id),l,r);}else if(mid<l){return query(tr(id),l,r);}else{node res;node left=query(tl(id),l,mid);node right=query(tr(id),mid+1,r);pushup(res,left,right);return res;}}}li void update(int id,int l,int r,int pos,ll v){if(l==r){seg[id].mn=v;return;}int mid=(l+r)>>1;if(mid>=pos){update(tl(id),l,mid,pos,v);}else{update(tr(id),mid+1,r,pos,v);}pushup(id);}li ll ask(int id,int l,int r,int pos){if(l==r){return seg[id].mn;}int mid=(l+r)>>1;if(mid>=pos){return ask(tl(id),l,mid,pos);}else{return ask(tr(id),mid+1,r,pos);}}li ll lquery(int id,int l,int r,int pos,int v){if(l==r){return l;}int mid=(l+r)>>1;ll ans=l;if(seg[tr(id)].mn<v && mid<pos){ans=lquery(tr(id),mid+1,r,pos,v);if(ask(1,1,n,ans)<v){return ans;}else{ans=l;}}if(seg[tl(id)].mn<v){ans=lquery(tl(id),l,mid,pos,v);}return ans;}li ll rquery(int id,int l,int r,int pos,int v){if(l==r){return l;}int mid=(l+r)>>1;ll ans=r;if(seg[tl(id)].mn<v && mid>=pos){ans=rquery(tl(id),l,mid,pos,v);if(ask(1,1,n,ans)<v){return ans;}else{ans=r;}}if(seg[tr(id)].mn<v){ans=rquery(tr(id),mid+1,r,pos,v);}return ans;}
}t;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}t.build(1,1,n);for(int i=1;i<=m;i++){int opt;cin>>opt;if(opt==1){int x,y;cin>>x>>y;t.update(1,1,n,x,y);}else{ll x;cin>>x;int val=t.ask(1,1,n,x);ll L=t.lquery(1,1,n,x-1,val);ll R=t.rquery(1,1,n,x+1,val);// cout<<L<<" "<<R<<'\n';int val1=t.ask(1,1,n,L);int val2=t.ask(1,1,n,R);// cout<<val1<<" "<<val2<<'\n';if(val1<val){L++;}if(val2<val){R--;}// cout<<L<<" "<<R<<'\n';ll ans=(x-L+1)*(R-x+1);cout<<ans<<'\n';}}
}
