青浦工厂网站建设,做网销做什么网站,网站建设怎么寻找客户,网络正能量你懂我意思的2023牛客暑期多校训练营8-C Clamped Sequence II
https://ac.nowcoder.com/acm/contest/57362/C 文章目录 2023牛客暑期多校训练营8-C Clamped Sequence II题意解题思路代码 题意 解题思路
先考虑不加紧密度的情况#xff0c;要支持单点修改#xff0c;整体查询#xff0…2023牛客暑期多校训练营8-C Clamped Sequence II
https://ac.nowcoder.com/acm/contest/57362/C 文章目录 2023牛客暑期多校训练营8-C Clamped Sequence II题意解题思路代码 题意 解题思路
先考虑不加紧密度的情况要支持单点修改整体查询可以用值域线段树来求。设 t r e e [ x ] . n u m tree[x].num tree[x].num表示数值在 [ l , r ] [l,r] [l,r]区间的数的个数 t r e e [ x ] . s u m tree[x].sum tree[x].sum表示数值在 [ l , r ] [l,r] [l,r]区间的数的总和 t r e e [ x ] . a n s tree[x].ans tree[x].ans表示数值在 [ l , r ] [l,r] [l,r]区间的数的紧密度结合下图可以求得转移式 n u m x n u m l s o n n u m r s o n s u m x n u m l s o n s u m r s o n a n s x a n s l s o n a n s r s o n s u m r s o n × n u m l s o n − s u m l s o n × n u m r s o n num_xnum_{lson}num_{rson}\\ sum_xnum_{lson}sum_{rson}\\ ans_xans_{lson}ans_{rson}sum_{rson}\times num_{lson}-sum_{lson}\times num_{rson} numxnumlsonnumrsonsumxnumlsonsumrsonansxanslsonansrsonsumrson×numlson−sumlson×numrson 此时我们加入紧凑的设定对于每一对确定的 [ l , r ] [l,r] [l,r]我们都可以算出此时的答案 a n s w e r a n s l , r s u m [ l , r ] × ( n u m [ 1 , l − 1 ] − n u m [ r 1 , n ] ) ( n u m [ 1 , l − 1 ] n u m [ l , r ] ) × n u m [ r 1 , n ] − ( n u m [ r 1 , n ] n u m [ l , r ] ) × n u m [ 1 , l − 1 ] answerans_{l,r}sum_{[l,r]}\times(num_{[1,l-1]}-num_{[r1,n]})(num_{[1,l-1]}num_{[l,r]})\\ \times num_{[r1,n]}-(num_{[r1,n]}num_{[l,r]})\times num_{[1,l-1]} answeransl,rsum[l,r]×(num[1,l−1]−num[r1,n])(num[1,l−1]num[l,r])×num[r1,n]−(num[r1,n]num[l,r])×num[1,l−1] 根据出题人所说该答案是严格单峰的所以可以用三分求解但经过我实践却不太像需要将三分的范围约束在最中间的数 ± d \pm d ±d再加上左右游移 2 ∼ 3 2\sim 3 2∼3个数大致能求出正确答案。
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N1e55,M1e65;
ll n,a[N],b[M],q;
struct node{ll num,l,r;ll sum,ans;node operator (const node a){node t;t.numnuma.num,t.sumsuma.sum;t.ansnum*a.sum-sum*a.numansa.ans;t.ll,t.ra.r;return t;}
};
struct tree{node tr[M2];void build(int res,int l,int r){tr[res].ll,tr[res].rr;if(lr){tr[res].numb[l],tr[res].sumb[l]*l;return;}int midlr1;build(res1,l,mid);build(res1|1,mid1,r);tr[res]tr[res1]tr[res1|1];}void add(int res,int x,ll d){int ltr[res].l,rtr[res].r;if(lrlx){tr[res].sumd*l;tr[res].numd;return;}int midlr1;if(xmid)add(res1,x,d);else add(res1|1,x,d);tr[res]tr[res1]tr[res1|1];return;}node query(int res,int x,int y){if(xy)return node{0,0,0,0,0};int ltr[res].l,rtr[res].r;if(xlyr){return tr[res];}int midlr1;if(ymid)return query(res1,x,y);if(xmid)return query(res1|1,x,y);return query(res1,x,y)query(res1|1,x,y);}int kth(int id,int l,int r,int k){if(lr) return l;int midlr1;if(tr[id1].numk) return kth(id1,l,mid,k);else return kth(id1|1,mid1,r,k-tr[id1].num);}
}t;
ll f(int l,int d){int rld;node pt.query(1,l,r);ll num1p.num,ans1p.ans,sum1p.sum;ll numlt.query(1,1,l-1).num,numrt.query(1,r1,M-1).num;return ans1-numl*(numrnum1)*lnumr*(numlnum1)*rsum1*(numl-numr);
}
ll work(int d){int kt.kth(1,1,M-1,n11);int lmax(1,k-d),rmin(M-1,kd);ll ma0;while(l2r){int mi1(r-l)/3l,mi2r-(r-l)/3;ll ma1f(mi1,d),ma2f(mi2,d);mamax(ma,max(ma1,ma2));if(ma1ma2)rmi2-1;else lmi11;}for(int il;ir;i)mamax(ma,f(i,d));return ma;
}
int main(){ios::sync_with_stdio(false);cinnq;for(int i1;in;i)cina[i],b[a[i]];t.build(1,1,M-1);while(q--){int op;cinop;if(op1){int x,d;cinxd;t.add(1,a[x],-1);t.add(1,d,1);a[x]d;}else{int d;cind;coutwork(d)\n;}}
}
