Codeforces Round #665 (Div. 2) / contest 1401_IOS

A	B	C	D	E	F
√	√	√	√	√	○

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

int main()
{
    int T=read();
    while(T--)
    {
        int n=read(),k=read();
        if(k<=n) puts((k%2)==(n%2)?"0":"1");
        else printf("%d\n",k-n);
    }

    return 0;
}

B Ternary Sequence

题意：签到题。

思路：贪心地去构造乘积等于 2 以及乘积等于 0 的就行了。

代码：

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

int main()
{
    int T=read();
    while(T--)
    {
        LL x1=read(),y1=read(),z1=read(),x2=read(),y2=read(),z2=read();
        LL ans=0;
        LL t1=min(z1,y2);
        ans+=t1*2;
        z1-=t1; y2-=t1;

        if(z1) t1=min(z1,z2),z1-=t1,z2-=t1;
        if(z1 || !z2) {printf("%lld\n",ans); continue;}
        t1=min(z2,x1);
        z2-=t1; x1-=t1;
        if(!z2) {printf("%lld\n",ans); continue;}
        t1=min(z2,y1);
        ans-=t1*2;
        printf("%lld\n",ans);
    }

    return 0;
}

C Mere Array

题意：给定一个数组 a，对于两个下标 i 和 j，如果 $gcd(a_i,a_j)=min\{a_i\}$ ，那么就可以交换这两个下标对应的数。现在问是否可以通过这种交换，把数组变成单调不减的。

思路：首先把 a 排好序，排好序之后的某个位置如果和原来的位置的数不一样，那么说明原来位置的那个数会被交换，那么必然满足那个数是数组中最小的数的倍数。如果不满足那么不成立。

这里有个问题，如果每个和排好序之后不同的数的位置的数都是那个最小值的倍数，就一定可以排好序吗？万一他们的最小公倍数也是最小值的倍数呢？这里是一定的，因为我们可以通过最小值，来进行三次交换，实现那两个数交换的目标。

代码：

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=1e5+5;
int a[maxn],c[maxn];

int main()
{
    int T=read();
    while(T--)
    {
        int n=read();
        REP(i,1,n) a[i]=c[i]=read();
        sort(c+1,c+n+1);
        int m=c[1],p=1,yes=1;
        REP(i,1,n) if(a[i]%m && a[i]!=c[i]) {yes=0; break;}
        puts(yes?"YES":"NO");
    }

    return 0;
}

D Maximum Distributed Tree

题意：给出一棵 n 个结点的树，再以 m 个质数的乘积（ $p_1\cdot p_2\dots p_m$ ）的形式给出一个大整数 k，你需要给树上每一条边分配一个正边权，使得最终所有边权乘积等于 k，并且边权为 1 的个数尽量少。然后定义 $f(u,v)$ 为树上 u 到 v 的边权之和，在满足刚才的条件下，要使得 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}f(i,j)$ 尽可能大，并求出这个最大值取模 1e9+7 。

思路：先考虑前面那个条件，这要分两种情况：

如果 $n-1\ge m$ ，那么说明边的数目比质数数目要多，那么最好的分配方式就是每个质数赋值到一个边，剩下的边权都为 1，这样保证 1 的个数最少；
如果 $n-1<m$ ，这时边的数目少于质数的数目，那么最好的分配方式中 1 的个数就为 0，这里凭感觉可以想象到，把其中若干个最大的质数乘起来，然后剩下的一一分配，这样是最优的。

然后所有的边权就已经定好了，剩下的就是该怎么分，对于某一条边，它的贡献就是边权乘上这条边两边的结点数的乘积，所以只用对树 dfs 一次，把 n-1 个乘积保存起来，然后从大到小一一分配即可。

代码：

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int M=1e9+7;
const int maxn=1e5+5;
VI G[maxn];
int n,p[maxn],m,ans,tmp[maxn],siz[maxn];
priority_queue<LL> Q;

