1 条题解
-
0
前言
五发罚时害死人!
莫队平衡复杂度差不多得了!
题意
给你两个长度为 的自然数序列, 和 。
规定在 范围内的平衡操作,是指自由选出一段长度为偶数 的整数序列 ,使得 ,然后令 位置的 加一,令 位置的 加一。
次询问,每次询问给你一段区间 ,问你至少做几次该区间内的平衡操作,可以使 间所有位置满足 ,无解输出 。询问独立。
数据范围:,,,。
思路
转化题意
记 ,则题意转化为:
给你一个长度为 的整数序列 。
规定在 范围内的平衡操作,是指自由选出一段长度为偶数 的整数序列 ,使得 ,然后令 位置的 加一,令 位置的 减一。
次询问,每次询问给你一段区间 ,问你至少做几次该区间内的平衡操作,可以使 间所有位置满足 ,无解输出 。询问独立。
数据范围:,,,。
分析
有了 数组还不够,我们依旧需要一个条件来判断是否有解。
I.显然若区间内 数组的和不是 ,则必然无解。
II.同时,若区间内存在前缀和为正数 ,则亦无解。
证明:
由每次操作对前缀和的影响一定不减且最多加一可得。
因为序列 $D:\big<0,\dots,0,1,0,\dots,0,-1,0,\dots,0,1,0,\dots,0,-1,0,\dots\big>$ 序列的前缀和序列 中每一项不是 就是 ,由前缀和的线性性即 ,这个 必然不减而无法变为 。0,\dots,0,1,0,\dots,0,-1,0,\dots,0,1,0,\dots,0,-1,0,\dots\big>
除去这两种情况,剩下的情况都容易构造方案,即利用上述论述中操作对前缀和的影响($\sum D:\big<0,0,0,1,1,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,0,\dots\big>$)来构造,构造方案略。0,0,0,1,1,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,0,\dots\big>
III.不难发现答案即区间内最大的前缀和的相反数,或者说区间内最小前缀和的相反数,即 ,证明由构造方案与证明下界两部分组成,此处略去。
考虑怎么快速判断。
对情况 I,直接维护全局前缀和数组即可。
对情况 II,等价于区间内最大前缀和为正,这个可以转化成序列上两个前缀和的差,于是就要维护全局前缀和数组,要求查询区间 ,用 ST 表即可。
对情况 III,等价于求区间内最小前缀和,这个也可以转化成序列上两个前缀和的差,于是就要维护全局前缀和数组,要求查询区间 ,用 ST 表即可。
复杂度 。
由于赛前在练习莫队,于是赛场上没有想到 ST 表,胡了一个奇妙的平衡复杂度莫队做法,大致方法类似,就是将全局前缀和数组先离散化再插入一个值域分块里面,反正是个非常谔谔的做法。
复杂度 。
结果拿了 发罚时,写了亿年才过(
Code
给出平衡复杂度莫队版的代码。
// Problem: E. Equilibrium // Contest: Codeforces - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1556/problem/E // Memory Limit: 256 MB // Time Limit: 2000 ms #include <algorithm> #include <math.h> #include <set> #include <map> #include <stdio.h> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;} template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;} template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;} template<typename T>T lowbit(T n){return n&-n;} template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;} template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;} template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;} template<const uint Sqrt=1500> struct Block { uint A[Sqrt*Sqrt],B[Sqrt]; Block() { for(uint i=0;i<Sqrt*Sqrt;i++)A[i]=0; for(uint i=0;i<Sqrt;i++)B[i]=0; } voi insert(uint v){A[v]++,B[v/Sqrt]++;} voi erase(uint v){A[v]--,B[v/Sqrt]--;} uint findmin() { for(uint i=0;i<Sqrt;i++)if(B[i]) for(uint j=0;j<Sqrt;j++)if(A[i*Sqrt+j])return i*Sqrt+j; return-1; } uint findmax() { for(uint i=Sqrt-1;~i;i--)if(B[i]) for(uint j=Sqrt-1;~j;j--)if(A[i*Sqrt+j])return i*Sqrt+j; return-1; } }; Block<>B; uint Siz; struct ques{uint l,r,t;llt ans;}; bol cmp1(const ques&a,const ques&b){return(a.l/Siz==b.l/Siz)?(((a.l/Siz)&1)?b.r<a.r:(a.r<b.r)):(a.l<b.l);} bol cmp2(const ques&a,const ques&b){return a.t<b.t;} llt A[100005],_S[100005],User[100005]; uint S[100005]; ques Q[100005]; uint l,r; std::set<llt>Set; std::map<llt,uint>Map; llt sgn(llt v){return(v>0)?1:(v?-1:0);} voi insert(uint m){B.insert(S[m+1]);} voi erase(uint m){B.erase(S[m+1]);} int main() { uint n,m;llt v; scanf("%u%u",&n,&m),Siz=sqrt(n); for(uint i=0;i<n;i++)scanf("%lld",A+i); for(uint i=0;i<n;i++)scanf("%lld",&v),Set.insert(_S[i+1]=_S[i]+(A[i]-=v)); Set.insert(0); while(!Set.empty())User[Map[*Set.rbegin()]=Set.size()]=*Set.rbegin(),Set.erase(*Set.rbegin()); for(uint i=0;i<=n;i++)S[i]=Map[_S[i]]; for(uint i=0;i<m;i++)scanf("%u%u",&Q[i].l,&Q[i].r),Q[i].l--,Q[i].t=i; std::sort(Q,Q+m,cmp1),l=r=0; for(uint i=0;i<m;i++) { ques&qs=Q[i]; while(l>qs.l)insert(l-1),l--; while(r<qs.r)insert(r),r++; while(l<qs.l)erase(l),l++; while(r>qs.r)erase(r-1),r--; qs.ans=(B.findmax()==S[l]&&S[r]==S[l])?User[S[l]]-User[B.findmin()]:-1; } std::sort(Q,Q+m,cmp2); for(uint i=0;i<m;i++)printf("%lld\n",Q[i].ans); return 0; }
- 1
信息
- ID
- 7273
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者