如何在网站开发客户,公司注册地址和经营地址不一致,长春网络建站模板,北京小程序制作卓越华网天下正题 题目大意 nnn个连续的数#xff0c;第iii个为hih_ihi。有操作
给出一个HHH#xff0c;询问大于等于HHH的数能组成多少个联通块修改一个位置的数。 解题思路
考虑计算连通块尾的数量#xff0c;我们可以发现一个位置作为联通块尾部当且仅当hi≥Hh_i\geq Hhi≥H且h…正题 题目大意
nnn个连续的数第iii个为hih_ihi。有操作
给出一个HHH询问大于等于HHH的数能组成多少个联通块修改一个位置的数。 解题思路
考虑计算连通块尾的数量我们可以发现一个位置作为联通块尾部当且仅当hi≥Hh_i\geq Hhi≥H且hi1Hh_{i1}Hhi1H。
也就是如果hi1hih_{i1}h_ihi1hi那hih_ihi能作为尾部的情况当且仅当H∈[hi11,hi]H\in[h_{i1}1,h_i]H∈[hi11,hi]。用树状数组维护每个位置的贡献区间即可。
时间复杂度O((nq)logn)O(\ (nq)\ \log n)O( (nq) logn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N2e610,S2e61;
int n,m,t[N],a[N];
void Change(int x,int w){x;while(xS){t[x]w;xlowbit(x);}return;
}
int Ask(int x){int ans0;x;while(x){anst[x];x-lowbit(x);}return ans;
}
int main()
{freopen(patrick.in,r,stdin);freopen(patrick.out,w,stdout);scanf(%d%d,n,m);a[n1]0;for(int i1;in;i)scanf(%d,a[i]);for(int i0;in;i)if(a[i]a[i1]){Change(a[i1],1);Change(a[i],-1);}int last0;for(int i1;im;i){char op[5];int x,y;scanf(%s,op);if(op[0]Q){scanf(%d,x);x^last;x--;printf(%d\n,lastAsk(x));}else{scanf(%d%d,x,y);x^last;y^last; if(a[x-1]a[x])Change(a[x],-1),Change(a[x-1],1);if(a[x]a[x1])Change(a[x],1),Change(a[x1],-1);a[x]y;if(a[x-1]a[x])Change(a[x],1),Change(a[x-1],-1);if(a[x]a[x1])Change(a[x],-1),Change(a[x1],1);}}
}