void dfs(int u,int fa)
{
    siz[u]=1;
    for(int v:G[u]) if(v!=fa)
    {
        dfs(v,u);
        siz[u]+=siz[v];
    }
    LL x=1ll*siz[u]*(n-siz[u]);
    if(x) Q.push(x);
}

int main()
{
    int T=read();
    while(T--)
    {
        n=read();
        REP(i,1,n) G[i].clear(),siz[i]=0;
        ans=0;
        REP(i,1,n-1)
        {
            int x=read(),y=read();
            G[x].pb(y); G[y].pb(x);
        }
        m=read();
        REP(i,1,m) p[i]=read();
        sort(p+1,p+m+1,greater<int>());
        if(n-1>=m)
        {
            REP(i,m+1,n-1) p[i]=1;
            m=n-1;
        }
        else
        {
            int cnt=1;
            tmp[1]=1;
            REP(i,1,m-n+2) tmp[1]=1ll*tmp[1]*p[i]%M;
            REP(i,m-n+3,m) tmp[++cnt]=p[i];
            m=n-1;
            REP(i,1,m) p[i]=tmp[i];
        }
        //REP(i,1,m) cout<<p[i]<<' ';

        dfs(1,0);
        REP(i,1,m)
        {
            LL x=Q.top()%M; Q.pop();
            ans=(ans+1ll*p[i]*x%M)%M;
        }
        printf("%d\n",ans);
    }

    return 0;
}

E Divide Square

题意：给出一个 $10^6\times10^6$ 的正方形框框，然后在上面画 n 条水平线，m条竖直线，保证每条线至少和正方形框框有一个交点，问最后正方形被分成了多少块。

思路：其实就是算交点。本来的答案是 1，现在如果在内部多一个交点，那么答案就 +1，如果某条线和正方形两边都相交，那么答案再 +1 。

算交点的话就是扫描线啦，比如可以把竖直的线的两个端点都存起来，然后排个序，然后扫描线从下往上扫，遇到某个竖直的线的端点，就判断它是进入还是出去（也就是下端点还是上端点），然后更新一下线段树，这里线段树维护当前扫描线中哪些位置是有竖直线的，然后如果当前扫描线的位置有水平线，那么就查询一下区间和就行了。

另外就是对于每个位置要注意，处理的顺序是：该进来的先进来，然后统计答案，该出去的出去。因为端点相交也是算对答案有贡献的。

代码：

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

template <class T>
struct segment_tree_sum
{
    #define chl (k<<1)
    #define chr (k<<1|1)
    #define mid ((l+r)>>1)
    T *t,*tag;
    int n;

    segment_tree_sum(int n) {t=new T[n<<2](); this->n=n;}

    void push_up(int k) {t[k]=t[chl]+t[chr];}

    void update(int k,int l,int r,int ll,T x)
    {
        if(ll<l || ll>r) return;
        if(ll==l && ll==r)
        {
            t[k]=x;
            return;
        }
        update(chl,l,mid,ll,x);
        update(chr,mid+1,r,ll,x);
        push_up(k);
    }
    void update(int ll,T x) {update(1,1,n,ll,x);}

    T query(int k,int l,int r,int ll,int rr)
    {
        if(l>rr || ll>r) return 0;
        if(l>=ll && r<=rr) return t[k];
        return query(chl,l,mid,ll,rr)+query(chr,mid+1,r,ll,rr);
    }
    T query(int ll,int rr) {return query(1,1,n,ll,rr);}
};

const int maxn=1e6+5,N=1e6;
segment_tree_sum<int> t(N);
int n,m,tot;
int lx[maxn],rx[maxn];
int ly[maxn],ry[maxn];
P a[maxn<<1];
LL ans;

void lai(int i)
{
    int x=a[i].second,y=a[i].first;
    if(y==ly[x])
    {
        t.update(x,1);
    }
}

void qu(int i)
{
    int x=a[i].second,y=a[i].first;
    if(y==ry[x])
    {
        t.update(x,0);
    }
}

void leijia(int y)
{
    if(lx[y]<rx[y])
    {
        ans+=t.query(lx[y],rx[y]);
    }
}

