首页 > 代码库 > FR #2题解

FR #2题解

2024-08-28 02:42:53   217人阅读

A.

　　考虑把(u,v)的询问离线挂在u上，然后dfs，每次从fath[x]到[x]相当于x子树dis区间加1，x子树以外区间-1，然后维护区间和区间平方和等。

      常数略大。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxv 100500
#define maxe 200500
using namespace std;
long long n,fath[maxv],q,uu,vv,dis[maxv],l[maxv],r[maxv],times=0,fdfn[maxv],g[maxv],nume=1,ans[maxv],cnt;
long long tot=0,root,ls[maxv<<2],rs[maxv<<2],val1[maxv<<2],val2[maxv<<2],lazy[maxv<<2];
vector <long long> v[maxv],id[maxv];
bool vis[maxv];
struct edge
{
    long long v,nxt;
}e[maxe];
long long read()
{
    char ch;long long data=http://www.mamicode.com/0;
    while (ch<‘0‘ || ch>‘9‘) ch=getchar();
    while (ch>=‘0‘ && ch<=‘9‘)
    {
        data=data*10+ch-‘0‘;
        ch=getchar();
    }
    return data;
}
void addedge(long long u,long long v)
{
    e[++nume].v=v;e[nume].nxt=g[u];g[u]=nume;
    e[++nume].v=u;e[nume].nxt=g[v];g[v]=nume;
}
void pushup(long long now,long long left,long long right)
{
    val1[now]=val1[ls[now]]+val1[rs[now]];
    val2[now]=val2[ls[now]]+val2[rs[now]];
}
void pushdown(long long now,long long left,long long right)
{
    if (!lazy[now]) return;
    long long mid=left+right>>1,d=lazy[now],ll=mid-left+1,rr=right-mid;
    val1[ls[now]]+=2*d*val2[ls[now]]+d*d*ll;val1[rs[now]]+=2*d*val2[rs[now]]+d*d*rr;
    val2[ls[now]]+=d*ll;val2[rs[now]]+=d*rr;
    lazy[ls[now]]+=d;lazy[rs[now]]+=d;
    lazy[now]=0;
}
void build(long long &now,long long left,long long right)
{
    now=++tot;lazy[now]=0;
    if (left==right)
    {
        val1[now]=dis[fdfn[left]]*dis[fdfn[left]];val2[now]=dis[fdfn[left]];
        return;
    }
    long long mid=left+right>>1;
    build(ls[now],left,mid);
    build(rs[now],mid+1,right);
    pushup(now,left,right);
}
long long ask(long long now,long long left,long long right,long long l,long long r)
{
    pushdown(now,left,right);
    if ((left==l) && (right==r)) return val1[now];
    long long mid=left+right>>1;
    if (r<=mid) return ask(ls[now],left,mid,l,r);
    else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r);
    else return ask(ls[now],left,mid,l,mid)+ask(rs[now],mid+1,right,mid+1,r);
}
void modify(long long now,long long left,long long right,long long l,long long r,long long val)
{
    if (l>r) return;
    pushdown(now,left,right);
    if ((left==l) && (right==r)) 
    {
        lazy[now]+=val;
        val1[now]+=2*val*val2[now]+val*val*(right-left+1);val2[now]+=val*(right-left+1);
        return;
    }
    long long mid=left+right>>1;
    if (r<=mid) modify(ls[now],left,mid,l,r,val);
    else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,val);
    else
    {
        modify(ls[now],left,mid,l,mid,val);
        modify(rs[now],mid+1,right,mid+1,r,val);
    }
    pushup(now,left,right);
}
void get_ans(long long x)
{
    for (long long i=0;i<v[x].size();i++)
        ans[id[x][i]]=ask(root,1,n,l[v[x][i]],r[v[x][i]]);
}
void modify_tree(long long x,long long f)
{
    modify(root,1,n,l[x],r[x],-f);
    modify(root,1,n,1,l[x]-1,f);
    modify(root,1,n,r[x]+1,n,f);
}
void dfs1(long long x)
{
    l[x]=r[x]=++times;fdfn[times]=x;
    for (long long i=g[x];i;i=e[i].nxt)
    {
        long long v=e[i].v;
        if (v!=fath[x])
        {
            dis[v]=dis[x]+1;
            dfs1(v);
            r[x]=max(r[x],r[v]);
        }
    }
}
void dfs2(long long x)
{
    get_ans(x);
    for (long long i=g[x];i;i=e[i].nxt)
    {
        long long v=e[i].v;
        if (v!=fath[x])
        {
            modify_tree(v,1);
            dfs2(v);
            modify_tree(v,-1);
        }
    }
}
int main()
{
    n=read();
    for (long long i=1;i<=n-1;i++) {fath[i+1]=read();addedge(fath[i+1],i+1);}
    q=read();
    for (long long i=1;i<=q;i++)
    {
        uu=read();vv=read();
        v[uu].push_back(vv);id[uu].push_back(i);
    }
    dfs1(1);build(root,1,n);
    dfs2(1);
    for (long long i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}

B.

　　我们发现k=0的时候可以o(1)计算（毕竟是01序列）。当k>=1的时候可以证明答案是ceil(l/2)*trunc(l/2)。

     要善于猜结论啊。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500500
using namespace std;
long long n,q,a[maxn],s1[maxn],s[maxn],x[maxn],y[maxn],k[maxn],cnt[2][maxn],ans[maxn],tab[maxn];
long long read()
{
    char ch;long long data=http://www.mamicode.com/0;
    while (ch<‘0‘ || ch>‘9‘) ch=getchar();
    while (ch>=‘0‘ && ch<=‘9‘)
    {
        data=data*10+ch-‘0‘;
        ch=getchar();
    }
    return data;
}
void calc(long long type,long long pos)
{
    cnt[0][0]=1;tab[0]=0;
    for (long long i=1;i<=n;i++)
    {
        cnt[0][i]=cnt[0][i-1];cnt[1][i]=cnt[1][i-1];
        if (!s[i]) cnt[0][i]++;
        else cnt[1][i]++;
        tab[i]=tab[i-1]+cnt[s[i]^1][i];
    }
    if (!type)
    {
        for (long long i=1;i<=n;i++)
        {
            if (x[i]>=2) ans[i]=(cnt[1][y[i]-1]-cnt[1][x[i]-2])*cnt[0][y[i]]+(cnt[0][y[i]-1]-cnt[0][x[i]-2])*cnt[1][y[i]]-(tab[y[i]-1]-tab[x[i]-2]);
            else ans[i]=cnt[1][y[i]-1]*cnt[0][y[i]]+cnt[0][y[i]-1]*cnt[1][y[i]]-tab[y[i]-1];
        }
    }
}
int main()
{
    n=read();q=read();
    for (long long i=1;i<=n;i++) {a[i]=read();s1[i]=s1[i-1]^a[i];s[i]=s1[i];}
    for (long long i=1;i<=q;i++) {x[i]=read();y[i]=read();k[i]=read();x[i]++;y[i]++;}
    calc(0,0);
    for (int i=1;i<=q;i++)
    {
        if (k[i])
        {
            long long l=y[i]-x[i]+2;
            ans[i]=(l/2+(l&1))*(l/2);
        }
    }
    for (long long i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}

C.

　　这TM的是个环套树啊。、

      我们找出路径上的值，然后每次加gcd(环长，m）加到最大即可。

      之前10分的原因是神TM没开long long。（我就说我怎么可能写挂这种题）（撤回）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 100500
#define maxe 200500
using namespace std;
struct edge
{
    long long v,w,nxt;
}e[maxe];
long long n,g[maxv],nume=1,dis1[maxv],dis2[maxv],root,father[maxv],anc[maxv][20],dep[maxv];
long long r1,r2,q,s,t,m,u,v,w,a,b,x;
long long read()
{
    char ch;long long data=http://www.mamicode.com/0;
    while (ch<‘0‘ || ch>‘9‘) ch=getchar();
    while (ch>=‘0‘ && ch<=‘9‘)
    {
        data=data*10+ch-‘0‘;
        ch=getchar();
    }
    return data;
}
void addedge(long long u,long long v,long long w) {e[++nume].v=v;e[nume].w=w;e[nume].nxt=g[u];g[u]=nume;}
long long getfather(long long x)
{
    if (x!=father[x]) father[x]=getfather(father[x]);
    return father[x];
}
bool unionn(long long a,long long b)
{
    long long f1=getfather(a),f2=getfather(b);
    if (f1==f2) return true;
    father[f1]=f2;return false;
}
void dfs(long long x,long long father)
{
    for (long long i=g[x];i;i=e[i].nxt)
    {
        long long v=e[i].v;
        if (v!=father)
        {
            anc[v][0]=x;dep[v]=dep[x]+1;
            dis1[v]=dis1[x]+e[i].w;dis2[v]=dis2[x]+e[i^1].w;
            dfs(v,x);
        }
    }
}
void get_table()
{
    for (long long e=1;e<=19;e++)
        for (long long i=1;i<=n;i++)
            anc[i][e]=anc[anc[i][e-1]][e-1];
}
long long lca(long long x,long long y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (long long e=19;e>=0;e--)
        if ((dep[anc[x][e]]>=dep[y]) && (anc[x][e]))
            x=anc[x][e];
    if (x==y) return x;
    for (long long e=19;e>=0;e--)
    {
        if (anc[x][e]!=anc[y][e])
        {
            x=anc[x][e];
            y=anc[y][e];
        }
    }
    return anc[x][0];
}
long long gcd(long long a,long long b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
long long calc(long long x)
{
    x=(x%m+m)%m;
    long long f1=(r1%m+m)%m,d1=gcd(f1,m);
    return (m-1-x)/d1*d1+x;
}
int main()
{
    n=read();
    for (long long i=1;i<=n;i++) father[i]=i;
    for (long long i=1;i<=n;i++)
    {
        a=read();b=read();x=read();
        if (unionn(a,b)) {root=a;u=a;v=b;w=x;}
        else {addedge(a,b,x);addedge(b,a,-x);}
    }
    dfs(root,0);get_table();
    r1=dis1[v]-w;r2=dis2[v]+w;
    q=read();
    for (long long i=1;i<=q;i++)
    {
        s=read();t=read();m=read();x=lca(s,t);
        printf("%lld\n",calc(dis2[s]-dis2[x]+dis1[t]-dis1[x]));
    } 
    return 0;
}

 

FR #2题解


联系
我们