房产网站建设方案项目书,博客网站开发技术,网络营销策略,做网站回答正题
题目连接:https://codeforces.com/contest/1556/problem/E 题目大意
两个长度为nnn的序列a,ba,ba,b#xff0c;qqq次询问一个区间[l,r][l,r][l,r]。
在这个区间中你每次可以选择一个长度为偶数的下标递增的序列#xff0c;让奇数位置的aaa加一#xff0c;偶数位置的…正题
题目连接:https://codeforces.com/contest/1556/problem/E 题目大意
两个长度为nnn的序列a,ba,ba,bqqq次询问一个区间[l,r][l,r][l,r]。
在这个区间中你每次可以选择一个长度为偶数的下标递增的序列让奇数位置的aaa加一偶数位置的bbb加111。
求最少操作次数使得每个aibia_ib_iaibi。
n,q≤105n,q\leq 10^5n,q≤105 解题思路
视为一个减一个加的话令xibi−aix_ib_i-a_ixibi−ai这样就变成了每个需要加/减的次数。
可以视为每个减后面需要跟一个加加前面需要跟一个减而加后面可以免费跟一个减。
把需要减的看成(((需要加的看成)))的话就能看出来无论什么区间的情况下每个(((都是和同一个)))匹配或者无法匹配。
离线询问开两个栈分别存(((和)))然后一个树状数组用来记录每个位置需要的左端点位置上限另一个记录每个左端点对应的权值即可。
时间复杂度O(nlognqlogn)O(n\log nq\log n)O(nlognqlogn) code
#includecstdio
#includecstring
#includealgorithm
#includestack
#define ll long long
#define lowbit(x) (x-x)
using namespace std;
const ll N1e510;
struct node{ll l,r,id;
}q[N];
ll n,m,a[N],c[N],d[N],t[N],s[N],ans[N];
stackint S,T;
void Change(ll x,ll val){xn-x1;while(xn){t[x]val;xlowbit(x);}return;
}
ll Ask(ll x){ll ans0;xn-x1;while(x){anst[x];x-lowbit(x);}return ans;
}
void Dhange(ll x,ll val){xn-x1;while(xn){s[x]min(s[x],val);xlowbit(x);}return;
}
ll Bsk(ll x){ll ansn1;xn-x1;while(x){ansmin(ans,s[x]);x-lowbit(x);}return ans;
}
bool cmp(node x,node y)
{return x.ry.r;}
signed main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1,x;in;i)scanf(%lld,x),a[i]x-a[i];for(ll i1;im;i)scanf(%lld%lld,q[i].l,q[i].r),q[i].idi;sort(q1,q1m,cmp);memset(s,0x3f,sizeof(s));c[0]1e18;S.push(0);for(ll i1,z1;in;i){if(a[i]0){ll xa[i];Change(i,x);while(!T.empty()d[T.top()]x)x-d[T.top()],Change(T.top(),-d[T.top()]),T.pop();if(!T.empty())d[T.top()]-x,Change(T.top(),-x);S.push(i);c[i]a[i];}if(a[i]0){ll x-a[i];while(c[S.top()]x)x-c[S.top()],S.pop();c[S.top()]-x;Dhange(i,S.top());if(c[S.top()]0)S.pop();T.push(i);d[i]-a[i];}while(zmq[z].ri){if(q[z].lS.top()||q[z].lBsk(q[z].l))ans[q[z].id]-1;else ans[q[z].id]Ask(q[z].l);z;}if(zm)break;}for(ll i1;im;i)printf(%lld\n,ans[i]);return 0;
}
