Codeforces Round 530 (Div. 1)

https://codeforces.com/contest/1098

前面有些很没意思很简单的题我就不写题解了（

C. Construct a tree

首先如果$s<2n-1$或者$s>\frac{n(n+1)}{2}$就无解。

否则可以按照以下构造出合法方案。

首先把子树大小和转换成每个点的深度之和，显然这俩等价。

那么最大的情况就是一条链，然后我们每次把一个叶子挂在他父亲深度减一的任意一个点上，那么答案恰好减一。

注意到显然度数越大最小值就越小，而最大值是固定的，所以我们二分度数，假设为$k$，此时最小值就是$1+k+k^2+\cdots+(n-k^x)(x+1)$，$x$是最大的$k^x\leqslant n$的值。

那么我们可以$O(\log n)$的判断，复杂度就是$O(n+\log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,s,fa[maxn],d[maxn];
vector<int > t[maxn];
 
int calc(int k) {
    int sum=1,res=1,now=1,dep=1;
    while(res+now*k<=n) 
        now*=k,dep++,res+=now,sum+=dep*now;
    dep++;sum+=dep*(n-res);
    return sum;
}
 
signed main() {
    read(n),read(s);
    int l=1,r=n-1,k=n-1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(calc(mid)<=s) r=mid-1,k=mid;
        else l=mid+1;
    }
    int sum=n*(n+1)/2;
    if(sum<s||2*n-1>s) return puts("No"),0;puts("Yes");
    for(int i=2;i<=n;i++) fa[i]=i-1,d[i-1]=1;
    for(int i=1;i<=n;i++) t[i].pb(i);int now=1;
    for(int i=n;i;i--) {
        if(d[t[now].back()]==k) t[now].pop_back();
        if(!t[now].size()) now++;//printf("%d %d\n",i,now);
        if(sum-(i-now-1)<=s) {
            fa[i]=i-(sum-s)-1;
            break;
        }fa[i]=t[now].back(),d[t[now].back()]++;
        t[now+1].pb(i),d[i]=0;sum-=i-now-1;
    }
    for(int i=2;i<=n;i++) printf("%lld ",fa[i]);puts("");
    return 0;
}

D. Eels

看了题解才会的。。大神题。

首先我们排序，我们定义$x$是好的当且仅当$2\sum_{i=1}^{x-1}a_i<a_x$，也就是说不可能有一个比$x$小的鱼和$x$贡献答案。

为了最大化答案，我们有一个这样的贪心策略：每次选两个最小的合并，假设当前合并的是$a,b$，假设$a2a$，说明$b$是一条好的鱼，因为$a$会和所有小的合并，所以假设有$t$条好鱼，这样贪心的答案就是$n-t$。

而我们显然不能得到更优的答案，因为所有好鱼都会减少一个答案，也就是说答案最大为$n-t$。

所以我们现在要维护这个$t$，我们把值域分割成若干块：$[1,2),[2,4),[4,8),\cdots,[2^{30},2^{31})$。

显然每个块内至多只有一个好鱼，并且是最小的那个。

所以随便拿个东西暴力维护下就好了，复杂度$O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int ans,pw[maxn],sum[maxn],cnt,mn[50];
multiset<int > r[50];
 
void insert(int x) {
    int p=0;cnt++;
    while(x>=pw[p+1]) p++;
    ans-=sum[p-1]*2<mn[p];
    r[p].insert(x);mn[p]=*r[p].begin();
    ans+=sum[p-1]*2<mn[p];
    for(int i=p;i<=30;i++) {
        ans-=sum[i]*2<mn[i+1];
        sum[i]+=x;
        ans+=sum[i]*2<mn[i+1];
    }
}
 
void del(int x) {
    int p=0;cnt--;
    while(x>=pw[p+1]) p++;
    ans-=sum[p-1]*2<mn[p];
    multiset<int > :: iterator t=r[p].find(x);r[p].erase(t);
    mn[p]=*r[p].begin();
    ans+=sum[p-1]*2<mn[p];
    for(int i=p;i<=30;i++) {
        ans-=sum[i]*2<mn[i+1];
        sum[i]-=x;
        ans+=sum[i]*2<mn[i+1];
    }
}
 
signed main() {
    pw[0]=1;
    for(int i=1;i<=40;i++) pw[i]=pw[i-1]<<1;
    int q;read(q);
    while(q--) {
        char op;int x;scanf("%c",&op),read(x);
        if(op=='+') insert(x);
        else del(x);write(cnt-ans);
    }
    return 0;
}

E. Fedya the Potter

强行把一堆东西套一起的题。。。因为这题我还去学了一波类欧几里得算法，学习笔记：类欧几里得算法。

首先注意到$b$数组不一样的数只有$O(n\log n)$个，因为考虑枚举$a$的左端点，拿右端点往后扫，$\gcd$每次要么不变要么至少除掉一个因数，所以只会减少$O(\log n)$次。

所以可以拿二分+$\rm rmq$求出$b$数组。

然后我们二分答案，现在就是要求多少个区间和小于等于二分出来的答案。