int main()
{
    n=read(),m=read();
    REP(i,1,n)
    {
        int y=read();
        lx[y]=read(); rx[y]=read();
    }
    REP(i,1,m)
    {
        int x=read();
        ly[x]=read(),ry[x]=read();
        a[++tot]=P(ly[x],x);
        a[++tot]=P(ry[x],x);
    }
    sort(a+1,a+tot+1);

    int cur=1;
    REP(y,0,N)
    {
        int r=cur-1;
        while(r+1<=tot && a[r+1].first==y) r++;
        REP(i,cur,r) lai(i);
        leijia(y);
        REP(i,cur,r) qu(i);
        cur=r+1;
    }
    REP(i,1,N)
    {
        if(lx[i]==0 && rx[i]==N) ans++;
        if(ly[i]==0 && ry[i]==N) ans++;
    }
    cout<<ans+1<<endl;

    return 0;
}

F Reverse and Swap

题意：给出一个长度为 $2^n$ 的数组，并且有 q 组询问，询问有 4 种：

把 $a_x$ 替换为 k；
从数组开头开始，把所有长度为 $2^k$ 的子数组翻转；
从数组开头开始，把所有相邻的长度为 $2^k$ 的子数组两两交换；
查询 $[l, r]$ 的和；

你要维护一个数据结构，实现以上操作。

思路：一开始想复杂了，后来的思路应该是正解：首先可以看到，第二个和第三个操作都是基于深度的，也就是如果对这个数组建立一棵完全二叉树，那么这两个操作都是对某个深度的所有结点进行交换他们的儿子这样的操作，不同之处在于第二个操作是操作某个深度往下所有深度，第三个操作只操作某个深度。

那么我们就用线段树去维护一个数组 a，然后再用一个数组记录每个深度应该交换儿子多少次，那么原本正常的替换和查询的线段树现在就要根据某个区间的交换次数，来决定往下查询的时候是进入左儿子，还是右儿子。所以就是一个变了一点点的单点修改区间求和线段树而已。

代码：

#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=2e6+5;
LL sum[maxn],rev[maxn];
int a[maxn],n,m,q,d[maxn];

#define chl (k<<1)
#define chr (k<<1|1)
#define mid ((l+r)>>1)

void build(int k,int l,int r,int de)
{
    d[k]=de;
    if(l>r) return;
    if(l==r) {sum[k]=a[l]; return;}
    build(chl,l,mid,de+1); build(chr,mid+1,r,de+1);
    sum[k]=sum[chl]+sum[chr];
}

void update(int k,int l,int r,int id,int x)
{
    if(id<l || id>r) return;
    if(l==r && l==id) {sum[k]=x; return;}
    if(rev[d[k]]%2==1)
    {
        update(chl,mid+1,r,id,x);
        update(chr,l,mid,id,x);
    }
    else
    {
        update(chl,l,mid,id,x);
        update(chr,mid+1,r,id,x);
    }
    sum[k]=sum[chl]+sum[chr];
}

LL query(int k,int l,int r,int ll,int rr)
{
    if(ll>r || rr<l) return 0;
    if(l>=ll && r<=rr) return sum[k];
    if(rev[d[k]]%2==1)
    {
        LL x=query(chl,mid+1,r,ll,rr);
        LL y=query(chr,l,mid,ll,rr);
        return x+y;
    }
    else
    {
        LL x=query(chl,l,mid,ll,rr);
        LL y=query(chr,mid+1,r,ll,rr);
        return x+y;
    }
}

int main()
{
    n=read(),q=read(); m=1<<n;
    REP(i,1,m) a[i]=read();
    build(1,1,m,1);

    while(q--)
    {
        int type=read();
        if(type==1)
        {
            int x=read(),k=read();
            update(1,1,m,x,k);
        }
        else if(type==2)
        {
            int k=read();
            REP(i,n+1-k,n) rev[i]++;
        }
        else if(type==3)
        {
            int k=read();
            rev[n-k]++;
        }
        else
        {
            int l=read(),r=read();
            printf("%lld\n",query(1,1,m,l,r));
        }
    }

    return 0;
}