然后这个$b$数组现在是很多块，每块内的值相同，所以我们一个一个块的进行$\rm two_pointer$，现在只要求左端点在$a$块，右端点在$b$块有多少种情况符合条件就行了，假设$a$块值为$x$，$b$为$y$，二分出来的答案为$s$，两个块中间的总和为$t$。

也就是：

$$\sum_{i=1}^{a}\sum_{j=1}^{b}[ix+jy+t\leqslant s]$$

假设$f(a,b,c)$表示$ax+by\leqslant c$的正整数解的个数，那么上式容斥一下就是：

$$f(x,y,s-a-b)-f(x,y,s-(a+1)x)-f(x,y,s-(b+1)y)+\\f(x,y,s-(a+1)x-(b+1)y)$$

至于$f$，我们可以得到一个很显然的式子：

$$f(a,b,c)=\sum_{i=0}^{c/a}(1+\lfloor\frac{c-ia}{b}\rfloor)$$

这是枚举$a$的使用次数，但是这样$a$的系数是负的，我们可以枚举$i$表示$a$用了$c/a-i$次，那么式子就是：

$$\begin{align} f(a,b,c)&=c/a+1+\sum_{i=0}^{c/a}\lfloor\frac{c-(c/a-i)a}{b}\rfloor\\ f(a,b,c)&=c/a+1+\sum_{i=0}^{c/a}\lfloor\frac{ai+c\bmod a}{b}\rfloor \end{align}$$

直接上类欧几里得就好了。

代码挺难写的。。细节很多，复杂度$O(n\log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int v[maxn],cnt,n;
struct _data {int x;ll t;}t[maxn];
 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)/2)
 
struct ST_table {
    int f[50050][16],lg[50050];
 
    void build() {
        for(int i=1;i<=n;i++) f[i][0]=v[i];
        for(int j=1;j<=15;j++)
            for(int i=1;i<=n;i++)
                f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    }
 
    int query(int x,int y) {
        int t=lg[y-x+1];
        return __gcd(f[x][t],f[y-(1<<t)+1][t]);
    }
}T;
 
void prepare() {
    map<int,ll > s;
    T.build();
    for(int i=1;i<=n;i++) {
        int p=i,now=v[i];
        while(p<=n) {
            int l=p,r=n,pre=p;
            while(l<=r)
                if(T.query(i,mid)==now) p=mid,l=mid+1;
                else r=mid-1;
            s[now]+=p-pre+1;
            p++;now=__gcd(now,v[p]);
        }
    }
    for(map<int,ll > :: iterator i=s.begin();i!=s.end();i++)
        t[++cnt]=(_data){i->fr,i->sc};
}
 
ll f(ll a,ll b,ll c,ll n) {
    if(n<0) return 0;
    if(!a) return (n+1)*(b/c);
    if(a>=c||b>=c) return f(a%c,b%c,c,n)+n*(n+1)/2*(a/c)+(n+1)*(b/c);
    ll m=(n*a+b)/c;
    return n*m-f(c,c-b-1,a,m-1);
}
 
ll sum[maxn],ct[maxn];
 
ll s(ll a,ll b,ll c) {
    if(c<0) return 0;
    int x=f(a,c%a,b,c/a)+c/a+1;
    return x;
}
 
ll calc(ll a,ll b,ll md) {
    if(a>=b) return 0;
    ll ss=md-(ct[b-1]-ct[a]),x=t[a].x,y=t[b].x;ss-=x,ss-=y;
    if((t[a].t-1)*x+(t[b].t-1)*y<=ss) return t[a].t*t[b].t;
    return s(x,y,ss)-s(x,y,ss-t[a].t*x)-s(x,y,ss-t[b].t*y)+s(x,y,ss-t[a].t*x-t[b].t*y);
}
 
ll get(ll x) {
    ll p=1,ans=0;
    for(int i=1;i<=cnt;i++) {
        ll w=min(x/t[i].x,t[i].t);
        ans+=(t[i].t+1)*w-w*(w+1)/2;
    }
    for(int i=1;i<=cnt;i++) {
        if(p>i+1) ans+=1ll*t[i].t*(sum[p-1]-sum[i]);
        while(p<=cnt&&ct[p]-ct[i]<=x) ans+=calc(i,p,x),p++;
        if(p<=cnt) ans+=calc(i,p,x);
    }
    return ans;
}
 
signed main() {
    int st=clock();
    read(n);
    for(int i=1;i<=n;i++) read(v[i]);
    prepare();
    for(int i=1;i<=cnt;i++) sum[i]=sum[i-1]+t[i].t;
    for(int i=1;i<=cnt;i++) ct[i]=ct[i-1]+1ll*t[i].t*t[i].x;
    ll l=1,r=ct[cnt]+1,w=1ll*n*(n+1)/2;
    w=w*(w+1)/2;w=(w+1)/2;
    while(l<r) {
        if(get(mid)<w) l=mid+1;
        else r=mid;
    }write(l);
    cerr<<(lf)(clock()-st)/1e3<<endl;
    return 0;
}